The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm

Question

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*}

Answer 1

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!

Answer 2

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.