Shortest Paths

Shortest paths

Many real problems use shortest-path algorithms, including finding a fast metro journey. Stations are vertices, connections are edges, and weights may represent distance, time or cost.

Among all routes between two vertices in a network, the shortest path minimizes total edge weight. Its first vertex is the source and its last is the destination.

There are two types of problem:

1. Single source: find shortest paths from one fixed source to all other vertices.

2. All pairs: find shortest paths between every pair of vertices.

Single-source paths in an unweighted graph

An unweighted single-source shortest-path algorithm discovers distances in nondecreasing order, like breadth-first traversal.

For example, from source 3, vertices 1 and 6 have distance 1; vertices 2 and 4 distance 2; vertices 5 and 7 distance 3.

dist[v] stores the shortest distance from source S to v, with dist[S] = 0. path[v] stores the vertex immediately preceding v on the route.

Unweighted single-source shortest paths

unweightedSSSP(Vertex S)
    dist[S] = 0; dist[other vertices] = -1; path[*] = NULL
    enqueue(Q, S)
    while !isEmpty(Q)
        V = dequeue(Q)
        for v in neighbors(V)
            if dist[v] == -1
                dist[v] = dist[V] + 1
                path[v] = V
                enqueue(Q, v)

Single-source paths in a weighted graph

The shortest weighted route need not use the fewest edges. A reachable negative-cost cycle prevents a finite shortest distance for vertices reachable from that cycle: following it repeatedly reduces cost without bound.

Dijkstra's algorithm solves the single-source problem when every edge weight is nonnegative. It cannot be used directly with negative edges.

Dijkstra—what a name!

The algorithm continually updates a table of distances from the source. It uses a greedy choice: settle the unprocessed vertex with the smallest dist. Settling one vertex may improve another vertex's tentative distance.

For example, find shortest paths from A.

First initialize the table. The source A has value 0; all other vertices start at $\infty$ because no route is known.

Process A's neighbors: B is 5 units away and C is 2.

Settle the closest candidate C. Its edges to D and F give candidate distances $2+6=8$ and $2+8=10$.

Next settle B. Its edge to D improves D to $5+1=6$, below 8. Its edge to E gives $5+6=11$.

Settle D. Improve E to $6+1=7$ and F to $6+2=8$.

Settle E. The edge to G gives $7+7=14$.

Settle F. Improve G to $8+3=11$ rather than 14.

Finally the table contains shortest distances from A to all vertices.

All-pairs shortest paths

How can we compute the shortest distance between every pair of vertices?

One approach is to run Dijkstra once from every source.

This works for nonnegative weights, but is there a simpler algorithm?

Floyd–Warshall solves the all-pairs problem provided there is no negative cycle. Its idea is that a route between two vertices can become shorter by going through an intermediate vertex.

Let $D^k[i][j]$ be the minimum length of a route from i to j whose intermediate vertices are among those numbered at most k. Given $D^{k-1}$:

1. If the optimum does not use k, retain $D^{k-1}[i][j]$.

2. If it uses k, join the shortest i-to-k and k-to-j routes. Combine both cases by taking the minimum:

For example, a traveler wants to know the shortest road distances between every pair of cities before planning a trip.

A detour through a third city may shorten a route. Sometimes the best route needs two or more intermediate cities.

With no intermediate city permitted, the initial distances come from the adjacency matrix.

Allow city 1 as an intermediate:

Allow cities 1 and 2:

Allow cities 1, 2 and 3:

Finally allow every city:

Floyd shortest paths

floyd(Graph G)
    for k = 0 to G.vertexNum - 1
        for i = 0 to G.vertexNum - 1
            for j = 0 to G.vertexNum - 1
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])