Does Dijkstra Work for Undirected Graphs? | When It Fails

Dijkstra works on undirected graphs just fine. The part that decides whether it is correct is not edge direction. It is edge weight. If every edge weight is non-negative, the algorithm can lock in each shortest distance one node at a time and never need to walk that choice back.

That point clears up a lot of confusion. Many learners hear Dijkstra tied to “directed weighted graphs” in textbook wording and start to wonder whether undirected graphs need a different method. They do not. An undirected graph can be treated as a pair of equal directed edges, one in each direction, and the same shortest-path logic still holds.

Where people get burned is this: an undirected graph with even one negative edge is a bad fit. That single edge can be traversed both ways, which creates a negative cycle right away. Once that happens, shortest paths stop being well-defined, since you can loop and keep pushing the total cost lower.

Why Undirected Edges Are Fine For Dijkstra

The algorithm cares about one rule: once it picks the unvisited node with the smallest tentative distance, that distance must already be final. That rule stays true on an undirected graph when all weights are zero or above.

Think of an undirected edge between A and B with weight 4. In shortest-path terms, that means you can move from A to B for 4 and from B to A for 4. Nothing in Dijkstra breaks there. The graph still has weighted edges, and every relaxation step still makes sense.

NIST’s definition of Dijkstra’s algorithm puts the rule in compact form: it finds shortest paths from one source in a weighted graph, and all weights must be non-negative. That is the real line in the sand.

A Small Mental Model

Say you start at node S on an undirected graph. Dijkstra keeps a running best distance to each node. At each step, it pulls out the node with the smallest tentative value and marks it done.

• If all remaining edges add zero or more cost, no unseen route can sneak in later and make that finished node cheaper.
• If an edge could subtract cost, that safe ordering falls apart.
• So the graph can be directed or undirected; the weight rule is what decides correctness.

Using Dijkstra On An Undirected Graph With Weights

In practice, an undirected graph is one of the most common places to use Dijkstra. Road networks, game maps, cable runs, and distance graphs often behave like undirected weighted graphs when travel cost is the same both ways.

There is also no penalty in the idea itself for using an undirected graph. The time cost still depends on the data structure you use for the priority queue and on the number of vertices and edges. With a binary heap, the standard bound is O((V + E) log V).

MIT’s Lecture 13 on Dijkstra frames it the same way many interviewers do: shortest paths with non-negative edge weights. That wording covers undirected graphs too, as long as the weight rule holds.

Here is the clean way to decide whether Dijkstra belongs on your undirected graph:

• Use it when edge weights are all non-negative.
• Use BFS instead when every edge has the same weight, such as 1.
• Do not use it when any edge weight is negative.
• Do not expect paths to unreachable nodes; those stay at infinity or come back as “no path.”

What Counts As “Working”

When people ask whether Dijkstra works, they usually mean one of two things. First, does it return the right shortest-path distances from the source? Second, can it also rebuild the actual path? On a non-negative undirected graph, the answer to both is yes.

You can store a predecessor for each node whenever a better route is found. Once the algorithm ends, walk those predecessor links backward from the target to rebuild the route.

Undirected Graph Case	Does Dijkstra Work?	What Happens
All weights are positive	Yes	Returns correct shortest distances and paths.
Some weights are zero	Yes	Still correct; ties may create more than one shortest path.
Every edge has weight 1	Yes, but BFS is leaner	Dijkstra still works, yet BFS gets the same result with less overhead.
Graph is disconnected	Yes	Reachable nodes get distances; unreachable nodes stay infinite.
One edge has a negative weight	No	The edge can be traversed in both directions, creating a negative cycle.
Multiple edges between the same nodes	Yes	The algorithm can still pick the lighter option when implemented for that graph type.
Self-loops with non-negative weight	Yes	They do not beat an existing shortest path unless the loop cost is zero and ties are allowed.
Need all-pairs shortest paths	Not as a single run	You would run it from each source or switch to another all-pairs method.

When Dijkstra Fails On An Undirected Graph

The failure case is clean and sharp: negative edges. On an undirected graph, a negative edge from U to V means you can go U to V and right back to U, dropping the path total each time. That is a negative cycle of length two.

Once a negative cycle exists, there is no single shortest path through that region. You can always loop one more time and get a smaller total. So this is not just a minor bug in the algorithm. The shortest-path problem itself stops having a finite answer there.

That is why people often say “Dijkstra fails on negative weights” and leave it at that. For undirected graphs, the warning is even stronger. A single negative edge is enough to poison the setup.

NetworkX’s shortest-path reference separates the choices in a handy way: Dijkstra is the general pick for non-negative weights, while Bellman–Ford is the choice for graphs with negative edge weights.

Zero Weights Are Not A Problem

Zero-weight edges often make people uneasy, but they are fine. They can create ties, and ties can create multiple shortest paths with the same total cost. None of that breaks correctness.

The only thing to watch is implementation detail. If your priority queue or visited set is coded sloppily, tied values can expose bugs in path reconstruction. That is a coding problem, not a graph-theory problem.

Unweighted Undirected Graphs Need Less Machinery

If every edge has the same cost, Dijkstra is valid but not the neatest pick. BFS gives shortest paths by hop count in linear time, and the code is often shorter. In interviews and production code alike, that choice reads better.

Goal	Best Method	Reason
Unweighted undirected graph	BFS	Shortest path in hops with low overhead.
Undirected graph with non-negative weights	Dijkstra	Correct and efficient for weighted shortest paths.
Graph with negative weights	Bellman–Ford	Built for shortest paths when negative edges exist.
All-pairs shortest paths on a dense graph	Floyd–Warshall	Direct all-pairs method with simple structure.

Common Mistakes In Class, Interviews, And Code

A few slips show up again and again with this topic:

• Mixing up directedness and weight rules. Direction is not the blocker. Negative weights are.
• Calling every weighted graph a Dijkstra graph. Weighted is not enough; the weights must be non-negative.
• Using Dijkstra for unit weights out of habit. BFS is usually the cleaner pick there.
• Forgetting disconnected nodes. “No path” is a normal output, not a failure.
• Marking a node visited too early. The node becomes final only when it is popped with the current smallest tentative distance.

One more subtle point: if someone asks this as a theory question, they may want the reason, not just the yes-or-no. The safest answer is short and exact: yes on undirected graphs with non-negative weights; no if any undirected edge is negative, since that creates a negative cycle.

Verdict On Undirected Graphs

Dijkstra is a solid match for undirected graphs. In fact, that is one of its standard homes. If the edges carry non-negative weights, the algorithm returns correct shortest distances and paths from the source.

If your undirected graph has a negative edge, stop there and switch methods. If all edges are unit cost, BFS is often the tidier call. Outside those cases, Dijkstra is right at home.