FloydWarshall algorithm
The story behind this post
Recently I’ve received +10
karma on StackOverflow. I was curious for what question or answer and clicked to check this. It appeared
to be a sevenyearold answer about a FloydWarshall algorithm. I was surprised both of my bad English back those days and the very small value the answer had. So I’ve revised it and here it is – the brandnew version!
The definitions
Let us have a graph, described by matrix D
, where D[i][j]
is the length of the edge (i > j)
(from graph’s vertex with index i
to the vertex with index j
).
Matrix D
has the size of N * N
, where N
is a total number of vertices in a graph because we can reach the maximum of paths by connecting each graph’s vertex to each other.
Also, we’ll need matrix R
, where we will store shortest paths (R[i][j]
contains the index of a next vertex in the shortest path, starting at vertex i
and ending at vertex j
).
Matrix R
has the same size as D
.
The FloydWarshall algorithm performs these steps:

initialize the matrix of all the paths between any two pairs of vertices in a graph with the edge’s end vertex (this is important since this value will be used for path reconstruction)

for each pair of connected vertices (read: for each edge
(u > v)
),u
andv
, find the vertex, which forms shortest path between them: if the vertexk
defines two valid edges(u > k)
and(k > v)
(if they are present in the graph), which are together shorter than path(u > v)
, then assume the shortest path betweenu
andv
lies throughk
; set the shortest pivot point in matrixR
for edge(u > v)
to be the corresponding pivot point for edge(u > k)
But how do we read the matrix D
?
Inputs
Let us have a graph:
We first create a twodimensional array of size 4
(since there are exactly 4
vertices in our graph).
We initialize its main diagonal (the items, whose indices are equal, for ex. G[0, 0]
, G[1, 1]
, etc.) with zeros, because
the shortest path from vertex to itself has the length 0
and the other elements with a very large number (to indicate there is no edge or an infinitely long edge between them). The defined elements, corresponding to graph’s edges, we fill with edges’ lengths:
The algorithm itself
Now that we are on a same page with definitions, algorithm can be implemented like this:
After the algorithm run, the matrix R
will be filled with vertices’ indices, describing shortest paths between them.
Path reconstruction
In order to reconstruct the path from vertex u
to vertex v
, you need follow the elements of matrix R
:
Summary
The whole code could be wrapped in a couple of methods:
You can read ‘bout this algorithm on wikipedia and get some data structures generated automatically here