What is the principle of floyd algorithm?

The principle of Floyd's algorithm is an algorithm that uses the idea of ​​dynamic programming to find the shortest path between multiple source points in a given weighted graph. It is similar to the Dijkstra algorithm. It is also an algorithm that uses the idea of ​​dynamic programming to find the shortest path between multiple source points in a given weighted graph. Algorithm for finding the shortest path in a weighted graph.

Floyd algorithm Also known as the interpolation method, it is a method that uses the idea of ​​dynamic programming to find multiple sources in a given weighted graph The algorithm for the shortest path between points is similar to Dijkstra's algorithm. The algorithm is named after Robert Floyd, one of the founders, winner of the 1978 Turing Award, and professor of computer science at Stanford University

In computer science, the Floyd-Warshall algorithm is a Algorithm for finding shortest paths in weighted graphs with positive or negative edge weights (but no negative periods). A single execution of the algorithm will find the length (weighted) of the shortest path between all pairs of vertices. Although it does not return details of the path itself, the path can be reconstructed with simple modifications to the algorithm. Versions of this algorithm can also be used to find the transitive closure of a relation R, or (related to the Schulze voting system) the widest path between all pairs of vertices in a weighted graph.

The Floyd-Warshall algorithm is an example of dynamic programming and was published in its currently accepted form by Robert Floyd in 1962. However, it is essentially the same algorithm for finding transitive closures of graphs published previously by Bernard Roy in 1959 and Stephen Warshall in 1962, and is closely related to Kleene's algorithm in 1956) for converting deterministic finite automata Convert to regular expression. The modern formulation of the algorithm as three nested for loops was first described by Peter Ingerman in 1962.

This algorithm is also called Floyd algorithm, Roy-Warshall algorithm, Roy-Floyd algorithm or WFI algorithm.

Core Idea Edit

1. Path Matrix

Find every two of a graph’s weight matrix Shortest path matrix between points.

Starting from the weighted adjacency matrix A=[a(i,j)] n×n of the graph, recursively perform n updates, that is, from the matrix D(0)=A, according to a formula, construct The matrix D(1) is obtained; and the same formula is used to construct D(2) from D(1);...; finally, the matrix D(n) is constructed from D(n-1) using the same formula. The elements in row i and column j of matrix D(n) are the shortest path length from vertex i to vertex j. D(n) is called the distance matrix of the graph. At the same time, a successor node matrix path can also be introduced to record the distance between two points. the shortest path.

Use relaxation technology (relaxation operation) to relax all other points between i and j. So the time complexity is O(n^3);

2. State transition equation

The state transition equation is as follows: map[i,j]:=min {map[i,k] map[k,j],map[i,j]};

map[i,j] represents the shortest distance from i to j, and K is the exhaustive list of i,j Breakpoint, the initial value of map[n,n] should be 0, or follow the meaning of the question.

Of course, if this road is not accessible, special processing must be performed, for example, there is no map[i,k] road.

Algorithm process editor

1, start from any unilateral path. The distance between all two points is the weight of the edge. If there is no edge connecting the two points, the weight is infinite.

2, for each pair of vertices u and v, see if there is a vertex w such that the path from u to w to v is shorter than the known path. If so update it.

Represent the graph as an adjacency matrix G. If there is a path from Vi to Vj, then G[i][j]=d, d represents the length of the path; otherwise G[i][j ] = infinity. Define a matrix D to record the information of the inserted point. D[i][j] represents the point that needs to be passed from Vi to Vj. Initialize D[i][j]=j. Insert each vertex into the graph and compare the distance after the insertion with the original distance, G[i][j] = min( G[i][j], G[i][k] G[k][j] ), if the value of G[i][j] becomes smaller, then D[i][j]=k. G contains the information of the shortest road between two points, while D contains the information of the shortest path.

For example, we want to find the path from V5 to V1. According to D, if D(5,1)=3, it means that the path from V5 to V1 passes through V3 is {V5,V3,V1}. If D(5,3)=3, it means that V5 and V3 are directly connected. If D (3,1)=1, indicating that V3 and V1 are directly connected.

Time complexity and space complexity editing

Time complexity: O(n^3);

Space complexity:O(n ^2)

Advantages and Disadvantages Analysis and Edit

Floyd algorithm is suitable for APSP (All Pairs Shortest Paths, multi-source shortest path). It is a dynamic programming algorithm, dense The graph has the best effect, and the edge weights can be positive or negative. This algorithm is simple and effective. Due to the compact triple loop structure, for dense graphs, the efficiency is higher than executing |V| times of Dijkstra's algorithm and higher than executing |V| times of SPFA algorithm.

Advantages: Easy to understand, can calculate the shortest distance between any two nodes, and the code is simple to write.

Disadvantages: The time complexity is relatively high and it is not suitable for calculating large amounts of data.

The above is the detailed content of What is the principle of floyd algorithm?. For more information, please follow other related articles on the PHP Chinese website!