### DaviddeGea1's blog

By DaviddeGea1, history, 10 months ago, ,

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).

• DFS, BFS : Both

• Topo sorting : Directed

• Dijkstra : Both

• Prims, Kruskal : Both

• -5

 » 10 months ago, # |   0 For Directed Graphs this info is useful for selecting a particular algo. Source: Competitive programming 3 by Steven Halim.
•  » » 10 months ago, # ^ |   +16 how did they make dijkstra work for negative weights?
•  » » » 10 months ago, # ^ |   0 They probably mean dijkstra with potentials
•  » » » » 10 months ago, # ^ |   0 Can you give an explanation? I can't find anything good on google.
•  » » » » » 10 months ago, # ^ |   0 linkIt'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.
•  » » » » » » 10 months ago, # ^ |   0 If they have to use bellman-ford to get the metagraph then wouldn't it still be O(VE)?
•  » » » » » » » 10 months ago, # ^ | ← Rev. 3 →   0 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).
•  » » » 10 months ago, # ^ |   0 !
•  » » » 10 months ago, # ^ | ← Rev. 4 →   +3 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.
 » 10 months ago, # |   0 Want to add: topological sort can only be used with directed acyclic graph(DAG).