Can Dijkstra's Algorithm work on a graph with weights of 0?

Question

If there exists a weighted graph G, and all weights are 0, does Dijkstra's algorithm still find the shortest path? If so, why?

As per my understanding of the algorithm, Dijsktra's algorithm will run like a normal BFS if there are no edge weights, but I would appreciate some clarification.

Answer 1

Explanation

Dijkstra itself has no problem with 0 weight, per definition of the algorithm. It only gets problematic with negative weights.

Since in every round Dijkstra will settle a node. If you later find a negative weighted edge, this could lead to a shorter path to that settled node. The node would then need to be unsettled, which Dijkstras algorithm does not allow (and it would break the complexity of the algorithm). It gets clear if you take a look at the actual algorithm and some illustration.

The behavior of Dijkstra on such an all zero-graph is the same as if all edges would have a different, but same, value, like 1 (except of the resulting shortest path length). Dijkstra will simply visit all nodes, in no particular order. Basically, like an ordinary Breadth-first search.

---

Details

Take a look at the algorithm description from Wikipedia:

 1 function Dijkstra(Graph, source):
 2
 3     create vertex set Q
 4
 5     for each vertex v in Graph:           // Initialization
 6         dist[v] ← INFINITY                // Unknown distance from source to v
 7         prev[v] ← UNDEFINED               // Previous node in optimal path from source
 8         add v to Q                        // All nodes initially in Q (unvisited nodes)
 9
10     dist[source] ← 0                      // Distance from source to source
11      
12     while Q is not empty:
13         u ← vertex in Q with min dist[u]  // Node with the least distance
14                                           // will be selected first
15         remove u from Q 
16          
17         for each neighbor v of u:         // where v is still in Q.
18             alt ← dist[u] + length(u, v)
19             if alt < dist[v]:             // A shorter path to v has been found
20                 dist[v] ← alt 
21                 prev[v] ← u 
22
23     return dist[], prev[]

The problem with negative values lies in line 15 and 17. When you remove node u, you settle it. That is, you say that the shortest path to this node is now known. But that means you won't consider u again in line 17 as a neighbor of some other node (since it's not contained in Q anymore).

With negative values it could happen that you later find a shorter path (due to negative weights) to that node. You would need to consider u again in the algorithm and re-do all the computation that depended on the previous shortest path to u. So you would need to add u and every other node that was removed from Q that had u on its shortest path back to Q.

Especially, you would need to consider all edges that could lead to your destination, since you never know where some nasty -1_000_000 weighted edge hides.

The following example illustrates the problem:

Dijkstra will declare the red way as shortest path from A to C, with length 0. However, there is a shorter path. It is marked blue and has a length of 99 - 300 + 1 = -200.

With negative weights you could even create a more dangerous scenario, negative cycles. That is a cycle in the graph with a negative total weight. You then need a way to stop moving along the cycle all the time, endlessly dropping your current weight.

---

Notes

In an undirected graph edges with weight 0 can be eliminated and the nodes be merged. A shortest path between them will always have length 0. If the whole graph only has 0 weights, then the graph could just be merged to one node. The result to every shortest path query is simply 0.

The same holds for directed graphs if you have such an edge in both directions. If not, you can't do that optimization as you would change reach-ability of nodes.