# Shortest Paths Graph Algorithms

This chapter is from the book

## 21.3 All-Pairs Shortest Paths

In this section, we consider two classes that solve the all-pairs shortest-paths problem. The algorithms that we implement directly generalize two basic algorithms that we considered in Section 19.3 for the transitive-closure problem. The first method is to run Dijkstra's algorithm from each vertex to get the shortest paths from that vertex to each of the others. If we implement the priority queue with a heap, the worst-case running time for this approach is proportional to VE lg V, and we can improve this bound to VE for many types of networks by using a d-ary heap. The second method, which allows us to solve the problem directly in time proportional to V3, is an extension of Warshall's algorithm that is known as Floyd's algorithm.

Both of these classes implement an abstract–shortest-paths ADT interface for finding shortest distances and paths. This interface, which is shown in Program 21.2, is a generalization to weighted digraphs of the abstract–transitive-closure interface for connectivity queries in digraphs that we studied in Chapter 19. In both class implementations, the constructor solves the all-pairs shortest-paths problem and saves the result in private data fields to support query methods that return the shortest-path length from one given vertex to another and either the first or last edge on the path. Implementing such an ADT is a primary reason to use all-pairs shortest-paths algorithms in practice.

Program 21.3 is a sample client program that uses the all-pairs shortest-paths ADT interface to find the weighted diameter of a network. It checks all pairs of vertices to find the one for which the shortest-path length is longest; then, it traverses the path, edge by edge. Figure 21.13 shows the path computed by this program for our Euclidean network example.

Figure 21.13. Diameter of a network

The goal of the algorithms in this section is to support constant-time implementations of the query methods. Typically, we expect to have a huge number of such requests, so we are willing to invest substantial resources in private data fields and preprocessing in the constructor to be able to answer the queries quickly. Both of the algorithms that we consider use space proportional to V2 for the private data fields.

The primary disadvantage of this general approach is that, for a huge network, we may not have so much space available (or we might not be able to afford the requisite preprocessing time). In principle, our interface provides us with the latitude to trade off preprocessing time and space for query time. If we expect only a few queries, we can do no preprocessing and simply run a single-source algorithm for each query, but intermediate situations require more advanced algorithms (see Exercises 21.48 through 21.50). This problem generalizes one that challenged us for much of Chapter 19: the problem of supporting fast reachability queries in limited space.

## Program 21.2 All-pairs shortest-paths ADT

Our solutions to the all-pairs shortest-paths problem are all classes with a constructor and two query methods: a dist method that returns the length of the shortest path from the first given vertex to the second; and one of two possible path methods, either path, which returns a reference to the first edge on the shortest path, or pathR, which returns a reference to the final edge on the shortest path. If there is no such path, the path method returns 0 and dist is undefined.

We use path or pathR as convenient for the algorithm under scrutiny; in practice, we might need to settle upon one or the other (or both) in the interface and use various transfer functions in implementations, as discussed in Section 21.1 and in the exercises at the end of this section.

```class GraphSPall // ADT interface
{ // implementations and private members hidden
GraphSPall(GRAPH G)
Edge path(int, int)
Edge pathR(int, int)
double dist(int, int)
}
```

The first all-pairs shortest-paths ADT method implementation that we consider solves the problem by using Dijkstra's algorithm to solve the single-source problem for each vertex. In Java, we can express the method directly, as shown in Program 21.4: We build an array of GraphSPT objects, one to solve the single-source problem for each vertex. This method generalizes the BFS-based method for unweighted undirected graphs that we considered in Section 17.7. It is also similar to our use of a DFS that starts at each vertex to compute the transitive closure of unweighted digraphs, in Program 19.4.

## Program 21.3 Computing the diameter of a network

This client illustrates the use of the interface in Program 21.2. It finds the longest of the shortest paths in the given network, prints the path, and returns its weight (the diameter of the network).

