If anyone has some insight on how to do this it would be very much appreciated.
Floyd's algorithm for the shortest paths....challenging
-
0I'm wo$n$dering, 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. – 2011-03-17
1 Answers
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.
-
0very nice answer – 2011-03-17