Why Dijkstra's Algorithm Fails with Negative Weight Edges: An In-Depth Analysis of Greedy Strategy Limitations

Core Algorithm Principles and Greedy Strategy

Dijkstra's algorithm is a greedy-based single-source shortest path algorithm whose core idea involves progressively expanding the set of known shortest paths. The algorithm maintains two sets: the set of vertices with determined shortest paths (typically called the closed set) and the set of vertices awaiting processing (the open set). In each iteration, the algorithm selects the vertex with the smallest current distance from the source from the open set, adds it to the closed set, and then updates the distance values of all its neighbors.

The key assumption of the algorithm is that once a vertex is marked as closed, the algorithm has found the shortest path from the source to that vertex. This assumption holds when all edge weights are non-negative, because any path through other unclosed vertices must include additional positive weights, thus cannot yield a shorter path.

Failure Mechanism Induced by Negative Weight Edges

When negative weight edges exist in the graph, the above assumption no longer holds. Consider the following concrete example:

Vertex set V = {A, B, C}
Edge set E = {(A, C, 2), (A, B, 5), (B, C, -10)}

The corresponding graph structure is:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

Let's analyze the execution of Dijkstra's algorithm from vertex A step by step:

1. Initialization: Set A's distance to 0, B and C's distances to infinity
2. First selection: From open set {A,B,C}, select vertex A with smallest distance and close it
3. Update neighbors: Update B's distance to 5, C's distance to 2
4. Second selection: From open set {B,C}, select vertex C (distance 2) and close it
5. Algorithm termination: Finally select vertex B, but since C is already closed, the path through B to C is not considered

The algorithm ultimately produces the shortest path as: A→C (distance 2), but actually there exists a shorter path A→B→C (distance 5 + (-10) = -5). The root cause is that the algorithm prematurely marks vertex C as closed, thus missing the optimization opportunity through the negative weight edge B→C.

Algorithm Implementation and Key Code Analysis

Below is the standard implementation of Dijkstra's algorithm, highlighting the key parts that cause failure with negative weight edges:

function dijkstra(graph, source):
    dist = map with default value infinity
    prev = empty map
    queue = priority queue containing all vertices
    
    dist[source] = 0
    
    while queue is not empty:
        u = queue.extract_min()  # Key step: select current minimum distance vertex
        
        for each neighbor v of u:
            if v in queue:  # Only process neighbors still in queue
                alt = dist[u] + graph[u][v]
                if alt < dist[v]:
                    dist[v] = alt
                    prev[v] = u
                    queue.decrease_key(v, alt)
    
    return dist, prev

The critical limitation manifests in the if v in queue condition. Once a vertex is removed from the queue (i.e., marked as closed), the algorithm no longer considers the possibility of updating other vertices through that vertex. In positive-weight graphs, this design is reasonable because paths through closed vertices cannot provide shorter alternatives. However, when negative weight edges exist, closed vertices might offer shorter paths to other vertices through negative edges.

Mathematical Principles and Correctness Proof

The correctness of Dijkstra's algorithm relies on the following mathematical property: for any closed vertex u and any vertex v still in the queue, dist[u] ≤ dist[v]. When all edge weights are non-negative, the path length through u to v is at least dist[u] + w(u,v) ≥ dist[u] ≥ dist[v], thus cannot improve v's current distance.

However, when negative weight edges exist, w(u,v) might be negative, making dist[u] + w(u,v) < dist[v] possible. This breaks the algorithm's monotonicity guarantee, leading to incorrect final results.

Alternative Approach: Bellman-Ford Algorithm

For graphs containing negative weight edges, the Bellman-Ford algorithm provides a viable solution. This algorithm employs dynamic programming principles, ensuring true shortest paths through multiple relaxation operations. Its core pseudocode is:

function bellman_ford(graph, source):
    dist = map with default value infinity
    dist[source] = 0
    
    for i from 1 to |V| - 1:
        for each edge (u, v) in graph:
            if dist[u] + graph[u][v] < dist[v]:
                dist[v] = dist[u] + graph[u][v]
    
    # Detect negative weight cycles
    for each edge (u, v) in graph:
        if dist[u] + graph[u][v] < dist[v]:
            return "Graph contains negative weight cycle"
    
    return dist

The Bellman-Ford algorithm has a time complexity of O(VE), which is worse than Dijkstra's O((V+E)logV), but it correctly handles negative weight edges and can detect the existence of negative weight cycles.

Practical Applications and Selection Guidelines

In practical engineering applications, choosing the appropriate shortest path algorithm requires comprehensive consideration of graph characteristics and performance requirements:

• Pure positive-weight graphs: Prefer Dijkstra's algorithm for better efficiency
• Graphs with negative weights but no negative cycles: Use Bellman-Ford algorithm
• Graphs potentially containing negative cycles: Must use Bellman-Ford for detection
• Large-scale graphs with limited weight ranges: Consider variants like Dial's algorithm

Understanding the limitations of Dijkstra's algorithm not only helps in its correct application but also lays important groundwork for learning more complex shortest path algorithms. This deep comprehension of algorithmic assumptions and applicability conditions represents core content in computer science education.