Shortest Paths in Weighted Graphs (Non-Negative Weights) - Shortest Path — Dijkstra's Algorithm | OneNoughtOne

Data Structures & AlgorithmsDijkstra's Algorithm

Shortest Path — Dijkstra's Algorithm

LevelIntermediate

Duration90 mins

TopicDijkstra's Algorithm

1 / 5

Shortest Paths in Weighted Graphs (Non-Negative Weights)

Beyond Counting Edges: The Weight of Real Paths

In the previous module, we discovered that Breadth-First Search (BFS) elegantly solves the shortest path problem in unweighted graphs. By exploring level by level, BFS guarantees that the first time we reach a vertex, we've found the shortest path to it—measured in the number of edges traversed.

But the real world is rarely so uniform. Roads have different lengths. Network connections have varying latencies. Flight routes have different costs. The edges in real-world graphs carry weights—numerical values representing distance, time, cost, or any quantifiable attribute.

When edges have weights, the problem transforms fundamentally. The path with fewer edges is no longer necessarily the shortest path. A scenic route through two highways might be shorter than cutting through five city blocks. And suddenly, BFS's level-by-level approach breaks down completely.

What You Will Learn

By the end of this page, you will understand: (1) Why weighted graphs require a different approach than BFS, (2) The formal definition of the weighted shortest path problem, (3) The key insight that makes solving this problem tractable, and (4) Why restricting to non-negative weights is crucial for efficient solutions.

The Failure of BFS on Weighted Graphs

Before we can appreciate the elegance of Dijkstra's algorithm, we must first understand why our go-to tool—BFS—fails spectacularly on weighted graphs. This isn't a subtle failure; it's a fundamental incompatibility.

Consider this simple graph:

        A -----(10)-----> B
        |                   |
       (1)                 (1)
        |                   |
        v                   v
        C -----(1)------> D
 
    Nodes: A, B, C, D
    Edges with weights:
      A → B : 10
      A → C : 1
      B → D : 1
      C → D : 1
    
    Question: What is the shortest path from A to D?

If we apply BFS from A:

Start at A (distance 0)
Explore neighbors: discover B and C (both at distance 1 in edges)
From B and C, explore neighbors: discover D from both
BFS reports: shortest path to D is 2 edges

What BFS tells us: A → B → D (2 edges) or A → C → D (2 edges) — both look equivalent!

What the actual shortest paths are:

A → B → D: weight = 10 + 1 = 11
A → C → D: weight = 1 + 1 = 2

The difference is stark: a factor of 5.5× in path weight! BFS returns the wrong answer because it optimizes for edge count, not total weight.

The Core Problem

BFS's guarantee—that the first discovery of a node yields the shortest path—only holds when all edges have equal weight. In weighted graphs, a path discovered later (with more edges) might actually be shorter (by total weight) than a path discovered earlier.

Why does BFS make this mistake?

BFS uses a standard queue (FIFO) to process vertices in the order they're discovered. The queue treats all edges as equivalent, processing vertices purely based on discovery order. But in weighted graphs:

An edge of weight 100 should not be treated the same as an edge of weight 1
A long detour through light edges might be better than one heavy edge
The optimal strategy must consider cumulative weight, not just hop count

This observation leads us to a crucial insight: we need a data structure that processes vertices not by discovery order, but by best-known distance.

Formal Problem Definition

Let's define the weighted shortest path problem with the precision required for algorithmic analysis. A clear problem statement is the foundation of a correct solution.

Definition — Weighted Graph:

A weighted graph G = (V, E, w) consists of:

V: A set of vertices (nodes)
E: A set of edges connecting vertices
w: A weight function w: E → ℝ that assigns a real number to each edge

The graph may be directed (edges have direction) or undirected (edges are bidirectional). For undirected graphs, each edge (u, v) implies both directions with the same weight.

Path Definition:
  A path P from vertex s to vertex t is a sequence of vertices:
  P = ⟨v₀, v₁, v₂, ..., vₖ⟩
  where v₀ = s, vₖ = t, and each (vᵢ, vᵢ₊₁) ∈ E
 
Path Weight:
  The weight of path P is the sum of its edge weights:
  w(P) = Σᵢ₌₀ᵏ⁻¹ w(vᵢ, vᵢ₊₁)
 
Shortest Path Weight:
  δ(s, t) = min { w(P) : P is a path from s to t }
  
  If no path exists from s to t, then δ(s, t) = ∞

