The Floyd-Warshall algorithm keeps track of path weights and vertex predecessors in arrays indexed in not just one dimension, but in three dimensions. You can think of a one-dimensional array as a table, just as we saw on page 11. A two-dimensional array would be like a matrix, such as the adjacency matrix on page 79; you need two indices 6 Named after Robert Floyd and Stephen Warshall. 107 108

Chapter 6: Shortest Paths (row and column) to identify an entry. dimensional array as a one-dimensional array in which each entry is itself a one-dimensional array. A three-dimensional array would be like a one-dimensional array of two-dimensional arrays; you need an index in each of the three dimensions to identify an entry. Well use commas to separate the dimensions when indexing into a multidimensional array. You can also think of a twoIn the Floyd-Warshall algorithm, we assume that the vertices are numbered from1 to n. Vertex numbers become important, because the Floyd-Warshall algorithm uses the following denition: shortestu; v; x(cid:2) is the weight of a shortest path from vertexu to vertex v in which each intermediate vertexa vertex on the path other thanu and vis numbered from 1 to x .

(So think of u, v, and x as integers in the range1 to n that represent vertices.) This denition does not require the intermediate vertices to consist of all x vertices numbered 1 to x ; it just requires each intermediate vertexhowever many there areto be numbered x or lower. Since all vertices are numbered at mostn, it must be the case thatshortestu; v; n(cid:2) equals sp.u; v/ , the weight of a shortest path fromu to v. Lets consider two vertices u and v, and pick a numberx in the range from 1 to n. Consider all paths fromu to v in which all intermediate vertices are numbered at mostx . Of all these paths, let pathp be one with minimum weight. Pathp either contains vertexx or it does not, and we know that, other than possiblyu or v, it does not contain any vertex numbered higher thanx . There are two possibilities:

First possibility: x is not an intermediate vertex in pathp . Then all intermediate vertices of pathp are numbered at mostx (cid:4) 1. What does this mean? It means that the weight of a shortest path fromu to v with all intermediate vertices numbered at mostx is the same as the weight of a shortest path fromu to v with all intermediate vertices numbered at most x (cid:4) equals shortestu; v; x (cid:4) 1(cid:2) . 1. In other words, shortestu; v; x(cid:2) Second possibility: x appears as an intermediate vertex in pathp . Because any subpath of a shortest path is itself a shortest path, the portion of path p that goes from u to x is a shortest path fromu to x . Likewise, the portion of p that goes from x to v is a shortest path from x to v. Because vertex x is an endpoint of each of these subpaths, it is not an intermediate vertex in either of them, and so