1
$\begingroup$

The most common proof for Floyd-Warshall's algorithm is an induction proof on the outer-most loop, which says

$\delta^k(i,j)=\begin{cases} \min\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\} & \text{for}\,k\geq 1\\ w(i,j) & \text{for}\,k=0\,\text{(i.e., base case)}, \end{cases}$

where $d^k(i,j)$ is the shortest path from $i$ to $j$ using $k$. Here I present another proof using induction on the length of any shortest path. I have a feeling that the main idea of my proof is the same as above, but I'm not sure if it is correct (missing something important). Here is the proof below:

Proof. (induction on $l$, the lengths of all shortest paths between all pairs of vertices $x_i$ and $x_j$ in the graph)

Base case $l=1$: the shortest path between some pair of vertices $x_i$ and $x_j$ is exactly the edge $(x_i x_j)$. In this case, $d_{ik}+d_{kj}\geq d_{ij}=k((x_i x_j))$ for all $k$ by the fact that $(x_i x_j)$ is the shortest path. The algorithm will not change $d_{ij}$ in this case, so it is correct.

Now, suppose that the algorithm will correctly find the length of all shortest paths of length up to some $c$, and that the shortest path between some pair of vertices $x_i$ and $x_j$ is $(x_i x_{p_1} x_{p_2}\cdots x_{p_c} x_j)$, which has length $c+1$. Now, let $x_{p_m}$ be the vertex in the path that has the biggest index in the distance matrix, and consider the path divided into $(x_i\cdots x_{p_m}\cdots x_j)$; let $P_1=(x_i\cdots x_{p_m})$ and $P_2=(x_{p_m}\cdots x_j)$. For $P_1$, the algorithm will correctly find its length by the inductive hypothesis, since it is of length at most $c-1$ and it is the shortest path between $x_i$ and $x_{p_m}$; similarly the algorithm will correctly find the length of $P_2$, since it is of length at most $c-1$ and it is the shortest path between $x_{p_m}$ and $x_j$. The algorithm will correctly do the comparison $d_{i p_m}+d_{p_m j}<d_{ij}$ when $d_{i p_m}$ and $d_{p_m j}$ are the length of $P_1$ and $P_2$, respectively, and update $d_{ij}$ correctly. This is because $p_m$ has the biggest index in the matrix, meaning that the algorithm would have already correctly found the length of $P_1$ and $P_2$ and stored them in $d_{i p_m}$ and $d_{p_m j}$, since they share intermediate vertices of smaller index and therefore would have been found in previous iterations of the outer-most loop.

P.S. To clarify, this is for a homework problem (as these problems typically are), and I am asking this after the due date. Most large universities in the U.S. nowadays employs graders (I am one myself), which means that my alternate proof may or may not receive a careful look. My point is that I want to know whether I missed something in the proof.

$\endgroup$
1
$\begingroup$

Your effort towards a new kind of proof for Floyd-Warshall algorithm is appreciated.

On one hand, your proof is very well written. It cannot be said to be all wrong as apparently you have tried to avoid saying anything wrong.

On the other hand, I would not call you proof a proof that is different from the usual induction proof on the loop variable of the outer-most loop.

... $p_m$ has the biggest index in the matrix, meaning that the algorithm would have already correctly found the length of $P_1$ and $P_2$ and stored them in $d_{i_{p_m}}$ and $d_{p_{m_j}}$, since they share intermediate vertices of smaller index and therefore would have been found in previous iterations of the outer-most loop.

Take a moment to reflect. What you said above is basically the induction hypothesis in the usual induction proof on the loop variable of outer-most loop. That induction hypothesis can be viewed as a proposition that is even stronger than the final result of the Floyd-Warshall algorithm. Armed with that kind of knowledge, it is expected the correctness can be proved easily. In other words, it is not far fetched to say you just proved its correctness by admitting its correctness. Or, you just repeated the usual proof with some extra unnecessary logic.

There is another hidden flaw in your proof that is actually critical. Suppose there is a negative cycle in a connected graph. Floyd-Warshall algorithm handles that situation graciously. However, there is no shortest paths between any pairs of vertices in the graph, since given any path, you can always find another path that is shorter. So, your induction hypothesis becomes void in that case.

$\endgroup$
  • $\begingroup$ Right, negative cycles do invalidate my IH. I had a hunch feeling that my proof does use the original proof idea in some way, but I was just not sure. Thanks! $\endgroup$ – ydh28 Oct 24 '18 at 14:55
  • $\begingroup$ Welcome! It looks like you are a careful grader, anyway. $\endgroup$ – Apass.Jack Oct 24 '18 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.