Mastering Shortest Path Algorithms: Theory, Models, and Python NetworkX Example

Shortest Path Problem

In graph theory, the shortest path problem seeks the minimum‑cost path between a source and a destination in a weighted directed or undirected graph. Edge weights may represent distance, time, or cost, and the goal is to minimize the sum of weights along the path.

Mathematical Model

The problem can be formulated as a linear or integer linear program. Let x_{ij} be a binary variable indicating whether the edge from node i to node j is selected (1) or not (0). The objective is to minimize the total weight Σ w_{ij} x_{ij} subject to flow conservation constraints, with source and sink nodes defined.

Algorithms

Common shortest‑path algorithms include:

Dijkstra’s algorithm – a single‑source method that iteratively selects the nearest unvisited vertex.

Bellman‑Ford algorithm – a dynamic‑programming approach that handles negative edge weights and detects negative cycles.

Floyd‑Warshall algorithm – a dynamic‑programming method that computes shortest paths between all pairs of vertices, also supporting negative weights.

Case Study: City Flight Ticket Prices

Given a matrix of ticket prices among six cities, we compute the cheapest routes from city A to all others. Zero entries indicate no direct flight.

<code>import networkx as nx

# Define ticket price matrix
costs = [
    [0, 50, 0, 40, 25, 10],
    [50, 0, 15, 20, 0, 25],
    [0, 15, 0, 10, 20, 0],
    [40, 20, 10, 0, 10, 25],
    [25, 0, 20, 10, 0, 55],
    [10, 25, 0, 25, 55, 0]
]

# Build directed weighted graph
G = nx.DiGraph()
for i in range(len(costs)):
    for j in range(len(costs[0])):
        if costs[i][j] != 0:
            G.add_edge(chr(65+i), chr(65+j), weight=costs[i][j])

# Compute shortest paths and costs from A
shortest_path = nx.shortest_path(G, source='A', weight='weight')
shortest_path_cost = nx.shortest_path_length(G, source='A', weight='weight')
for dest, cost in shortest_path_cost.items():
    print(f"From A to {dest} cheapest path {shortest_path[dest]}, cost {cost} yuan")
</code>

Output:

<code>From A to A cheapest path ['A'], cost 0 yuan
From A to F cheapest path ['A', 'F'], cost 10 yuan
From A to E cheapest path ['A', 'E'], cost 25 yuan
From A to B cheapest path ['A', 'F', 'B'], cost 35 yuan
From A to D cheapest path ['A', 'F', 'D'], cost 35 yuan
From A to C cheapest path ['A', 'E', 'C'], cost 45 yuan
</code>

NetworkX shortest_path Function

The core function used is nx.shortest_path , which computes shortest paths in weighted graphs. Its signature is:

<code>nx.shortest_path(G, source=None, target=None, weight=None, method='dijkstra')</code>

Parameters:

G: the graph (directed or undirected).

source: starting node (default None for all nodes).

target: ending node (default None for all nodes).

weight: edge attribute name for weights (default None, meaning each edge weight is 1).

method: algorithm to use, default 'dijkstra'; alternatives include 'bellman-ford' and 'floyd-warshall'.

To obtain path lengths, use nx.shortest_path_length() . The example above demonstrates both functions.