CMSC 435 Algorithm Analysis & Design

Floyd-Warshall All Pairs--Shortest Path Algorithm

Given a graph G = {V, E}, where |V| = n and G[n][n] is a matrix representation of G.

The entry G[i][j] is the "cost" of the edge from vertex i to vertex j, if it exists, else infinity.

Let M[n][n] be the matrix representing the lowest total cost between vertices. The

entries of M will be structures with two fields. The first field will be the minimum cost

between the vertices i and j, and the second field will be the intermediate vertex k that

lies on the least cost path between the two vertices.

Let m[i][j] be the minimum cost between vertices i and j, then

m[i][j] = min {m[i][k] + m[k][j]}

^k=1..n

and let M be the matrix that holds this minimum cost information.

Write a dynamic programming algorithm for the least-cost all pairs problem.

What are the initial values of M? {Hint! M should be initialized to indicate

the cost of all paths of length one between the vertices.}

The minimum cost information m[i][j]is stored in one of the fields of

the entries of M[i][j]. What is stored in the other field?

Find the minimum cost entries for M[i][j] by examining the path through

each of the intermediate vertices k in turn. {The program will consist of

nested for-loops.} What is the appropriate nesting of these loops?

Use the above information to write the Floyd-Warshall algorithm.