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