Mathematics.

graph algorithms

Shortest Path

Graph Theory20 minDifficulty4 out of 10

You should know: graph traversal

Overview

The shortest path problem asks for a path between two vertices in a graph such that the sum of the weights of its edges is minimized. When all edges have equal weight, BFS solves it directly; when edges carry different (non-negative) weights, Dijkstra's algorithm is the standard solution.

Interactive Graph

Explore how traversal finds paths through a graph

Loading visualization…

Formal Definition

Definition

Given a weighted graph with edge-weight function f, a path P = (v₁, v₂, …, vₙ) from v₁ to vₙ has total weight equal to the sum of its edge weights. The shortest path from v to v′ is a path minimizing this sum over all paths connecting them:

P=(v1,v2,…,vn)∈V×V×⋯×V,v1=v, vn=v′P = (v_1, v_2, \ldots, v_n) \in V \times V \times \cdots \times V,\quad v_1 = v,\ v_n = v'

A path from v to v′ as a sequence of vertices

w(P)=∑i=1n−1f(ei,i+1)w(P) = \sum_{i=1}^{n-1} f(e_{i,i+1})

Total weight of path P, summing the weight of each consecutive edge

d(v,v′)=min⁡Pw(P)d(v, v') = \min_{P} w(P)

The shortest-path distance — the minimum total weight over all paths from v to v′

Worked Examples

  1. Direct path A→B has weight 4.

    w(A→B)=4w(A \to B) = 4

  2. Path A→C→B has weight 1 + 1 = 2, which is shorter.

    w(A→C→B)=1+1=2w(A \to C \to B) = 1 + 1 = 2

  3. Compare: 2 < 4, so the indirect path is shorter.

    d(A,B)=min⁡(4,2)=2d(A,B) = \min(4, 2) = 2

Answer: Shortest path is A → C → B, with total weight 2.

Practice Problems

Difficulty 3/10

In an unweighted graph, why does BFS starting from vertex s always find the shortest path (fewest edges) from s to every other vertex?

Difficulty 5/10

A GPS app models a city as a weighted graph where edge weights are travel times (minutes). From home H the roads are: H→A = 4, H→B = 2, B→A = 1, A→C = 5, B→C = 8. Use Dijkstra's algorithm to find the fastest route from H to C and its time.

Difficulty 6/10

A logistics network has a 'rebate' edge with a NEGATIVE cost (a subsidy). Which algorithm should you use to find least-cost routes, and why not Dijkstra?

Difficulty 4/10

In a social network (unweighted friendship graph), you want the 'degrees of separation' between two users. Which algorithm is appropriate and what is its time complexity on a graph with V users and E friendships?

Quiz

Why does Dijkstra's algorithm require non-negative edge weights?
For an UNWEIGHTED graph, the simplest shortest-path algorithm is:
Which real-world system most directly relies on shortest-path algorithms?

Summary

  • The shortest path problem finds the minimum-total-weight path between two vertices in a graph.
  • For unweighted graphs, BFS directly gives shortest paths (minimum edge count).
  • For weighted graphs with non-negative weights, Dijkstra's algorithm is the standard solution.
  • Edsger Dijkstra published his namesake algorithm in 1959, and it remains the foundation of routing (e.g. internet protocols, GPS navigation).

References

  1. WebsiteWikipedia — Shortest path problem