0
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.