Shortest Path Algorithms: Complete Guide with Examples

The shortest path pattern finds the lowest-cost route between nodes in a graph. GPS navigation, network routing, and ride-hailing pricing all reduce to this single problem, which is why it shows up so often in real interview loops. The interesting part is rarely the graph itself. It is the choice of algorithm, because each one assumes something different about the edges, and using the wrong one silently produces wrong answers.

Definition: given a graph of nodes connected by edges that carry a cost, the shortest path between two nodes is the route whose total edge cost is minimal. The pattern is the family of algorithms that compute this minimum for different edge qualities: unweighted edges, non-negative weights, negative weights, and all-pairs queries.

Real-World Analogy

Say you are planning a road trip and want the cheapest tolls between two cities. You do not settle on a route until you are sure it beats everything you have seen. One strategy is to keep a list of cities you have confirmed the cheapest price for, and every time you confirm a new city, you check whether its tolls open up a cheaper way to reach the cities you have not confirmed yet. That confirm-the-closest-first loop is exactly Dijkstra’s algorithm.

Now imagine the same trip where every road costs exactly one toll, and you just want the fewest roads. You would check all one-hop towns, then all two-hop towns, and stop the moment your destination shows up, because it cannot be reached any faster than it appearing in that layer. That is BFS. The analogy does not stretch to Bellman-Ford or Floyd-Warshall as neatly, but the mental model carries over: shortest path work is about confirming distances in an order that lets you stop trusting unconfirmed routes.

How Dijkstra Actually Works

Dijkstra is a greedy scan organized around one invariant: every time a node is removed from the priority queue with its smallest tentative distance, that distance is final. The queue hands back the node with the lowest known distance, and at that moment no other route can beat it because every remaining route passes through a node with a distance that is already equal to or larger.

    graph TD
    A["Initialize distance[source] = 0, all others = infinity"] --> B["Push (0, source) into the min-heap"]
    B --> C{"Heap empty?"}
    C -->|No| D["Pop the node with the smallest distance"]
    D --> E{"That distance is stale<br/>(larger than the stored one)?"}
    E -->|Yes| C
    E -->|No| F["For each neighbor (v, weight) of u"]
    F --> G{"distance[u] + weight smaller<br/>than the stored distance[v]?"}
    G -->|Yes| H["Update distance[v], push the new candidate"]
    G -->|No| I["Leave distance[v] alone"]
    H --> C
    I --> C
    C -->|Yes| J["Return the distances array"]
  

There are two details to notice in that flow. The stale-entry check is not optional. A node can be pushed several times, each time with a better distance, and only the last entry matters. The other detail is why Dijkstra forbids negative weights. Once a node is popped and treated as final, a better route through a later, cheaper negative edge would be ignored. The greedy only works if the queue always hands back the true minimum, which negative edges break. If negative weights can appear, use Bellman-Ford below.

When to Use This Pattern

Use some shortest path algorithm when a problem matches these characteristics:

• The input is a graph and the question contains “shortest”, “cheapest”, “minimum time”, “fewest moves”, or “closest”. These words are the pattern’s trigger, and the first thing to test is what the edge cost represents.
• All edges carry the same cost, usually a count of steps or moves. Then the layer-by-layer guarantee of BFS gives an answer in
  O(V + E)
  with a plain queue, and no priority queue is needed.
• Edge weights are non-negative and you need distances from a single source to every other node. Dijkstra applies and the standard implementation uses a binary heap.
• Weights can be negative or you need to report negative-cycle existence. Bellman-Ford handles both, at a time cost.
• You need the distance between every pair of nodes in one shot, especially in dense graphs where V is small. Floyd-Warshall trades a big matrix for the simplest triple loop you can write.

These cases overlap. The selection is a progression, and the table below is the decision aid to memorize.

Complexity Analysis

The four classic algorithms sit in four different complexity classes, and the difference between them is usually the deciding factor between a passing and a failing solution.

Space shows up in the distance array in every algorithm, plus a queue or heap for the frontier. Floyd-Warshall is the exception because it needs the full matrix to answer any pair in constant time.

Common Mistakes

These mistakes all follow one pattern: the algorithm runs, returns an answer, and the answer is quietly wrong on a real graph.

Running Dijkstra on negative weights. Dijkstra confirms each node exactly once, in order of distance. A negative edge can create a cheaper route through a node that was already confirmed, and the algorithm will never reconsider it. The test case passes, the interviewer notes the guarantee was violated. Catch it by asking about edge-weight sign in the first minute, then reach for Bellman-Ford when weights can be negative.

Forgetting the stale-entry check when implementing Dijkstra. Without the “popped distance equals the stored distance” check, every improvement to a node pushes another copy into the heap. The result stays correct, but the time complexity silently drifts toward

Marking visited nodes at dequeue time instead of enqueue time in BFS. A node discovered by two neighbors on the same layer gets enqueued twice, and dominates the queue with duplicates in dense graphs. Mark the node the moment it is enqueued. The first neighbor to discover it is the one on the shortest path, so the early mark changes nothing about the distances.

Counting on Floyd-Warshall with a bad infinity. If the matrix is initialized with the language’s INT_MAX and two unreachable values get added, the result overflows into a negative number that looks like a real path. Use a sentinel around half of the maximum, and keep a skip-check for unreachable pairs.

Basing “unreachable” checks on a zero instead of the infinity sentinel. Both Bellman-Ford and Dijkstra start distances at an infinity sentinel. Checking whether the target distance equals 0 instead of the sentinel marks reachable nodes as unreachable, and the target itself as distance 0. The failure shows only in disconnected graphs, which is exactly when interviews test it. Always compare against the sentinel you initialized with.

Related Patterns

• Graph Traversal . BFS and DFS are the foundation every shortest path algorithm sits on. The graph-traversal page covers visited tracking and component counting, which you use before you ever pick a weighted algorithm.
• Heap / Priority Queue . Dijkstra is a priority queue doing the work of an interview. Each relaxation pushes a better distance, and the heap hands back the next node to confirm.
• Topological Sort . On a directed acyclic graph, shortest paths can be computed in linear time by processing nodes in topological order with plain DP. That variant beats Dijkstra whenever the graph is a DAG, and it is worth knowing because interviewers occasionally ask for it.

Next Steps

The concept is the theory half. The code templates turn the four algorithms into memorizable implementations in 6 languages, and the practice problems run you through the classic interview versions of each.