3
$\begingroup$

In the Floyd-Warshall algorithm we have:

Let $d_{ij}^{(k)}$ be the weight of a shortest path from vertex $i$ to $j$ for which all intermediate vertices are in the set $\{1, 2, \cdots, k\}$ then

\begin{align*} &d_{ij}^{(k)}= \begin{cases} w_{ij} & \text{ if } k = 0 \\ \min\{d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\} & \text{ if } k > 0 \end{cases}\\ \end{align*}

In fact it considers whether $k$ is an intermediate vertex in the shortest path from $i$ to $j$ or not. If $k$ is an intermediate it selects $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ becuase it decomposes the shortest path to $i \stackrel{p_1}{\leadsto} k \stackrel{p_2}{\leadsto} j$ otherwise $d_{ij}^{(k-1)}$ since $k$ is not an intermediate vertex so it has no effect on the shortest path.

My problem is, For a given shortest path between $i$ and $j$, $k$ is an intermediate vertex or not and its existence is deduced from the structure of the graph not our decision. so we have no freedom to select or not to select the $k$, because if $k$ is an intermediate vertex so we must choose $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ and if not we must choose $d_{ij}^{(k-1)}$. But when in formula it takes $\min$ between two numbers, it sounds like that it has option to select any of them while based on the structure of the graph there is no option for us. I believe the formula must be

\begin{align*} &d_{ij}^{(k)}= \begin{cases} w_{ij} & \text{ if } k = 0 \\ d_{ij}^{(k-1)} & \text{ if } k > 0 \text{ and } k \notin \text{ intermediate}(p)\\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)} & \text{ if } k > 0 \text{ and } k \in \text{ intermediate}(p) \end{cases}\\ \end{align*}

$\endgroup$
4
$\begingroup$

In fact the algorithm determines whether the vertex $k$ is "intermediate" on the path from $i$ to $j$. If indeed $d_{ik}^{(k-1)} + d_{kj}^{(k-1)} < d_{ij}^{(k-1)} $ during the computation we know that (up to the first $k$ vertices) the vertex $k$ is needed to obtain a shorter path between $i$ and $j$.

So, in my opinion, the algorithm takes into account the structure of the graph!

$\endgroup$
  • $\begingroup$ thanks. If so, my formula at the bottom of the question should be right. is not it? $\endgroup$ – M a m a D Jan 2 '18 at 4:50
  • $\begingroup$ actually, I do not think it is true. One might have $d_{ik}^{(k-1)} + d_{kj}^{(k-1)} < d_{ij}^{(k-1)} $ even when $k$ is not on the path from $i$ to $j$, a later step might find an even better shortcut. And frankly, I do not think your formula has a good meaning. Floyd-Warshall does not know which path it tries to optimize, it computes all-pairs shortest path. A vertex that is internal for one $i,j$ pair is not internal for another pair. $\endgroup$ – Hendrik Jan Jan 2 '18 at 7:02
3
$\begingroup$

The Floyd–Warshall algorithm computes the weight of the shortest walk between any two vertices (a walk is defined like a path, but with repeated vertices allowed). Assuming all weights are positive, the shortest walk is always a path, since if a walk hits the same vertex twice, then we can remove the cycle to obtain a shorter walk.

$\endgroup$

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.