I get really confused at times at to which graph algorithms is specific to directed(or undirected) graphs or can be applied to both. So just wanted to create a blog that will contain all the graphs algorithms and their area of application(Directed, undirected or both).
I'll start with some about which I'm sure of:
DFS, BFS : Both
Topo sorting : Directed
Dijkstra : Both
Prims, Kruskal : Both
Please add more algorithms and/or correct me if I'm wrong.!
how did they make dijkstra work for negative weights?
They probably mean dijkstra with potentials
Can you give an explanation? I can't find anything good on google.
link
It's typically used in min-cost-max-flow. In that case the initial potentials are 0 and you just add the distance to vertex potential (if I remember that right) after the Dijkstra run.
If they have to use bellman-ford to get the metagraph then wouldn't it still be O(VE)?
Idk, I found the source, the Dijkstra on 148 page is just the regular one and Exercise 4.4.3.2* on page 150 hints it does not really work (in $$$O((V + E)logV)$$$) for negative weights iiuc. At least $$$O(V(V + E)logV)$$$ (I can construct that).
In order to make Dijkstra's algo work for negative weights, you have to push nodes into the priority queue whenever an edge is relaxed. But this may lead to multiple copies of a single vertex (with different distance info) being pushed into the priority queue. So, you will need to check if the distance of the node that you just removed from the priority queue is == optimal distance calculated for that node. If the condition is true, you use the node. Otherwise, you discard it.
Unfortunately, this modified version of Dijkstra's algo has exponential runtime in the worst case (for graphs with -ve weights) and it doesn't terminate on graphs with -ve cycles. But the type of graphs that can force the exponential behavior occur very rarely so it is quite safe to use it.
Just in case you are interested, here is the link to Dr Halim's modified dijkstra's algo and here is the worst case graph. Click on Example graphs > Dijkstra's Killer.
Want to add: topological sort can only be used with directed acyclic graph(DAG).