Skip to main content

Getting Stuck: When Dijkstra Meets Negative Edges

 

Getting Stuck: When Dijkstra Meets Negative Edges

One of the joys (and pains) of computer science is when you take a tool you know, confidently apply it, and then watch everything break down in surprising ways. This happened to me recently when I decided to revisit shortest path algorithms — specifically, Dijkstra’s algorithm — only to get stuck in a swamp of negative edges.

Setting the Scene

The problem was classic:

Given a directed, weighted graph and a source vertex, find the shortest path to all other vertices.

This is the kind of problem that every CS student learns early, usually with Dijkstra’s algorithm. I already knew Dijkstra like an old friend:

  • Keep a priority queue of distances.

  • Always expand the node with the current smallest distance.

  • Relax its edges.

Simple, elegant, efficient (O((V + E) log V) with a binary heap).

So when I started coding a graph utility for my project — a tool to analyze transportation networks — I confidently plugged in Dijkstra.

Attempt 1: Dijkstra on All Graphs

Here’s my initial code:

import heapq

def dijkstra(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    pq = [(0, source)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

The graph was stored as an adjacency list, graph[u] = [(v, weight), ...].

I tested it on a clean, positive-weighted example:

0 --1--> 1 --1--> 2
 \                   /
  --------2---------

Output matched expectations.

Then, like any curious coder, I tried a graph with a negative edge:

0 --4--> 1
0 --5--> 2
1 -- -2 --> 2

The shortest path from 0 to 2 should be 0 → 1 → 2 with cost 2.

But Dijkstra gave me 5.

I stared at the code. No bugs. Dijkstra just… failed.

Red Herring #1: Did I Implement It Wrong?

My first thought was: maybe I had a bug. Maybe I wasn’t handling the priority queue right.

I added debug prints:

print("Relaxing", u, "->", v, "with weight", w)

I watched the updates step by step. And everything checked out.

But the algorithm stubbornly refused to take the negative edge into account properly.

I was stuck — but not yet ready to admit that the problem wasn’t my code.

Red Herring #2: Maybe If I “Fix” the Edge Weights

In frustration, I thought: what if I just shift all weights up by a constant, so none are negative? For example, add +2 to every weight in the graph.

That would turn the previous graph into:

0 --6--> 1
0 --7--> 2
1 --0--> 2

Now there are no negative weights.

I reran Dijkstra… and the result was wrong again.

Why? Because shifting weights changes relative path costs. A path with more edges is disproportionately penalized, even if it was shorter before.

I realized this “fix” was bogus. Dead end.

Researching the Problem

At this point, I did what anyone does when stuck: I started Googling “Dijkstra negative edges.”

The answer was blunt:

Dijkstra’s algorithm only works on graphs with nonnegative edge weights.

The moment negative weights are involved, it can’t guarantee correctness.

I felt both relief (my code was fine) and despair (my tool was useless on real-world graphs where discounts or penalties could introduce negative weights).

So what now?

Attempt 2: Bellman–Ford to the Rescue

The standard alternative is the Bellman–Ford algorithm. Unlike Dijkstra, it doesn’t assume nonnegative weights. It works by relaxing all edges repeatedly — up to V-1 times for V vertices.

Here’s the code I wrote:

def bellman_ford(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    
    for _ in range(n-1):
        for u in range(n):
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
    
    # detect negative cycles
    for u in range(n):
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                raise ValueError("Negative cycle detected")
    
    return dist

I tested it on the failing graph:

0 --4--> 1
0 --5--> 2
1 -- -2 --> 2

This time, the answer was correct: distance to 2 was 2.

Victory!

But…

Performance Problems

Bellman–Ford runs in O(VE) time. For small graphs, fine. But when I tried it on a real dataset (thousands of nodes, tens of thousands of edges), it crawled.

I had traded correctness for performance.

Red Herring #3: Can I Hybridize?

I wondered: Could I run Dijkstra when weights are nonnegative, and Bellman–Ford only when they’re negative?

Sure. But that meant writing code to detect “negative edges” and switching algorithms on the fly. Worse, what if some subgraph was negative while others weren’t? You’d still need Bellman–Ford globally.

Not elegant.

Attempt 3: Johnson’s Algorithm

Digging deeper, I discovered Johnson’s algorithm. This one was a revelation.

The trick is:

  1. Add a dummy vertex connected to all others with edge weight 0.

  2. Run Bellman–Ford once to compute “potentials.”

  3. Reweight edges so all weights become nonnegative.

  4. Run Dijkstra from each node.

This way, you combine the correctness of Bellman–Ford with the speed of Dijkstra.

I sketched a rough implementation:

def johnson(graph):
    n = len(graph)
    # Step 1: add dummy vertex
    new_graph = graph + [[]]
    dummy = n
    for u in range(n):
        new_graph[dummy].append((u, 0))
    
    # Step 2: Bellman-Ford from dummy
    h = bellman_ford(new_graph, dummy)
    
    # Step 3: reweight edges
    reweighted = [[] for _ in range(n)]
    for u in range(n):
        for v, w in graph[u]:
            reweighted[u].append((v, w + h[u] - h[v]))
    
    # Step 4: Dijkstra for each source
    dist_all = []
    for u in range(n):
        dist = dijkstra(reweighted, u)
        # fix back weights
        dist = [d + h[v] - h[u] if d < float('inf') else d for v, d in enumerate(dist)]
        dist_all.append(dist)
    
    return dist_all

Now, shortest paths for large graphs with negative edges became feasible again.

Reflection

This entire journey taught me several lessons:

  1. Algorithms come with assumptions.
    Dijkstra is brilliant, but only when all weights are nonnegative. I had overlooked that critical detail.

  2. Dead ends matter.
    My attempts to “shift weights” or hybridize were wrong, but exploring them deepened my intuition about why negative edges are tricky.

  3. There’s always a bigger hammer.
    Bellman–Ford was the first fix, Johnson’s algorithm the ultimate one. Sometimes you need to layer algorithms instead of searching for a single magical solution.

  4. Getting stuck is the best way to learn.
    I’ll never forget now why Dijkstra fails with negative edges. That confusion, the red herrings, the frustration — they carved the lesson deeper than any lecture slide could.


Labels:

Comments

Post a Comment

Popular posts from this blog

Sharp Extremal Bounds for Angular Occupancy (Behind the Curtains)

you can find the full paper here First Attempts, and the Limits of Energy When I first began thinking about angular occupancy, I wasn’t looking for a brand-new problem. I was chasing a theme that has long fascinated me in discrete geometry: how do we measure the geometric richness of a finite set of points? This fascination is not unique to me. Erdős, way back in 1946, posed the distinct distances problem : given n points in the plane, how many distinct distances can they determine? That question alone gave birth to entire decades of work in combinatorial geometry. Later, Fishburn and Füredi asked about distinct angles , while Pach and Sharir studied repeated angles . Each time, the same underlying itch was being scratched: when you place points in the plane, what kinds of diversity can they generate? Why angles, why bins? It was natural to think of angles — after all, distances and directions had already been well studied. But if you go straight for “distinct angles,” you run in...
Post a Comment
Read more

The Art of Goodbye

  The Art of Goodbye: How Relationships End and Why It Matters The friendship had been slowly dissolving for months. What used to be weekly coffee dates became monthly check-ins, then sporadic text messages, then silence. No fight precipitated the ending, no dramatic confrontation or betrayal. It simply... faded. One day you realized you hadn't spoken to someone who was once central to your life, and you weren't sure when the relationship had officially ended or even if it had. This ambiguous loss left you with a peculiar grief – mourning someone still alive, still accessible, but no longer present in your world. This experience is incredibly common yet rarely discussed. While we have cultural scripts for how relationships begin – meet-cutes, first dates, friendship origin stories – we have few models for how they end. We talk extensively about building connections but rarely about gracefully releasing them. This gap in our social understanding leaves many people unprepared ...
1 comment
Read more