```static double diameter(Graph G)
{ int vmax = 0, wmax = 0;
GraphSPall all = new GraphSPall(G);
for (int v = 0; v < G.V(); v++)
for (int w = 0; w < G.V(); w++)
if (all.path(v, w) != null)
if (all.dist(v, w) > all.dist(vmax, wmax))
{ vmax = v; wmax = w; }
int v = vmax; Out.print(v + "");
while (v != wmax)
{ v = all.path(v, wmax).w(); Out.print("-" + v); }
return all.dist(vmax, wmax);
}
```

With Dijkstra's algorithm, we can find all shortest paths in a network that has nonnegative weights in time proportional to VE logd V, where d = 2 if E < 2 V, and d = E/V otherwise.

Proof: Immediate from Property 21.6. ▪

As are our bounds for the single-source shortest-paths and the MST problems, this bound is conservative; a running time of VE is likely for typical graphs.

To compare this implementation with others, it is useful to study the matrices implicit in the array-of-arrays structure of the private data fields. The wt arrays form precisely the distances matrix that we considered in Section 21.1: The entry in row s and column t is the length of the shortest path from s to t. As illustrated in Figures 21.8 and 21.9, the spt arrays form the transpose of the paths matrix: The entry in row s and column t is the last entry on the shortest path from s to t.

For dense graphs, we could use an adjacency-matrix representation and avoid computing the reverse graph by implicitly transposing the matrix (interchanging the row and column indices), as in Program 19.7. Developing an implementation along these lines is an interesting programming exercise and leads to a compact implementation (see Exercise 21.43); however, a different approach, which we consider next, admits an even more compact implementation.

## Program 21.4 Dijkstra's algorithm for all shortest paths

This class uses Dijkstra's algorithm to build an SPT for each vertex so that it can answer pathR and dist queries for any pair of vertices.

```class GraphSPall
{ private GraphSPT[] A;
GraphSPall(Graph G)
{
A = new GraphSPT[G.V()];
for (int v = 0; v < G.V(); v++)
A[v] = new GraphSPT(G, v);
}
Edge pathR(int s, int t)
{ return A[s].pathR(t); }
double dist(int s, int t)
{ return A[s].dist(t); }
}
```

The method of choice for solving the all-pairs shortest-paths problem in dense graphs, which was developed by R. Floyd, is precisely the same as Warshall's method, except that instead of using the logical or operation to keep track of the existence of paths, it checks distances for each edge to determine whether that edge is part of a new shorter path. Indeed, as we have noted, Floyd's and Warshall's algorithms are identical in the proper abstract setting (see Sections 19.3 and 21.1).

Program 21.5 is an all-pairs shortest-paths ADT implementation that uses Floyd's algorithm. It explictly uses the matrices from Section 21.1 as private data fields: a V-by-V array of arrays d for the distances matrix, and another V-by-V array of arrays p for the paths table. For every pair of vertices s and t, the constructor sets d[s][t] to the shortest-path length from s to t (to be returned by the dist method) and p[s][t] to the index of the next vertex on the shortest path from s to t (to be returned by the path method). The implementation is based upon the path relaxation operation that we considered in Section 21.1.

## Program 21.5 Floyd's algorithm for all shortest paths

This implementation of the interface in Program 21.2 uses Floyd's algorithm, a generalization of Warshall's algorithm (see Program 19.3) that finds the shortest paths between each pair of points instead of just testing for their existence.

After initializing the distances and paths matrices with the graph's edges, we do a series of relaxation operations to compute the shortest paths. The algorithm is simple to implement, but verifying that it computes the shortest paths is more complicated (see text).

