Skip to content

Shortest Path Problem

Definition

The course's shortest path problem is defined on a connected undirected network with nonnegative edge lengths, a specified origin, and a specified destination. It asks for a path between those vertices whose sum of edge lengths is minimum.

Interpretation

The shortest path problem asks for the best route between two given vertices of a network. The same formulation can minimize distance, travel time, fuel use, or any other route measure that adds up along the edges.

A weighted network from A to F with the shortest path from A to F, of length 13, highlighted.

The highlighted route A−C−B−D−E−FA-C-B-D-E-F has length 2+1+5+2+3=132+1+5+2+3=13. It uses five edges, while A−B−D−FA-B-D-F uses only three but has length 4+5+6=154+5+6=15: the shortest path is the one of smallest total length, not the one with the fewest edges, and it may make a detour through extra vertices.

Each part of the definition has a role. The origin and destination fix which paths are compared, and the objective adds the edge lengths along a path. A measure that is not a sum, such as the smallest capacity along a route, does not fit this form. The nonnegative lengths match distances and times, and they are what the shortest path algorithm relies on when it fixes the distances one vertex at a time.

Shortest paths are also building blocks: they supply the pair costs in the Chinese postman problem. A shortest path should not be confused with a minimum spanning tree, which minimizes the total length of a network connecting all vertices rather than the length of one route. Later in the course, the problem is also written as a binary program.

Key Results

  • The nonnegative-length assumption supports the course label-setting algorithm.
  • Several different paths can have the same minimum length.
  • The shortest-path tree from one origin and a minimum spanning tree solve different objectives.

Examples

In the figure, the red A−C−B−D−E−FA-C-B-D-E-F path has length 13. The alternatives A−B−D−FA-B-D-F, A−C−E−FA-C-E-F and A−C−D−FA-C-D-F have lengths 15, 15 and 16 respectively.

  • The worked route S-B-A-D-E-T has length 12.
  • In the CPP network, the shortest A-D route is A-C-D, of length 5, rather than the direct edge of length 6.

Prerequisites

Sources

Aliases: shortest route problem

Last updated: 20 October 2026 03:02