9.23 Shortest Path Fundamentals

Problem

You need to find the cheapest route between vertices.

Many graph applications revolve around finding paths:

• Driving directions between cities
• Network packet routing
• Flight planning
• Robot navigation
• Supply chain optimization
• Dependency analysis

The question is usually not:

Can I reach the destination?

but:

What is the best way to reach it?

The definition of "best" depends on the problem.

It may mean:

• Minimum distance
• Minimum cost
• Minimum time
• Minimum risk
• Minimum number of hops

You need a framework for reasoning about shortest-path problems.

Solution

Model the problem as a weighted graph and compute shortest paths.

A shortest path is a path whose total weight is minimal among all paths connecting two vertices.

Example:

A --5-- B
|       |
2       3
|       |
C --1-- D

Path:

A → B → D

costs:

5 + 3 = 8

Path:

A → C → D

costs:

2 + 1 = 3

The second path is shorter.

Discussion

Shortest-path problems appear so frequently that they form an entire family of algorithms.

Different algorithms solve different variations:

Problem	Typical Algorithm
Unweighted shortest path	BFS
Positive weights	Dijkstra
Negative weights allowed	Bellman-Ford
All pairs shortest paths	Floyd-Warshall
DAG shortest paths	Topological-order relaxation
Heuristic route finding	A*

Understanding the common concepts behind these algorithms is more important than memorizing individual implementations.

Weighted Graphs

Shortest-path problems typically use weighted graphs.

An edge weight represents cost.

Example:

graph = {
    "A": [
        ("B", 5),
        ("C", 2),
    ],
    "B": [
        ("D", 3),
    ],
    "C": [
        ("D", 1),
    ],
    "D": [],
}

Visualization:

A
|\\n5 2
|  \\nB   C
|   |
3   1
|   |
D

The weight may represent:

• Distance
• Time
• Money
• Energy
• Latency
• Probability cost

The algorithm treats all of these as abstract costs.

Path Cost

The cost of a path is the sum of its edge weights.

Example:

A → C → D

Cost:

2 + 1 = 3

Example:

A → B → D

Cost:

5 + 3 = 8

The smaller total determines the shorter path.

Notice that shortest paths optimize the total path cost, not individual edge costs.

A path may contain expensive edges if the overall route is cheaper.

Single-Source Shortest Paths

Many problems begin with one source vertex.

Example:

Find shortest paths from A to every vertex.

Output:

Vertex	Distance
A	0
B	5
C	2
D	3

This is called the Single-Source Shortest Path (SSSP) problem.

Dijkstra's algorithm and Bellman-Ford both solve variants of SSSP.

Single-Pair Shortest Paths

Sometimes only one destination matters.

Example:

Find shortest path from A to D.

Result:

A → C → D

Cost:

3

Many systems stop searching once the target is reached.

Route planners frequently use this optimization.

All-Pairs Shortest Paths

Sometimes every pair matters.

Example:

Distance(A, B)
Distance(A, C)
Distance(B, D)
Distance(C, D)
...

Output becomes a distance matrix.

From	To	Cost
A	B	5
A	C	2
A	D	3
B	D	3

This is called the All-Pairs Shortest Path (APSP) problem.

Floyd-Warshall is one of the classical solutions.

Unweighted Graphs

When every edge has the same cost, weights become unnecessary.

Example:

A -- B -- D
 \\n  \\n   C -- D

Distance is measured in edges.

Shortest path:

A → C → D

Length:

2

BFS automatically finds shortest paths in unweighted graphs.

This is one of the most important BFS properties.

Recipe: Unweighted Shortest Path

from collections import deque

def shortest_path(graph, start):
    distance = {
        start: 0
    }

    queue = deque([start])

    while queue:
        vertex = queue.popleft()

        for neighbor in graph[vertex]:
            if neighbor not in distance:
                distance[neighbor] = (
                    distance[vertex] + 1
                )

                queue.append(neighbor)

    return distance

This algorithm runs in:

O(V + E)

time.

Path Reconstruction

Distances alone are often insufficient.

Users usually want the actual route.

Store a predecessor.

parent = {
    start: None
}

Whenever a shorter path is discovered:

parent[neighbor] = vertex

After the search finishes:

Destination
↓
Parent
↓
Parent
↓
Source