```class GraphSPall
{ private Edge[][] p;
private double[][] d;
GraphSPall(Graph G)
{ int V = G.V();
p = new Edge[V][V]; d = new double[V][V];
for (int s = 0; s < V; s++)
for (int t = 0; t < V; t++)
d[s][t] = maxWT;
for (int s = 0; s < V; s++)
for (int t = 0; t < V; t++)
if (G.edge(s, t) != null)
{ p[s][t] = G.edge(s, t);
d[s][t] = G.edge(s, t).wt(); }
for (int s = 0; s < V; s++) d[s][s] = 0.0;
for (int i = 0; i < V; i++)
for (int s = 0; s < V; s++)
if (p[s][i] != null)
for (int t = 0; t < V; t++)
if (s != t)
if (d[s][t] > d[s][i] + d[i][t])
{ p[s][t] = p[s][i];
d[s][t] = d[s][i] + d[i][t]; }
}
Edge path(int s, int t)
{ return p[s][t]; }
double dist(int s, int t)
{ return d[s][t]; }
}
```

With Floyd's algorithm, we can find all shortest paths in a network in time proportional to V3.

Proof: The running time is immediate from inspection of the code. We prove that the algorithm is correct by induction in precisely the same way as we did for Warshall's algorithm. The ith iteration of the loop computes a shortest path from s to t in the network that does not include any vertices with indices greater than i (except possibly the endpoints s and t). Assuming this fact to be true for the ith iteration of the loop, we prove it to be true for the (i+1)st iteration of the loop. A shortest path from s to t that does not include any vertices with indices greater than i+1 is either (i) a path from s to t that does not include any vertices with indices greater than i, of length d[s][t], that was found on a previous iteration of the loop, by the inductive hypothesis; or (ii) comprising a path from s to i and a path from i to t, neither of which includes any vertices with indices greater than i, in which case the inner loop sets d[s][t]. ▪

Figure 21.14 is a detailed trace of Floyd's algorithm on our sample network. If we convert each blank entry to 0 (to indicate the absence of an edge) and convert each nonblank entry to 1 (to indicate the presence of an edge), then these matrices describe the operation of Warshall's algorithm in precisely the same manner as we did in Figure 19.15. For Floyd's algorithm, the nonblank entries indicate more than the existence of a path; they give information about the shortest known path. An entry in the distance matrix has the length of the shortest known path connecting the vertices corresponding to the given row and column; the corresponding entry in the paths matrix gives the next vertex on that path. As the matrices become filled with nonblank entries, running Warshall's algorithm amounts to just double-checking that new paths connect pairs of vertices already known to be connected by a path; in contrast, Floyd's algorithm must compare (and update if necessary) each new path to see whether the new path leads to shorter paths.

Figure 21.14. Floyd's algorithm

Comparing the worst-case bounds on the running times of Dijkstra's and Floyd's algorithms, we can draw the same conclusion for these all-pairs shortest-paths algorithms as we did for the corresponding transitive-closure algorithms in Section 19.3. Running Dijkstra's algorithm on each vertex is clearly the method of choice for sparse networks, because the running time is close to VE. As density increases, Floyd's algorithm—which always takes time proportional to V3—becomes competitive (see Exercise 21.67); it is widely used because it is so simple to implement.

A more fundamental distinction between the algorithms, which we examine in detail in Section 21.7, is that Floyd's algorithm is effective in even those networks that have negative weights (provided that there are no negative cycles). As we noted in Section 21.2, Dijkstra's method does not necessarily find shortest paths in such graphs.

The classical solutions to the all-pairs shortest-paths problem that we have described presume that we have space available to hold the distances and paths matrices. Huge sparse graphs, where we cannot afford to have any V-by-V matrices, present another set of challenging and interesting problems. As we saw in Chapter 19, it is an open problem to reduce this space cost to be proportional to V while still supporting constant-time shortest-path-length queries. We found the analogous problem to be difficult even for the simpler reachability problem (where we are satisfied with learning in constant time whether there is any path connecting a given pair of vertices), so we cannot expect a simple solution for the all-pairs shortest-paths problem. Indeed, the number of different shortest path lengths is, in general, proportional to V2 even for sparse graphs. That value, in some sense, measures the amount of information that we need to process and perhaps indicates that when we do have restrictions on space, we must expect to spend more time on each query (see Exercises 21.48 through 21.50).

#### Exercises

• 21.39 Estimate, to within a factor of 10, the largest graph (measured by its number of vertices) that your computer and programming system could handle if you were to use Floyd's algorithm to compute all its shortest paths in 10 seconds.