The Single-Source Shortest Path (SSSP) Problem:

Given:

A weighted graph G = (V, E, w)
A designated source vertex s ∈ V

Find:

The shortest path weight δ(s, v) from s to every vertex v ∈ V
(Optionally) The actual paths that achieve these weights

This is the Single-Source Shortest Path problem—one source, all destinations. Dijkstra's algorithm solves this problem efficiently when all edge weights are non-negative.

Why Single-Source?

Solving shortest paths from one source to all destinations might seem like overkill if you only care about one destination. But remarkably, there's no known algorithm that finds the shortest path to one specific vertex faster than finding shortest paths to all vertices! The SSSP formulation matches the actual computational difficulty.

The Key Data Structure — Distance Estimates:

Every shortest path algorithm maintains a distance array (or map) that tracks the best-known distance from the source to each vertex:

dist[v] represents the shortest known path weight from s to v
Initially, dist[s] = 0 (we're already at the source)
Initially, dist[v] = ∞ for all other vertices (no path known)

As the algorithm progresses, these estimates are refined until they equal the true shortest path weights.

Distance Array Evolution
Stage	dist[B]	dist[C]	dist[D]	Status
Initial	∞	∞	∞	Only source known
After processing A	10	1	∞	Neighbors discovered
After processing C	10	1	2	Better paths found
After processing D	10	1	2	D finalized
After processing B	10	1	2	All finalized

The Non-Negative Weight Constraint

Dijkstra's algorithm requires that all edge weights are non-negative: w(e) ≥ 0 for every edge e ∈ E. This isn't an arbitrary restriction—it's fundamental to the algorithm's correctness. Understanding why reveals deep insights about shortest paths.

Why negative weights break greedy algorithms:

Consider a graph with a negative edge:

    A -----(5)-----> B
    |                  |
    |                  |
    +-----(2)-----> C -+
                       |
                     (-10)
                       |
                       v
                       B
 
    Edges:
      A → B : 5
      A → C : 2
      C → B : -10
    
    Direct path: A → B costs 5
    Detour path: A → C → B costs 2 + (-10) = -8
    
    The longer path is actually "shorter" in total weight!

The problem with negative edges:

Greedy decisions become unreliable: When we commit to a shortest path, a negative edge later might retroactively make another path shorter. We can't trust that any path is truly final.
Negative cycles create infinite descent: If a cycle has total negative weight, we can traverse it infinitely to get arbitrarily negative path weights. The shortest path is undefined (or -∞).
Monotonicity breaks: With non-negative edges, path weight can only increase as we add edges. With negative edges, paths can get "cheaper" as they get longer—breaking every intuition about progress.

Negative Cycles: The Ultimate Problem

A negative cycle is a cycle whose total edge weight is negative. If a graph contains a negative cycle reachable from the source, shortest paths are undefined—we could loop forever, driving the path weight to -∞. Dijkstra's algorithm cannot detect or handle this; it simply produces wrong answers.

The non-negative guarantee enables greedy finalization:

With non-negative edge weights, we gain a crucial property:

Monotonicity Principle: If we've found a path to vertex v with weight d, no extension of that path can produce a shorter path to v. Adding non-negative edges can only increase (or maintain) the total weight.

This means once we find the true shortest path to a vertex, we're done with that vertex forever. We can "finalize" it and never revisit it. This is the key insight that makes Dijkstra's algorithm efficient.

Comparison: Non-Negative vs Negative Weights
Property	Non-Negative Weights	Negative Weights
Path weight change	Can only increase	Can increase or decrease
Greedy finalization	Safe and optimal	Unsafe, may need revision
Shortest path existence	Always well-defined	May not exist (negative cycle)
Algorithm complexity	O((V+E) log V)	O(VE) with Bellman-Ford
Processing each vertex	Once	Up to V-1 times

Real-World Weighted Graph Problems

Weighted shortest path problems appear throughout computing and beyond. Understanding these applications provides intuition for why this problem is so important—and why the non-negative weight constraint is often naturally satisfied.

Navigation and Routing

•GPS Navigation: Find the shortest/fastest route between locations. Vertices are intersections; edges are road segments weighted by distance or travel time. Always non-negative.
•Network Routing (OSPF): Internet routers use Dijkstra's algorithm to find shortest paths for packet delivery. Edges weighted by latency, bandwidth, or hop count. Non-negative by definition.
•Flight Path Optimization: Finding cheapest or fastest flight itineraries. Graph of airports connected by routes with cost/time weights.
•Robot Path Planning: Navigate a robot from start to goal avoiding obstacles. Grid cells as vertices, movement costs as edge weights.

Network and Infrastructure

•Cable/Pipe Routing: Minimize construction cost for new utility lines. Terrain costs create the edge weights.
•Content Delivery Networks: Route requests to the nearest/fastest server. Network topology weighted by latency.
•Telecommunications: Find lowest-cost paths for call routing through a network of switches.
•Supply Chain Logistics: Optimize delivery routes considering fuel costs, tolls, and time.

Computer Science Applications

•Type Inference in Compilers: Finding shortest derivation paths in type lattices.
•Garbage Collection: Navigating object reference graphs with weighted constraints.
•Game AI Pathfinding: A* algorithm (Dijkstra with heuristics) for NPC movement.
•Currency Arbitrage Detection: Finding profitable trading cycles (negative cycles indicate arbitrage opportunities—this is where Bellman-Ford is needed instead!).

When Weights Are Naturally Non-Negative

Most physical quantities—distance, time, cost, fuel consumption—are inherently non-negative. You can't have negative distance or negative time. This is why Dijkstra's algorithm is so widely applicable: the real world provides its required constraint for free.

The Key Insight: Processing by Distance

We've established that BFS fails because it processes vertices by discovery order (FIFO), not by distance. The fix is conceptually simple: process vertices in order of their distance from the source.

The greedy insight:

Among all vertices whose shortest path we haven't finalized, the one with the smallest current distance estimate must actually have that as its true shortest path distance.

Why? Because to find a shorter path to it, we'd need to go through some other unfinalized vertex first—which would have an even larger distance estimate (since we picked the minimum). And with non-negative edge weights, going through that farther vertex can only make the path longer, not shorter.

Claim: Let u be an unfinalized vertex with minimum dist[u].
       Then dist[u] = δ(s, u), the true shortest path weight.
 
Proof intuition:
  - Any path to u must pass through either:
    (a) Only finalized vertices (whose distances are correct), or
    (b) At least one unfinalized vertex v before reaching u
    
  For case (a): We've already found the best such path; it's dist[u].
  
  For case (b): The path goes s → ... → v → ... → u
    - dist[v] ≥ dist[u]  (since we chose u as the minimum)
    - path s→v has weight ≥ dist[v] ≥ dist[u]
    - path v→u has weight ≥ 0 (non-negative edges)
    - total path ≥ dist[u]
    
  Either way, no path is shorter than dist[u]. ∎

This greedy insight is the heart of Dijkstra's algorithm. Each iteration:

Select the unfinalized vertex u with minimum dist[u]
Finalize u (we now know its true shortest path distance)
Relax all edges from u (potentially improving distances to neighbors)
Repeat until all vertices are finalized

The order of finalization produces vertices in non-decreasing order of their shortest path distances. It's as if we're "growing" a frontier of known shortest paths outward from the source.

BFS Approach

•Uses standard FIFO queue
•Processes by discovery order
•All edges treated equally
•Optimal for edge count only
•Cannot handle weights

Dijkstra Approach

•Uses priority queue (min-heap)
•Processes by distance order
•Respects edge weights
•Optimal for weighted paths
•Core insight for SSSP

The Priority Queue Connection

BFS uses a queue to enforce FIFO order. Dijkstra's algorithm uses a priority queue (min-heap) to enforce 'minimum distance first' order. This single data structure change transforms BFS from a hop-count optimizer into a weight optimizer. The rest of the algorithm remains remarkably similar.

From BFS to Dijkstra: The Conceptual Bridge

Understanding Dijkstra's algorithm becomes much easier if we see it as a generalization of BFS. Both algorithms share the same fundamental structure; they differ only in how they prioritize which vertex to process next.

The shared structure:

Both BFS and Dijkstra:

Start from a source vertex with distance 0
Maintain a frontier of discovered-but-not-finalized vertices
Repeatedly extract a vertex from the frontier, finalize it, and expand to neighbors
Track the best-known distance to each vertex

The key difference:

BFS: Frontier is a FIFO queue; extract the earliest-discovered vertex
Dijkstra: Frontier is a min-heap; extract the minimum-distance vertex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// BFS for unweighted shortest paths
function bfs(graph, source) {
    dist[source] = 0;
    queue.enqueue(source);           // FIFO queue
    
    while (!queue.isEmpty()) {
        u = queue.dequeue();         // Take earliest discovered
        
        for (v of graph.neighbors(u)) {
            if (dist[v] === Infinity) {
                dist[v] = dist[u] + 1;    // +1 hop
                queue.enqueue(v);
            }
        }
    }
}
 
// Dijkstra for weighted shortest paths
function dijkstra(graph, source) {
    dist[source] = 0;
    heap.insert(source, 0);          // Min-heap by distance
    
    while (!heap.isEmpty()) {
        u = heap.extractMin();       // Take minimum distance
        
        for (v of graph.neighbors(u)) {
            newDist = dist[u] + weight(u, v);  // +edge weight
            if (newDist < dist[v]) {
                dist[v] = newDist;
                heap.insert(v, newDist);  // or decrease-key
            }
        }
    }
}

The beautiful correspondence:

Notice that BFS is essentially Dijkstra's algorithm where all edge weights are 1! When every edge has weight 1:

The minimum-distance vertex is always one of the earliest-discovered at the current frontier
A FIFO queue naturally produces them in the right order
There's no need for a heap because discovery order matches distance order

BFS is Dijkstra's algorithm for the special case of uniform weights—optimized to avoid heap overhead by exploiting the structure of the problem.

Mental Model

Think of Dijkstra as 'BFS with weighted edges.' The algorithm 'grows' a frontier of known shortest paths outward from the source. The priority queue ensures we always expand the nearest unexplored vertex first, maintaining the invariant that finalized vertices have correct shortest path distances.

Historical Context: Dijkstra's Contribution

The algorithm bears the name of Edsger W. Dijkstra (1930–2002), one of the most influential computer scientists in history. Understanding the context of his contribution illuminates why this algorithm is so significant.

The 1956 invention:

Dijkstra invented the algorithm in 1956, reportedly in about twenty minutes while thinking about how to demonstrate the capabilities of a new computer called ARMAC. He wanted a problem that non-computer scientists could relate to, and choosing a routing problem (shortest path from Rotterdam to Groningen) fit perfectly.

The algorithm was published in 1959 in Numerische Mathematik, in a paper of remarkable brevity—just two and a half pages. Despite (or perhaps because of) its simplicity, it has become one of the most widely used algorithms in computer science.

Dijkstra's Own Words

"The question was: What is the shortest way to travel from Rotterdam to Groningen? I designed [the algorithm] in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path." — Edsger Dijkstra

Dijkstra's broader legacy:

Beyond this algorithm, Dijkstra made foundational contributions to:

Structured programming: Advocating against uncontrolled GOTO statements
Concurrent programming: The concept of semaphores for synchronization
Program verification: Contributions to formal methods and correctness proofs
Algorithm design: The shortest path algorithm, among others
Computing education: The influential "Notes on Structured Programming"

He received the Turing Award in 1972, computing's highest honor. His algorithm for shortest paths remains a testament to how clear thinking about a problem can yield solutions of lasting elegance and utility.

Why the algorithm endures:

Dijkstra's algorithm has survived for over six decades because:

It's provably correct: The mathematical foundations are solid
It's optimally efficient: No algorithm with the same constraints can do better
It's widely applicable: The non-negative weight constraint covers most practical cases
It's elegantly simple: The core idea fits in a few lines of code
It's extendable: Serves as the foundation for A*, which adds heuristics

Few algorithms in computer science have achieved such a combination of theoretical significance and practical utility.

Summary: Setting the Stage for Dijkstra

We've laid the groundwork for understanding one of the most important algorithms in computer science. Let's consolidate before diving into the implementation:

Key Takeaways

•BFS fails on weighted graphs — Edge count ≠ total weight. Level-by-level exploration doesn't account for varying edge weights.
•The SSSP problem is well-defined — Given a source, find shortest paths to all vertices, where 'shortest' means minimum total edge weight.
•Non-negative weights are essential — They guarantee that paths can only get longer (or stay same), enabling greedy finalization.
•The key insight: process by distance — Always finalize the unprocessed vertex with minimum distance estimate. This is provably optimal.
•Priority queue is the key data structure — A min-heap replaces BFS's FIFO queue, ordering by distance instead of discovery time.
•Dijkstra generalizes BFS — The structure is nearly identical; only the prioritization strategy changes.

What's next:

With the conceptual foundation established, we're ready to examine the algorithm's engine: the priority queue-based approach. The next page explores how a min-heap enables efficient extraction of minimum-distance vertices, the mechanics of the algorithm's main loop, and implementation details that separate correct from efficient solutions.

Page Complete

You now understand why weighted graphs require a different approach from BFS, why non-negative weights are crucial, and the key insight that processing vertices by distance enables greedy finalization. Next, we'll see how priority queues bring this insight to life.

1 / 5

Loading learning content...

Data Structures & AlgorithmsDijkstra's Algorithm

Shortest Path — Dijkstra's Algorithm

LevelIntermediate

Duration90 mins

TopicDijkstra's Algorithm

1 / 5

Shortest Paths in Weighted Graphs (Non-Negative Weights)

Beyond Counting Edges: The Weight of Real Paths

What You Will Learn

The Failure of BFS on Weighted Graphs

Consider this simple graph:

        A -----(10)-----> B
        |                   |
       (1)                 (1)
        |                   |
        v                   v
        C -----(1)------> D
 
    Nodes: A, B, C, D
    Edges with weights:
      A → B : 10
      A → C : 1
      B → D : 1
      C → D : 1
    
    Question: What is the shortest path from A to D?

If we apply BFS from A:

Start at A (distance 0)
Explore neighbors: discover B and C (both at distance 1 in edges)
From B and C, explore neighbors: discover D from both
BFS reports: shortest path to D is 2 edges

What BFS tells us: A → B → D (2 edges) or A → C → D (2 edges) — both look equivalent!

What the actual shortest paths are:

A → B → D: weight = 10 + 1 = 11
A → C → D: weight = 1 + 1 = 2

The difference is stark: a factor of 5.5× in path weight! BFS returns the wrong answer because it optimizes for edge count, not total weight.

The Core Problem

Why does BFS make this mistake?

An edge of weight 100 should not be treated the same as an edge of weight 1
A long detour through light edges might be better than one heavy edge
The optimal strategy must consider cumulative weight, not just hop count

This observation leads us to a crucial insight: we need a data structure that processes vertices not by discovery order, but by best-known distance.

Formal Problem Definition

Let's define the weighted shortest path problem with the precision required for algorithmic analysis. A clear problem statement is the foundation of a correct solution.

Definition — Weighted Graph:

A weighted graph G = (V, E, w) consists of:

V: A set of vertices (nodes)
E: A set of edges connecting vertices
w: A weight function w: E → ℝ that assigns a real number to each edge

The graph may be directed (edges have direction) or undirected (edges are bidirectional). For undirected graphs, each edge (u, v) implies both directions with the same weight.

Path Definition:
  A path P from vertex s to vertex t is a sequence of vertices:
  P = ⟨v₀, v₁, v₂, ..., vₖ⟩
  where v₀ = s, vₖ = t, and each (vᵢ, vᵢ₊₁) ∈ E
 
Path Weight:
  The weight of path P is the sum of its edge weights:
  w(P) = Σᵢ₌₀ᵏ⁻¹ w(vᵢ, vᵢ₊₁)
 
Shortest Path Weight:
  δ(s, t) = min { w(P) : P is a path from s to t }
  
  If no path exists from s to t, then δ(s, t) = ∞

The Single-Source Shortest Path (SSSP) Problem:

Given:

A weighted graph G = (V, E, w)
A designated source vertex s ∈ V

Find:

The shortest path weight δ(s, v) from s to every vertex v ∈ V
(Optionally) The actual paths that achieve these weights

This is the Single-Source Shortest Path problem—one source, all destinations. Dijkstra's algorithm solves this problem efficiently when all edge weights are non-negative.

Why Single-Source?

The Key Data Structure — Distance Estimates:

Every shortest path algorithm maintains a distance array (or map) that tracks the best-known distance from the source to each vertex:

dist[v] represents the shortest known path weight from s to v
Initially, dist[s] = 0 (we're already at the source)
Initially, dist[v] = ∞ for all other vertices (no path known)

As the algorithm progresses, these estimates are refined until they equal the true shortest path weights.

Distance Array Evolution
Stage	dist[B]	dist[C]	dist[D]	Status
Initial	∞	∞	∞	Only source known
After processing A	10	1	∞	Neighbors discovered
After processing C	10	1	2	Better paths found
After processing D	10	1	2	D finalized
After processing B	10	1	2	All finalized

The Non-Negative Weight Constraint

Why negative weights break greedy algorithms:

Consider a graph with a negative edge:

    A -----(5)-----> B
    |                  |
    |                  |
    +-----(2)-----> C -+
                       |
                     (-10)
                       |
                       v
                       B
 
    Edges:
      A → B : 5
      A → C : 2
      C → B : -10
    
    Direct path: A → B costs 5
    Detour path: A → C → B costs 2 + (-10) = -8
    
    The longer path is actually "shorter" in total weight!

The problem with negative edges:

Greedy decisions become unreliable: When we commit to a shortest path, a negative edge later might retroactively make another path shorter. We can't trust that any path is truly final.
Negative cycles create infinite descent: If a cycle has total negative weight, we can traverse it infinitely to get arbitrarily negative path weights. The shortest path is undefined (or -∞).
Monotonicity breaks: With non-negative edges, path weight can only increase as we add edges. With negative edges, paths can get "cheaper" as they get longer—breaking every intuition about progress.

Negative Cycles: The Ultimate Problem

The non-negative guarantee enables greedy finalization:

With non-negative edge weights, we gain a crucial property:

Monotonicity Principle: If we've found a path to vertex v with weight d, no extension of that path can produce a shorter path to v. Adding non-negative edges can only increase (or maintain) the total weight.

Comparison: Non-Negative vs Negative Weights
Property	Non-Negative Weights	Negative Weights
Path weight change	Can only increase	Can increase or decrease
Greedy finalization	Safe and optimal	Unsafe, may need revision
Shortest path existence	Always well-defined	May not exist (negative cycle)
Algorithm complexity	O((V+E) log V)	O(VE) with Bellman-Ford
Processing each vertex	Once	Up to V-1 times

Real-World Weighted Graph Problems

Navigation and Routing

•GPS Navigation: Find the shortest/fastest route between locations. Vertices are intersections; edges are road segments weighted by distance or travel time. Always non-negative.
•Network Routing (OSPF): Internet routers use Dijkstra's algorithm to find shortest paths for packet delivery. Edges weighted by latency, bandwidth, or hop count. Non-negative by definition.
•Flight Path Optimization: Finding cheapest or fastest flight itineraries. Graph of airports connected by routes with cost/time weights.
•Robot Path Planning: Navigate a robot from start to goal avoiding obstacles. Grid cells as vertices, movement costs as edge weights.

Network and Infrastructure

•Cable/Pipe Routing: Minimize construction cost for new utility lines. Terrain costs create the edge weights.
•Content Delivery Networks: Route requests to the nearest/fastest server. Network topology weighted by latency.
•Telecommunications: Find lowest-cost paths for call routing through a network of switches.
•Supply Chain Logistics: Optimize delivery routes considering fuel costs, tolls, and time.

Computer Science Applications

•Type Inference in Compilers: Finding shortest derivation paths in type lattices.
•Garbage Collection: Navigating object reference graphs with weighted constraints.
•Game AI Pathfinding: A* algorithm (Dijkstra with heuristics) for NPC movement.
•Currency Arbitrage Detection: Finding profitable trading cycles (negative cycles indicate arbitrage opportunities—this is where Bellman-Ford is needed instead!).

When Weights Are Naturally Non-Negative

The Key Insight: Processing by Distance

The greedy insight:

Among all vertices whose shortest path we haven't finalized, the one with the smallest current distance estimate must actually have that as its true shortest path distance.

Claim: Let u be an unfinalized vertex with minimum dist[u].
       Then dist[u] = δ(s, u), the true shortest path weight.
 
Proof intuition:
  - Any path to u must pass through either:
    (a) Only finalized vertices (whose distances are correct), or
    (b) At least one unfinalized vertex v before reaching u
    
  For case (a): We've already found the best such path; it's dist[u].
  
  For case (b): The path goes s → ... → v → ... → u
    - dist[v] ≥ dist[u]  (since we chose u as the minimum)
    - path s→v has weight ≥ dist[v] ≥ dist[u]
    - path v→u has weight ≥ 0 (non-negative edges)
    - total path ≥ dist[u]
    
  Either way, no path is shorter than dist[u]. ∎

This greedy insight is the heart of Dijkstra's algorithm. Each iteration:

Select the unfinalized vertex u with minimum dist[u]
Finalize u (we now know its true shortest path distance)
Relax all edges from u (potentially improving distances to neighbors)
Repeat until all vertices are finalized

The order of finalization produces vertices in non-decreasing order of their shortest path distances. It's as if we're "growing" a frontier of known shortest paths outward from the source.

BFS Approach

•Uses standard FIFO queue
•Processes by discovery order
•All edges treated equally
•Optimal for edge count only
•Cannot handle weights

Dijkstra Approach

•Uses priority queue (min-heap)
•Processes by distance order
•Respects edge weights
•Optimal for weighted paths
•Core insight for SSSP

The Priority Queue Connection

From BFS to Dijkstra: The Conceptual Bridge

The shared structure:

Both BFS and Dijkstra:

Start from a source vertex with distance 0
Maintain a frontier of discovered-but-not-finalized vertices
Repeatedly extract a vertex from the frontier, finalize it, and expand to neighbors
Track the best-known distance to each vertex

The key difference:

BFS: Frontier is a FIFO queue; extract the earliest-discovered vertex
Dijkstra: Frontier is a min-heap; extract the minimum-distance vertex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// BFS for unweighted shortest paths
function bfs(graph, source) {
    dist[source] = 0;
    queue.enqueue(source);           // FIFO queue
    
    while (!queue.isEmpty()) {
        u = queue.dequeue();         // Take earliest discovered
        
        for (v of graph.neighbors(u)) {
            if (dist[v] === Infinity) {
                dist[v] = dist[u] + 1;    // +1 hop
                queue.enqueue(v);
            }
        }
    }
}
 
// Dijkstra for weighted shortest paths
function dijkstra(graph, source) {
    dist[source] = 0;
    heap.insert(source, 0);          // Min-heap by distance
    
    while (!heap.isEmpty()) {
        u = heap.extractMin();       // Take minimum distance
        
        for (v of graph.neighbors(u)) {
            newDist = dist[u] + weight(u, v);  // +edge weight
            if (newDist < dist[v]) {
                dist[v] = newDist;
                heap.insert(v, newDist);  // or decrease-key
            }
        }
    }
}

The beautiful correspondence:

Notice that BFS is essentially Dijkstra's algorithm where all edge weights are 1! When every edge has weight 1:

The minimum-distance vertex is always one of the earliest-discovered at the current frontier
A FIFO queue naturally produces them in the right order
There's no need for a heap because discovery order matches distance order

BFS is Dijkstra's algorithm for the special case of uniform weights—optimized to avoid heap overhead by exploiting the structure of the problem.

Mental Model

Historical Context: Dijkstra's Contribution

The 1956 invention:

Dijkstra's Own Words

Dijkstra's broader legacy:

Beyond this algorithm, Dijkstra made foundational contributions to:

Structured programming: Advocating against uncontrolled GOTO statements
Concurrent programming: The concept of semaphores for synchronization
Program verification: Contributions to formal methods and correctness proofs
Algorithm design: The shortest path algorithm, among others
Computing education: The influential "Notes on Structured Programming"

Why the algorithm endures:

Dijkstra's algorithm has survived for over six decades because:

It's provably correct: The mathematical foundations are solid
It's optimally efficient: No algorithm with the same constraints can do better
It's widely applicable: The non-negative weight constraint covers most practical cases
It's elegantly simple: The core idea fits in a few lines of code
It's extendable: Serves as the foundation for A*, which adds heuristics

Few algorithms in computer science have achieved such a combination of theoretical significance and practical utility.

Summary: Setting the Stage for Dijkstra

We've laid the groundwork for understanding one of the most important algorithms in computer science. Let's consolidate before diving into the implementation:

Key Takeaways

•BFS fails on weighted graphs — Edge count ≠ total weight. Level-by-level exploration doesn't account for varying edge weights.
•The SSSP problem is well-defined — Given a source, find shortest paths to all vertices, where 'shortest' means minimum total edge weight.
•Non-negative weights are essential — They guarantee that paths can only get longer (or stay same), enabling greedy finalization.
•The key insight: process by distance — Always finalize the unprocessed vertex with minimum distance estimate. This is provably optimal.
•Priority queue is the key data structure — A min-heap replaces BFS's FIFO queue, ordering by distance instead of discovery time.
•Dijkstra generalizes BFS — The structure is nearly identical; only the prioritization strategy changes.

What's next:

Page Complete

1 / 5