6.3 Shortest Path

When you visit a website like Google Maps or use your Smartphone to ask for directions from home to your Aunt’s house in Pasadena, you are usually looking for a shortest path between the two locations. These computer applications use representations of the street maps as graphs, with estimated driving times as edge weights.

While often it is possible to find a shortest path on a small graph by guess-and-check, our goal in this chapter is to develop methods to solve complex problems in a systematic way by following algorithms. An algorithm is a step-by-step procedure for solving a problem. Dijkstra’s (pronounced dike-stra) algorithm will find the shortest path between two vertices.

Example 1

Suppose you need to travel from Tacoma, WA (vertex T) to Yakima, WA (vertex Y). Looking at a map, it looks like driving through Auburn (A) then Mount Rainier (MR) might be shortest, but it’s not totally clear since that road is probably slower than taking the major highway through North Bend (NB). A graph with travel times in minutes is shown below. An alternate route through Eatonville (E) and Packwood (P) is also shown.

# Ch 6.3 - Dijkstra's algorithm, run the way the book runs it: label every
# vertex with its distance TO THE END, working backwards from the destination.
# Travel times in minutes around Mount Rainier.
W = {("T", "A"): 20, ("T", "E"): 57, ("A", "NB"): 36, ("A", "MR"): 79,
     ("E", "P"): 96, ("NB", "Y"): 104, ("MR", "P"): 27, ("MR", "Y"): 96,
     ("P", "Y"): 76}
START, END = "T", "Y"   # T=Tacoma A=Auburn E=Eatonville NB=North Bend
                        # MR=Mount Rainier P=Packwood Y=Yakima
# TRY IT: set START,END = "E","NB".  Or make the road A-NB slow (say 150)
# and watch the shortest route abandon the highway.

G = {}
for (u, v), w in W.items():
    G.setdefault(u, {})[v] = w
    G.setdefault(v, {})[u] = w

INF = float("inf")
dist = {v: INF for v in G}
prev = {v: None for v in G}
dist[END] = 0
visited = []
order = list(G)

print("Distances to " + END + " as the algorithm fills them in:")
print("step " + "".join(f"{v:>6}" for v in order) + "   current")
step = 0
while len(visited) < len(G):
    unvisited = [v for v in G if v not in visited]
    current = min(unvisited, key=lambda v: dist[v])
    if dist[current] == INF:
        break                        # whatever is left is unreachable
    row = "".join(f"{('-' if dist[v] == INF else int(dist[v])):>6}" for v in order)
    print(f"{step:>4} {row}   {current}")
    for nb, w in G[current].items():
        if nb not in visited and dist[current] + w < dist[nb]:
            dist[nb] = dist[current] + w
            prev[nb] = current
    visited.append(current)
    step += 1

if dist[START] == INF:
    print(f"\nthere is no route at all from {START} to {END}")
else:
    route, v = [START], START
    while prev[v] is not None:
        v = prev[v]
        route.append(v)
    legs = " + ".join(str(W.get((a, b), W.get((b, a)))) for a, b in zip(route, route[1:]))
    print(f"\nshortest {START} to {END}: {' - '.join(route)}")
    print(f"   {legs} = {int(dist[START])} minutes")
    if (START, END) == ("T", "Y"):
        print("compare: the scenic guess T-A-MR-Y costs "
              f"{W[('T','A')] + W[('A','MR')] + W[('MR','Y')]} minutes, and the")
        print("highway guess T-A-NB-Y is the one Dijkstra actually confirms.")

Adjacency Table

Adjacency table with travel time in minutes between cities
	T	A	E	NB	MR	P	Y
T		20	57
A	20			36	79
E	57					96
NB		36					104
MR		79				27	96
P			96		27		76
Y				104	96	76

Show solution

Step 1: Mark the ending vertex with a distance of zero. The distances will be recorded in [brackets] after the vertex name.

Adjacency Table

In the adjacency table, we will record the distances in the column headers

Adjacency table with travel time in minutes between cities
	T	A	E	NB	MR	P	Y [0]
T		20	57
A	20			36	79
E	57					96
NB		36					104
MR		79				27	96
P			96		27		76
Y				104	96	76

Step 2: For each vertex leading to Y, we calculate the distance to the end. For example, NB is a distance of 104 from the end, and MR is 96 from the end. Remember that distances in this case refer to the travel time in minutes.

Adjacency Table

Adjacency table with travel time in minutes between cities
	T	A	E	NB [104]	MR [96]	P [76]	Y [0]
T		20	57
A	20			36	79
E	57					96
NB		36					104
MR		79				27	96
P			96		27		76
Y				104	96	76

