The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm
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!