# Floyd's algorithm for the shortest paths…challenging

If anyone has some insight on how to do this it would be very much appreciated.

-
It looks like there is an algorithm given in the book. There is also a description at en.wikipedia.org/wiki/Floyd%27s_algorithm which seems clear enough but does not return the highest vertex used. It seems you could add that in as another index in the matrix path. What is your question? – Ross Millikan Mar 16 '11 at 21:33
Ross is right. The insight I can give you right now is to read the algorithm and execute it. If that's not enough, please explain why and we can work toward a formulation of your question we can help you answer. – leif Mar 16 '11 at 22:29
No worries, I eventually got it. Thanks for the responses – Trevor Arjeski Mar 16 '11 at 22:33
I'm wondering, was this for homework? Or what? It's a good concept to know about. But it is kind of a mess to actually calculate by hand. – Mitch Mar 17 '11 at 22:41

## 1 Answer

One way, as others have said, is to just follow the book.

But what the book probably says is: you'll have at the end for your answer seven 7x7 matrices, each entry in a matrix $A_{i, j}$ will be the pair (shortest path from $i$ to $j$, max labelled vertex on that path), the max or shortest known so far.

The first matrix will be about the paths that allow a path through $v_1$, the second paths through any of $v_1, v_2$, ..., the seventh through any of them. At the $k$th matrix you update all entries involving vertices up to $v_k$ using the formula most likely given in the book:

$$a_{ij} = a_{ij} + a_{ik}\cdot a_{kk}^{*} \cdot a_{kj}$$

where '$+$', '$*$', and even multiplication ('$\cdot$') have their special meanings for shortest paths and other special meanings for max vertex label, and the LHS is the new value (value in matrix $n+1$) and the RHS uses old values (values from matrix $n$. In practice you can do all this in-place in just one $n^2$ matrix).

The 0th matrix, the base case, where the paths don't go through any other vertex, is just for the edges. For shortest path, it is either the values of the edge weight, or $\infty$ if no edge because any finite value is less then/shorter than $\infty$).

The next exercise in the book will be to use the same method to convert a finite automaton into a regular expression. (Really!)

Extra commentary

• '+' is usually taken to mean 'or', min (to get the shortest or least), or max (to get the largest vertex label
• 'multiplication' (or '$\cdot$' is taken to mean 'plus' (to get the sum of weights along a path) or max again (yes, 'multiplication' is the same as 'addition' here)
• '*' is taken to mean 'for any number of cycles'. Since for both interpretations (shortest path, or max vertex label) a cycle isn't involved in any shortest path/max vertex, it can be ignored here.

The informative thing about this multiple interpretation, is that it is the first practical instance where abstract algebra (overloading of the interpretation of the +, $\cdot$, and *, but provable facts knowing only a few properties of those interpreted operations) in the CS curriculum.

-
very nice answer – Trevor Arjeski Mar 17 '11 at 15:53