Step 3 & 4: We mark Y as visited, and mark the vertex with the smallest recorded distance as current. At this point, P will be designated current. Back to step 2.

Step 2 (#2): For each vertex leading to P (and not leading to a visited vertex) we find the distance from the end. Since E is 96 minutes from P, and we’ve already calculated P is 76 minutes from Y, we can compute that E is 96+76 = 172 minutes from Y.

If we make the same computation for MR, we’d calculate 76+27 = 103. Since this is larger than the previously recorded distance from Y to MR, we will not replace it.

Adjacency Table

Adjacency table with travel time in minutes between cities
	T	A	E [172]	NB [104]	MR [96]	P [76] current	Y [0] visited
T		20	57
A	20			36	79
E	57					96
NB		36					104
MR		79				27	96
P			96		27		76
Y				104	96	76

Step 3 & 4 (#2): We mark P as visited, and designate the vertex with the smallest recorded distance as current: MR. Back to step 2.

Step 2 (#3): For each vertex leading to MR (and not leading to a visited vertex) we find the distance to the end. The only vertex to be considered is A, since we’ve already visited Y and P. Adding MR’s distance 96 to the length from A to MR gives the distance 96+79 = 175 minutes from A to Y.

Adjacency Table

Adjacency table with travel time in minutes between cities
	T	A [175]	E [172]	NB [104]	MR [96] current	P [76] visited	Y [0] visited
T		20	57
A	20			36	79
E	57					96
NB		36					104
MR		79				27	96
P			96		27		76
Y				104	96	76

Step 3 & 4 (#3): We mark MR as visited, and designate the vertex with smallest recorded distance as current: NB. Back to step 2.

Step 2 (#4): For each vertex leading to NB, we find the distance to the end. We know the shortest distance from NB to Y is 104 and the distance from A to NB is 36, so the distance from A to Y through NB is 104+36 = 140. Since this distance is shorter than the previously calculated distance from Y to A through MR, we replace it.

Adjacency Table

Adjacency table with travel time in minutes between cities
	T	A [140]	E [172]	NB [104] current	MR [96] visited	P [76] visited	Y [0] visited
T		20	57
A	20			36	79
E	57					96
NB		36					104
MR		79				27	96
P			96		27		76
Y				104	96	76

Step 3 & 4 (#4): We mark NB as visited, and designate A as current, since it now has the shortest distance.

Step 2 (#5): T is the only non-visited vertex leading to A, so we calculate the distance from T to Y through A: 20+140 = 160 minutes.

Adjacency Table

Adjacency table with travel time in minutes between cities
	T [160]	A [140] current	E [172]	NB [104] visited	MR [96] visited	P [76] visited	Y [0] visited
T		20	57
A	20			36	79
E	57					96
NB		36					104
MR		79				27	96
P			96		27		76
Y				104	96	76

Step 3 & 4 (#5): We mark A as visited, and designate E as current.

Step 2 (#6): The only non-visited vertex leading to E is T. Calculating the distance from T to Y through E, we compute $172 + 57 = 229$ minutes. Since this is longer than the existing marked time, we do not replace it.

Step 3 (#6): We mark E as visited. Since all vertices have been visited, we are done.

From this, we know that the shortest path from Tacoma to Yakima will take 160 minutes. Tracking which sequence of edges yielded 160 minutes, we see the shortest path is T-A-NB-Y.

Dijkstra’s algorithm is an optimal algorithm, meaning that it always produces the actual shortest path, not just a path that is pretty short, provided one exists. This algorithm is also efficient, meaning that it can be implemented in a reasonable amount of time. Dijkstra’s algorithm takes around V² calculations, where V is the number of vertices in a graph[1]. A graph with 100 vertices would take around 10,000 calculations. While that would be a lot to do by hand, it is not a lot for computer to handle. It is because of this efficiency that your car’s GPS unit can compute driving directions in only a few seconds.

In contrast, an inefficient algorithm might try to list all possible paths then compute the length of each path. Trying to list all possible paths could easily take 10²⁵ calculations to compute the shortest path with only 25 vertices; that’s a 1 with 25 zeros after it! To put that in perspective, the fastest computer in the world would still spend over 1000 years analyzing all those paths.

Example 2

A shipping company needs to route a package from Washington, D.C. to San Diego, CA. To minimize costs, the package will first be sent to their processing center in Baltimore, MD then sent as part of mass shipments between their various processing centers, ending up in their processing center in Bakersfield, CA. From there it will be delivered in a small truck to San Diego.

The travel times, in hours, between their processing centers are shown in the table below. Three hours has been added to each travel time for processing.

Travel times adjacency table
	Baltimore	Denver	Dallas	Chicago	Atlanta	Bakersfield
Baltimore	*			15	14
Denver		*		18	24	19
Dallas			*	18	15	25
Chicago	15	18	18	*	14
Atlanta	14	24	15	14	*
Bakersfield		19	25			*

Find the shortest path from Baltimore to Bakersfield.

Show solution

While we could draw a graph, we can also work directly from the table.

Step 1: The ending vertex, Bakersfield, is marked as current.

Step 2: All cities connected to Bakersfield, in this case Denver and Dallas, have their distances calculated; we’ll mark those distances in the column headers.

Step 3 & 4: Mark Bakersfield as visited. Here, we are labeling it as such in the column header and putting a line through the corresponding row and column of the table as a quick visual indicator. We mark Denver as current, labeled as such in the column header, since it is the vertex with the shortest distance.

Travel times adjacency table
	Baltimore	Denver [19] current	Dallas [25]	Chicago	Atlanta	Bakersfield [0] visited
Baltimore	*			15	14
Denver		*		18	24	19
Dallas			*	18	15	25
Chicago	15	18	18	*	14
Atlanta	14	24	15	14	*
~~Bakersfield~~		19	25			*

Step 2 (#2): For cities connected to Denver, calculate distance to the end. For example, Chicago is 18 hours from Denver, and Denver is 19 hours from the end, the distance for Chicago to the end is 18+19 = 37 (Chicago to Denver to Bakersfield). Atlanta is 24 hours from Denver, so the distance to the end is 24+19 = 43 (Atlanta to Denver to Bakersfield).

Step 3 & 4 (#2): We mark Denver as visited and mark Dallas as current.

Travel times adjacency table
	Baltimore	Denver [19] visited	Dallas [25] current	Chicago [37]	Atlanta [43]	Bakersfield [0] visited
Baltimore	*			15	14
~~Denver~~		*		18	24	19
Dallas			*	18	15	25
Chicago	15	18	18	*	14
Atlanta	14	24	15	14	*
~~Bakersfield~~		19	25			*

Step 2 (#3): For cities connected to Dallas, calculate the distance to the end. For Chicago, the distance from Chicago to Dallas is 18 and from Dallas to the end is 25, so the distance from Chicago to the end through Dallas would be 18+25 = 43. Since this is longer than the currently marked distance for Chicago, we do not replace it. For Atlanta, we calculate 15+25 = 40. Since this is shorter than the currently marked distance for Atlanta, we replace the existing distance.

Step 3 & 4 (#3): We mark Dallas as visited, and mark Chicago as current.

Travel times adjacency table
	Baltimore	Denver [19] visited	Dallas [25] visited	Chicago [37] current	Atlanta [40]	Bakersfield [0] visited
Baltimore	*			15	14
~~Denver~~		*		18	24	19
~~Dallas~~			*	18	15	25
Chicago	15	18	18	*	14
Atlanta	14	24	15	14	*
~~Bakersfield~~		19	25			*

Step 2 (#4): Baltimore and Atlanta are the only non-visited cities connected to Chicago. For Baltimore, we calculate 15+37 = 52 and mark that distance. For Atlanta, we calculate 14+37 = 51. Since this is longer than the existing distance of 40 for Atlanta, we do not replace that distance.

Step 3 & 4 (#4): Mark Chicago as visited and Atlanta as current.

Travel times adjacency table
	Baltimore [52]	Denver [19] visited	Dallas [25] visited	Chicago [37] visited	Atlanta [40] current	Bakersfield [0] visited
Baltimore	*			15	14
~~Denver~~		*		18	24	19
~~Dallas~~			*	18	15	25
~~Chicago~~	15	18	18	*	14
Atlanta	14	24	15	14	*
~~Bakersfield~~		19	25			*

Step 2 (#5): The distance from Atlanta to Baltimore is 14. Adding that to the distance already calculated for Atlanta gives a total distance of 14+40 = 54 hours from Baltimore to Bakersfield through Atlanta. Since this is larger than the currently calculated distance, we do not replace the distance for Baltimore.

Step 3 & 4 (#5): We mark Atlanta as visited. All cities have been visited and we are done.

The shortest route from Baltimore to Bakersfield will take 52 hours, and will route through Chicago and Denver.

Your Turn

Try it Now 2

Find the shortest path between vertices A and G in the graph below.

Adjacency Table

Adjacency table with edge weights
	A	B	C	D	E	F	G
A	*	1	4
B	1	*		4	6
C	4		*	2		5
D		4	2	*	2	4
E		6		2	*	2	7
F			5	4	2	*	6
G					7	6	*

Answer

The shortest path is ABDEG, with length 13

[1] It can be made to run faster through various optimizations to the implementation.

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.