Write 1 page response

CSC 240

Lab 10

Write a function named allPairsShortestPaths. This function expects a distance matrix (Table 10.1) for a graph as an argument. The function uses Floyd’s algorithm to modify this matrix (Table 10.2) so that it contains the shortest paths between any vertices that are connected by paths. Write a driver program to test the function on the graph shown in Figure 10.1.

Figure 10.1 Floyd’s Algorithm Floyd’s algorithm solves the all-pairs shortest-path problem. That is, for each vertex v in a graph, the algorithm finds the shortest path from vertex v to any other vertex w that is reachable from v. The following pseudocode is the algorithm: for i from 0 to n – 1 for r from 0 to n – 1 for c from 0 to n – 1 matrix[r][c] = min(matrix[r][c], matrix[r][i] + matrix[i][c]) Note: The min and + operations should be capable of managing an infinity(∞) value, since some of the matrix entries will have infinity(∞) as its distance. Floyd’s algorithm traverses the matrix and finds the minimum-distance path that connects any two vertices and replaces the value in each entry of the matrix associated with the two vertices as necessary. The

distance from a vertex to itself is 0. In some cases, there is no path between the two vertices.

So, the entry will remain infinity(∞). For our purposes we will use the “-“ string to represent infinity(∞). Implement the following functions to help facilitate the operations on string edges: addWithInfinity, isLessWithInfinity, minWithInfinity. Distance Matrix Initialized:

A B C D E F G

A 0 80 ∞ ∞ ∞ ∞ ∞

B 80 0 79 ∞ 153 ∞ ∞

C ∞ 79 0 78 ∞ 74 ∞

D ∞ ∞ 78 0 98 89 ∞

E ∞ 153 ∞ 98 0 67 ∞

F ∞ ∞ 74 89 67 0 67

G ∞ ∞ ∞ ∞ ∞ 67 0

Table 10.1

Distance Matrix Solution:

A B C D E F G

A 0 80 159 237 233 233 300

B 80 0 79 157 153 153 220

C 159 79 0 78 141 74 141

D 237 157 78 0 98 89 156

E 233 153 141 98 0 67 134

F 233 153 74 89 67 0 67

G 300 220 141 156 134 67 0

Table 10.2