Walking backward reconstructs the route.

This technique appears in nearly every shortest-path algorithm.

Recipe: Reconstruct a Path

def reconstruct(parent, target):
    path = []

    current = target

    while current is not None:
        path.append(current)
        current = parent[current]

    path.reverse()

    return path

Example:

parent = {
    "A": None,
    "C": "A",
    "D": "C",
}

Result:

[
    "A",
    "C",
    "D"
]

Relaxation

Relaxation is the central operation in shortest-path algorithms.

Suppose:

distance[A] = 2

and edge:

A → B

has weight:

5

Then:

candidate = 2 + 5 = 7

If:

7 < distance[B]

update:

distance[B] = 7

This process is called relaxation.

Pseudo-code:

if distance[u] + weight < distance[v]:
    distance[v] = (
        distance[u] + weight
    )

Nearly every shortest-path algorithm consists primarily of repeated relaxation.

Distance Initialization

A common pattern is:

distance = {
    vertex: float("inf")
    for vertex in graph
}

distance[start] = 0

Initially:

Unknown distance = infinity

Source distance:

0

Relaxation gradually replaces infinity with actual path costs.

This initialization appears in Dijkstra, Bellman-Ford, Floyd-Warshall, and many related algorithms.

Positive and Negative Weights

Positive weights:

5
2
7
1

Negative weights:

-3
-5

Example:

A --2--> B
B ---5--> C

Path cost:

2 + (-5) = -3

Negative weights are legal in many shortest-path formulations.

However, some algorithms assume nonnegative weights.

Dijkstra's algorithm requires:

weight ≥ 0

Bellman-Ford handles negative weights correctly.

Negative Cycles

Consider:

A → B (1)
B → C (-3)
C → A (1)

Cycle cost:

1 + (-3) + 1 = -1

Each traversal reduces path cost.

Repeat forever:

-1
-2
-3
-4
...

No shortest path exists.

The cost can decrease without bound.

This structure is called a negative cycle.

Shortest-path algorithms must either detect negative cycles or assume they do not exist.

Shortest Path Trees

Single-source algorithms often produce a shortest-path tree.

Example:

A
|\\n| \\nC  B
|
D

Every vertex stores its predecessor.

The resulting tree contains:

One shortest path
from source
to every vertex

This differs from a minimum spanning tree.

A shortest-path tree minimizes path lengths from a source.

An MST minimizes total tree weight.

These objectives are not the same.

Common Applications

Navigation Systems

Vertices:

Intersections

Edges:

Roads

Weight:

Travel time

Network Routing

Vertices:

Routers

Edges:

Links

Weight:

Latency

Logistics

Vertices:

Warehouses

Edges:

Transportation routes

Weight:

Shipping cost

Game Development

Vertices:

Map locations

Edges:

Movement options

Weight:

Movement cost

Choosing the Right Algorithm

A useful decision table:

Graph Type	Recommended Algorithm
Unweighted	BFS
Positive weights	Dijkstra
Negative weights	Bellman-Ford
DAG	Topological shortest path
All pairs	Floyd-Warshall
Heuristic search	A*

This classification appears repeatedly in graph engineering.

Complexity Overview

Algorithm	Complexity
BFS	O(V + E)
Dijkstra (heap)	O((V + E) log V)
Bellman-Ford	O(VE)
Floyd-Warshall	O(V³)
DAG shortest path	O(V + E)

Different graph structures justify different algorithms.

There is no single shortest-path algorithm that dominates every scenario.

Common Pitfalls

Do not use BFS on weighted graphs.

Do not use Dijkstra when negative weights exist.

Do not confuse shortest-path trees with minimum spanning trees.

Do not ignore path reconstruction if actual routes are required.

Do not forget negative-cycle detection when negative weights are present.

Do not assume the shortest path contains the fewest edges.

A path with more edges may have lower total cost.

Takeaway

Shortest-path problems seek minimum-cost routes through a graph. The core concepts are path cost, distance estimates, predecessor tracking, and edge relaxation. Different graph properties lead to different algorithms, from BFS for unweighted graphs to Dijkstra, Bellman-Ford, Floyd-Warshall, and A*. Understanding these fundamentals provides the foundation for the shortest-path algorithms that follow in the next sections.