3 ms·

>do it one pass in O(n) time Mind you, the “n” here is not the number of nodes! More precisely, Dijkstra’s algorithm runs in O(E + V * log V) time (if the pri

>do it one pass in O(n) time Mind you, the “n” here is not the number of nodes! More precisely, Dijkstra’s algorithm runs in O(E + V * log V) time (if the priority queue is implemented with a heap), where E is the number of edges and V is the number of nodes. In the general case, E = O(V^2) (i.e. fully connected graph), so Dijkstra’s algorithm can calculate the shortest path to V nodes in O(V^2) time. It sounds less staggering this way. And in a general graph where negative edge-weights are permitted, it’s actually impossible to find the shortest path between two nodes without finding the shortest path between the source node and every other node! It’s pretty easy to see why: you can’t be sure you’ve actually found the shortest path until you’ve covered all the edges, because there’s always the possibility of a very large negative edge to be visited. Dijkstra’s algorithm improves on this general case by exploiting the fact that the edges must have positive weight.

mhandley 8y ago
You are, of course, correct. That was sloppy writing on my part.
munificent 8y ago
> And in a general graph where negative edge-weights are permitted, it’s actually impossible to find the shortest path between two nodes without finding the shortest path between the source node and every other node! If there are negative edge-weights and cycles may occur, there is no shortest path between some nodes. You can keep going through a cycle whose total weight is negative getting "shorter" and "shorter". It's like a race where one shortcut takes you back in time and leaves you where you started. You can use it to finish the race as far back in time before you started as you want.
- aaaaaaaaaab 8y ago
  Sure, but between "all edges have positive weights" and "there are cycles with negative total weight" there are still graphs that have negative edge weights, yet there's no negative-weight cycle. Example: V = { A, B, C } E = { A -> B, B -> C, C -> A } weight(A -> B) = 1 weight(B -> C) = 1 weight(C -> A) = -1
  - munificent 8y ago
    Right, yes.

mhandley 8y ago

You are, of course, correct. That was sloppy writing on my part.

munificent 8y ago

> And in a general graph where negative edge-weights are permitted, it’s actually impossible to find the shortest path between two nodes without finding the shortest path between the source node and every other node! If there are negative edge-weights and cycles may occur, there is no shortest path between some nodes. You can keep going through a cycle whose total weight is negative getting "shorter" and "shorter". It's like a race where one shortcut takes you back in time and leaves you where you started. You can use it to finish the race as far back in time before you started as you want.

aaaaaaaaaab 8y ago
Sure, but between "all edges have positive weights" and "there are cycles with negative total weight" there are still graphs that have negative edge weights, yet there's no negative-weight cycle. Example: V = { A, B, C } E = { A -> B, B -> C, C -> A } weight(A -> B) = 1 weight(B -> C) = 1 weight(C -> A) = -1
- munificent 8y ago
  Right, yes.