The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm 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*}
&amp;d_{ij}^{(k)}= \begin{cases}
w_{ij} &amp; \text{ if } k = 0 \\
\min\{d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\} &amp; \text{ if } k &gt; 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*}
&amp;d_{ij}^{(k)}= \begin{cases}
w_{ij} &amp; \text{ if } k = 0 \\
d_{ij}^{(k-1)} &amp; \text{ if } k &gt; 0 \text{ and } k \notin \text{ intermediate}(p)\\
d_{ik}^{(k-1)} + d_{kj}^{(k-1)} &amp; \text{ if } k &gt; 0 \text{ and } k \in \text{ intermediate}(p)
\end{cases}\\
\end{align*}
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)} &lt; 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!