• 21.40 Estimate, to within a factor of 10, the largest graph of density 10 (measured by its number of edges) that your computer and programming system could handle if you were to use Dijkstra's algorithm to compute all its shortest paths in 10 seconds.

• 21.41 Show, in the style of Figure 21.9, the result of using Dijkstra's algorithm to compute all shortest paths of the network defined in Exercise 21.1.

• 21.42 Show, in the style of Figure 21.14, the result of using Floyd's algorithm to compute all shortest paths of the network defined in Exercise 21.1.

• 21.43 Combine Program 20.6 and Program 21.4 to make an implementation of the all-pairs shortest-paths ADT interface (based on Dijkstra's algorithm) for dense networks that supports path queries but does not explicitly compute the reverse network. Do not define a separate method for the single-source solution—put the code from Program 20.6 directly in the inner loop, and put results directly in private data fields d and p like those in Program 21.5).

• 21.44 Run empirical tests, in the style of Table 20.2, to compare Dijkstra's algorithm (Program 21.4 and Exercise 21.43) and Floyd's algorithm (Program 21.5) for various networks (see Exercises 21.4–8).

• 21.45 Run empirical tests to determine the number of times that Floyd's and Dijkstra's algorithms update the values in the distances matrix for various networks (see Exercises 21.4–8).

• 21.46 Give a matrix in which the entry in row s and column t is equal to the number of different simple directed paths connecting s and t in Figure 21.1.

• 21.47 Implement a class whose constructor computes the path-count matrix that is described in Exercise 21.46 so that it can provide count queries through a query method in constant time.

• 21.48 Develop a class implementation of the abstract–shortest-paths ADT for sparse graphs that cuts the space cost to be proportional to V by increasing the query time to be proportional to V.

• 21.49 Develop a class implementation of the abstract–shortest-paths ADT for sparse graphs that uses substantially less than O(V2) space but supports queries in substantially less than O(V) time. Hint: Compute all shortest paths for a subset of the vertices.

• 21.50 Develop a class implementation of the abstract–shortest-paths ADT for sparse graphs that uses substantially less than O(V2) space and (using randomization) supports queries in constant expected time.

• 21.51 Develop a class implementation of the abstract–shortest-paths ADT that takes the lazy approach of using Dijkstra's algorithm to build the SPT (and associated distance array) for each vertex s the first time that the client issues a shortest-path query from s, then references the information on subsequent queries.

• 21.52 Modify the shortest-paths ADT and Dijkstra's algorithm to handle shortest-paths computations in networks that have weights on both vertices and edges. Do not rebuild the graph representation (the method described in Exercise 21.4); modify the code instead.

• 21.53 Build a small model of airline routes and connection times, perhaps based upon some flights that you have taken. Use your solution to Exercise 21.52 to compute the fastest way to get from one of the served destinations to another. Then test your program on real data (see Exercise 21.5).

### InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

## Overview

Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

## Collection and Use of Information

To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

### Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

### Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

### Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

### Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

### Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

### Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

### Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

## Other Collection and Use of Information

### Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

### Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

### Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

### Do Not Track

This site currently does not respond to Do Not Track signals.

## Security

Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

## Children

This site is not directed to children under the age of 13.

## Marketing

Pearson may send or direct marketing communications to users, provided that

• Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
• Such marketing is consistent with applicable law and Pearson's legal obligations.
• Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
• Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

## Correcting/Updating Personal Information

If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

## Choice/Opt-out

Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

## Sale of Personal Information

Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

## Supplemental Privacy Statement for California Residents

California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

## Sharing and Disclosure

Pearson may disclose personal information, as follows:

• As required by law.
• With the consent of the individual (or their parent, if the individual is a minor)
• In response to a subpoena, court order or legal process, to the extent permitted or required by law
• To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
• In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
• To investigate or address actual or suspected fraud or other illegal activities
• To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
• To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
• To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

## Links

This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

## Requests and Contact

Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

## Changes to this Privacy Notice

We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020