Mastering Shortest Path Algorithms: From Dijkstra to A* with Real-World Example

1 Shortest Path Problem

Shortest path problem is a classic algorithmic problem in graph theory used to compute the shortest path between two vertices in a graph.

2 Common Shortest‑Path Algorithms

The typical algorithms for solving shortest‑path lengths are Dijkstra, Bellman‑Ford, Floyd, and the heuristic A* algorithm.

2.1 Dijkstra Algorithm

Dijkstra’s algorithm starts from the source, uses a greedy strategy to repeatedly visit the nearest unvisited vertex until the destination is reached.

Dijkstra can find the optimal weighted shortest path but cannot handle negative‑weight edges due to its greedy selection rule.

2.2 Bellman‑Ford Algorithm

Bellman‑Ford computes single‑source shortest paths in graphs that may contain negative‑weight edges.

Its efficiency is low; each iteration updates distances between all vertices, and the final shortest paths are known only after the algorithm terminates.

2.3 Floyd Algorithm

Floyd (also known as the insertion method) uses dynamic programming to solve the all‑pairs shortest‑path problem on weighted graphs. Starting from the weighted adjacency matrix, it recursively performs n updates to obtain the distance matrix and the predecessor matrix.

The advantage is that it can compute the shortest distance between any two nodes in one run, and it is more efficient than running Dijkstra V times on dense graphs.

Floyd can also handle negative‑weight edges.

2.4 A* Algorithm

A* is a heuristic algorithm that employs a best‑first search strategy, evaluating each position with an estimate function to prioritize the most promising nodes.

A* greatly reduces low‑quality search paths, offering high search efficiency, better real‑time performance and flexibility for large‑scale, time‑critical problems; however, it yields a relatively optimal path rather than an absolute shortest one.

2.5 Choosing a Shortest‑Path Algorithm

For arbitrary pairs of nodes, use Floyd.

For single‑source problems, use Bellman‑Ford when negative edges exist; otherwise use Dijkstra.

A* provides relatively optimal paths suitable for large‑scale, real‑time scenarios.

3 Case Study: City Ticket‑Price Problem

Given the ticket prices between six cities (∞ indicates no direct flight), find the cheapest routes and total costs from city A to all other cities. A value of 0 means no direct flight; a non‑zero value represents the price.

A  B  C  D  E  F
A   0 50  0 40 25 10
B  50  0 15 20  0 25
C   0 15  0 10 20  0
D  40 20 10  0 10 25
E  25  0 20 10  0 55
F  10 25  0 25 55  0

Using Python’s NetworkX library, the results are:

<code>City A to City A: route ['A'], total cost 0
City A to City B: route ['A', 'F', 'B'], total cost 35
City A to City C: route ['A', 'E', 'C'], total cost 45
City A to City D: route ['A', 'E', 'D'], total cost 35
City A to City E: route ['A', 'E'], total cost 25
City A to City F: route ['A', 'F'], total cost 10
</code>

4 Summary

This article used the city‑ticket pricing example to illustrate the concept and solution of shortest‑path problems.

References

youcans Python小白的数学建模课 https://www.zhihu.com/column/c_1381900867424075776