3 ms·
> 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 n
by 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.