The Floyd-Warshall algorithm is used on a directed graph with 4 vertices (labelled 1, 2, 3, 4). The initial shortest distances are given by an adjacency matrix where "inf" means infinity (no direct path).
The initial distances are:
- From 1 to 1 is 0, to 2 is 8, to 3 is inf, and to 4 is 1.
- From 2 to 1 is inf, to 2 is 0, to 3 is 1, and to 4 is inf.
- From 3 to 1 is 4, to 2 is inf, to 3 is 0, and to 4 is inf.
- From 4 to 1 is inf, to 2 is 2, to 3 is 9, and to 4 is 0.
The algorithm calculates the shortest paths by adding intermediate vertices one by one. What is the length of the shortest path from vertex 4 to vertex 1 after the algorithm has considered using vertices $\{1,2,3\}$ as intermediate points?
- $7$
- $9$
- $11$
- inf (infinity)
