Algorithm Floyd-Uorshella finding the shortest paths between all pairs of vertices
Dan directed or undirected weighted graph with vertices. You want to find the values of all variables - the length of the shortest path from vertex to vertex .
It is assumed that the graph contains no cycles of negative weight (if the response between some pairs of vertices may not exist - it will be infinitely small).
This algorithm was simultaneously published in the article by Robert Floyd (Robert Floyd) and Steven Uorshella (Warshall) (Stephen Warshall) in 1962, on behalf of which the
algorithm is called now. However, in 1959, Bernard Roy (Bernard Roy) has published almost the same algorithm, but its publication went unnoticed.
Description of the algorithm
The key idea of the algorithm - the process of finding a partition of the shortest paths in the phase .
Before th phase ( ) is considered that the distances matrix stored length of the shortest paths, which contain as the only internal vertices of a plurality of
vertices (vertices we number from unity).
In other words, before th phase value equal to the length of the shortest path from vertex to vertex , if this path is allowed to go only in vertices with indices less than (the beginning and the end of the road do not count).
Easy to see that that this property holds for the first phase, it is sufficient in the distance matrix to record the adjacency matrix: - the cost of an edge from vertex to vertex . Thus, if between any vertex of not, write down the following values
"infinity" . From the vertex to itself, always record the value , it is critical for the algorithm.
Suppose now that we are on th phase, and we want to count the matrix so that it meets the requirements for the already -th phase. We fix some peaks and . We there are two fundamentally different cases:
• The shortest path from vertex to vertex , which is allowed to pass through an additional vertex , coincides with the shortest path, which is allowed to pass through the vertices of the set .
In this case, the value does not change when switching from th to -th phase.
• "New" was the shortest way better than the "old" way.
This means that the "new" shortest path passes through the top . Just note that we do not lose generality, further considering only simple paths (ie paths that do not pass on some vertex twice).
Then we note that if we will divide this "new" way of the apex into two halves (one running , and the other - ), each of these halves are no longer comes to the top . But then it turns out that the length of each of the halves was deemed more on th phase or even earlier, and it is sufficient to simply take the amount , it will give the length of the "new" shortest path.
Combining these two cases, we find that on th phase is required to recalculate the length of the shortest paths between all pairs of vertices , and as follows:
new_d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
Thus, all the work that is required to produce th phase - is to iterate over all pairs of vertices and recalculate the length of the shortest path between them. As a result, after the -th phase in the matrix of distances will be recorded between the length of the shortest path and , or , if paths between these nodes does not exist.
The last remark, which should be done - something that can not create a separate
matrix for the temporary matrix of shortest paths on th phase: all the changes you can make immediately in the matrix . In fact, if we have improved (reduced) some value in the matrix of distances, we could not degrading the length of the shortest path for any other pairs of vertices processed later.
Asymptotic algorithm obviously is .
Implementation
The input to the program served graph given in the form of adjacency matrix - a two- dimensional array size , in which each element specifies the length of the edge between the vertices.
It is required that for any . for (int k=0; k<n; ++k)
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
It is assumed that between two if some vertices are no ribs , the adjacency matrix was recorded some large number (large enough that it is greater than the length of any path in this graph); then this edge will always be profitable to take, and the algorithm works correctly.
However, if you do not take special measures, in the presence of edges in the graph of negative weight , in the resulting matrix can appear number of species ,
etc., which, of course, still means that between the corresponding vertices in general there is no way. Therefore, in the presence of negative edges in the graph algorithm Floyd's better to write so that it did not perform transitions from those states that already is "no way":
for (int k=0; k<n; ++k)
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
if (d[i][k] < INF && d[k][j] < INF)
d[i][j] = min (d[i][j], d[i][k] + d[k]
[j]);
Restoring themselves ways
Easy to maintain additional information - the so-called "ancestors" in which it will be possible to restore himself the shortest path between any two given vertices as a sequence of vertices .
It's enough apart distance matrix also support matrix ancestors that for every pair of vertices will contain a number of phases, which was obtained by the shortest distance between them. It is clear that the phase number is not more than the "average" top title of the shortest path, and now we just need to find the shortest path between the vertices and , and between and . This yields a simple recursive algorithm for the shortest path recovery.
The case of real weights
If the weight of the edges of the graph is not an integer, and real, we should take into account the errors that inevitably arise when dealing with floating-point types.
With regard to the algorithm Floyd unpleasant special effect of these errors become what distance algorithm results may take much minus because of accumulated errors . In fact, if the first phase error has occurred , then in the second iteration of this error may have in turn on the third - in , and so on.
To avoid this, the comparison algorithm Floyd should be done taking into account the error:
if (d[i][k] + d[k][j] < d[i][j] - EPS) d[i][j] = d[i][k] + d[k][j];
The case of negative cycles
If the graph has cycles of negative weight, then formally algorithm Floyd-Uorshella inapplicable to such a graph.
In fact, for those pairs of vertices and between which it is impossible to go into a cycle of negative weight, the algorithm will work correctly.
For those pairs of vertices, the answer to which does not exist (because of the presence of a negative cycle in the way between them), Floyd algorithm finds an answer in a certain number of (probably strongly negative, but not necessarily). Nevertheless, we can improve the algorithm Floyd that he carefully handle such pairs of vertices, and drew for them, for example .
This can be done, for example, the following criterion "is not the existence of the
way." Thus, even for a given graph has worked usual algorithm Floyd. Then between the tops and the shortest path does not exist, and then only if there exists a vertex accessible from and from which is achievable for which the following .
In addition, when using the Floyd algorithm for graphs with negative cycles should be remembered that arise in the process of distance can go into much less exponentially with each phase. Therefore, you should take action against integer overflow, limiting all distances from the bottom of any value (for example, ).
For more information about this task, see. A separate article: "Finding a negative cycle in the graph" .
Shortest path of fixed length, the number of tracks fixed length
The following describes the solutions of these two problems, built on the same idea: to reduce the problem to the construction of the power matrix (with the usual multiplication, and modified).
The number of paths of fixed length
Given a directed graph is unweighted with vertices, and contains an integer . Is required for each pair of vertices and the number of ways to find between these vertices consisting of exactly edges. Ways at the same time consider arbitrary, not necessarily simple (ie, the vertices can be repeated any number of times).
We assume that the graph is given adjacency matrix , ie, matrix size , where each element is equal to one if there is between the edge nodes, and zero if there is no edge. Described below, and the algorithm works in the case of multiple edges: if between some vertices and is at once the ribs, the adjacency matrix should record this
number . Also, the algorithm correctly takes into account the loops in the graph, if any.
Obviously, in this form, the adjacency matrix of the graph is the answer to the problem when - it contains a number of paths of length between each pair of vertices.
Solution will be constructed iteratively : let the answer for some is found, we show how to build it . Denoted by the matrix found answers to , and through - a matrix of responses you want to build. Then clear the following formula:
Easy to see that the above formulas - nothing but the product of two matrices and in the usual sense:
Thus, the solution of this problem can be represented as follows:
It remains to note that the construction of the matrix in the degree can be produced efficiently using the algorithm binary exponentiation .
Thus, the resulting solution has the asymptotic behavior and is in a binary construction of th degree of adjacency matrix of the graph.
Shortcuts fixed length
Given a directed weighted graph with vertices, and contains an integer . Is required for each pair of vertices , and find the length of the shortest path between the vertices of exactly edges.
We assume that the graph is given adjacency matrix , ie, matrix size , where each element contains the length of the edge from vertex to vertex . If between some vertices of the edge is not, then the corresponding element of the matrix is taken to be infinity .
Obviously, in this form, the adjacency matrix of the graph is the answer to the problem when - it contains the length of the shortest paths between each pair of vertices, or if the length of the path does not exist.
Solution will be constructed iteratively : let the answer for some is found, we show how to build it . Denoted by the matrix found answers to , and through - a matrix of responses you want to build. Then clear the following formula:
Take a good look at this formula, it is easy to draw an analogy with matrix multiplication: in fact, the matrix is multiplied by the matrix , only the operation of multiplication instead of the sum of all the minimum is taken over all :
where the operation of multiplication of two matrices is defined as follows:
Thus, the solution to this problem can be represented by this multiplication as follows:
It remains to note that exponentiation with this multiplication operation can be performed efficiently using the algorithm binary exponentiation , because the only required for a feature - associativity of multiplication - obviously there.
Thus, the resulting solution has the asymptotic behavior and is in a binary construction of th degree of adjacency matrix of a modified matrix multiplication.
Generalization to the case when the required path length, no more than a predetermined length
The above solutions solve problems when you need to consider the way a certain, fixed length. However, these solutions can be adapted to solve problems when you need to consider ways of containing not more than a specified number of edges.
You can do it, slightly modified input graph. For example, if we are interested only path ending in a particular vertex , the graph can add a loop of zero weight.
If we are still interested in the answers for all pairs of vertices, then simply adding loops to all vertices spoil the answer. Instead, you can bifurcate each node: for each vertex to create additional vertex , edge hold and add a loop .
Deciding on a modified graph the problem of finding ways of fixed length, the answers to the original problem will be obtained as the responses between the vertices and (ie,
additional peaks - it tops-end, in which we can "whirl" necessary number of times).