I am reading about algorithms to find the shortest path on a graph with one source, and I have a doubt about Dijkstra's algorithm about the negative weights on edges. In this case is Bellman-Ford algorithm a better solution for this part?
1
- $\begingroup$ en.wikipedia.org/wiki/…, cs.stackexchange.com/q/102437/755, cs.stackexchange.com/q/87556/755, cs.stackexchange.com/q/7649/755 $\endgroup$D.W.– D.W. ♦2023-01-30 23:20:43 +00:00Commented Jan 30, 2023 at 23:20
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
Dijkstra's algorithm might solve some cases where there are negative edges in the graph. However, it doesn't solve for every graph that has a negative edge. For instance, if you have a negative cycle, Dijkstra won't work.
For graphs with negative weighted edges, you should use Bellman-Ford's algorithm.
If you want to find the shortest path from one source, then use Bellman-Ford on graphs with negative edges, and Dijkstra on graphs with non-negative edges.
If you want to find the shortest path for every pair of vertices $(u, v)$, then you can use Floyd-Warshall algorithm
I will leave you to determine, whether on graphs with non-negative edges, whether it is more efficient to run Dijkstra $n$ times where $n = |V|$, or to run Floyd-Warshall.
