4 ms·
> but the best algorithm we have (Djikstra’s) runs in exponential time in the worst case Dijkstra doesn't handle negative weights so in that case you can use F
by ithinkso 4y ago
> but the best algorithm we have (Djikstra’s) runs in exponential time in the worst case
Dijkstra doesn't handle negative weights so in that case you can use Ford-Bellman. It's slower than Dijkstra but far from exponential - O(VE) or something like that.
- hammock 4y ago> Dijkstra doesn't handle negative weights I took this straight from the Q&A I referenced in my link: Q. Does Dijkstra's algorithm work with negative weights? A. Yes and no. There are two shortest paths algorithms known as Dijkstra's algorithm, depending on whether a vertex can be enqueued on the priority queue more than once. When the weights are nonnegative, the two versions coincide (as no vertex will be enqueued more than once). The version implemented in DijkstraSP.java (which allows a vertex to be enqueued more than once) is correct in the presence of negative edge weights (but no negative cycles) but its running time is exponential in the worst case.
- thaumasiotes 4y ago> The version implemented in DijkstraSP.java (which allows a vertex to be enqueued more than once) is correct in the presence of negative edge weights (but no negative cycles) This is a strange parenthetical. No shortest-path algorithm can be correct in the presence of a negative cycle; the concept of "shortest path" does not apply to such a graph.
- ghusbands 4y agoI suspect it's to make clear to the peanut gallery that there is indeed a valid shortest path in the tests they were doing.
- deleted 4y ago[deleted]