preface
A new series, “Easy to Understand Data Structures and Algorithms by Looking at Pictures”, is launched, mainly using pictures to describe common data structures and algorithms, easy to read and understand. This series includes dozens of examples of heaps, queues, lists, trees, graphs, sorts, and more.
Floyd algorithm
Floyd is a classical multi-source shortest path algorithm, which uses the idea of dynamic programming to find the shortest path between multi-source points in a given weighted graph. The algorithm’s time complexity is O(N3). It is called Floyd because one of the inventors of the algorithm is Robert Floyd, a 1978 Turing Award winner and professor of computer science at Stanford University.
core idea
For the weighted graph of n points, starting from the weight matrix of the weighted graph, the shortest path matrix between each two points is finally obtained by recursively updating n times. Namely, the adjacency matrix of the weighted graph is
Dynamic programming
How do you understand this dynamic programming algorithm? It can be understood as selecting the transit points one by one, and then, for this transit point, all the other points as the transit points should be updated according to the regulation, which is the distance between the original two points. If the distance becomes smaller through the transit point, the distance matrix should be updated. For example, if “1” is selected as the transit point, the original distance between “02” is 5, but after passing through the transit point 1 (that is, the path becomes “012”), the distance becomes 4 and becomes smaller. Then, the element corresponding to the distance matrix is updated from 5 to 4. When all the vertices in the graph are treated as transit points, the final distance matrix is the multi-source shortest distance matrix.
set
Now we set up
The algorithm process
- Starting from any single path, the distance between all points is the weight of the edge, and if there is no edge between the points, the weight is infinite. With an array
To record the shortest distance between I and j, initially, if I =j then dis[I][j]=0. If two points I and j are connected, dis[I][j] is the weight of this edge. If the two points are not connected dis[I][j] is infinite.
- For each pair of vertices u and v, see if there is a vertex W that makes the path from u to w to v shorter than the known path, and update it if there is. For all values of k (1 < k < n), computing (d [I] [k] [k] [j]) + d value, if it is less than d [I] [j], [I] is d [j] [I] [k] = d + d [k] [j], or d [j] [I] value remains the same.
Magic five lines of code
The core of Floyd algorithm is the following five lines of code, as you can see, three for cycles are nested, and the outermost k is the situation when the cycle takes different transit points. Each vertex in the graph is used as the transit point to update the distance, and the final shortest distance matrix is obtained after completing all cycles.
for(k=1; k<=n; k++)for(i=1; i<=n; i++)for(j=1; j<=n; j++)if(d[i][k]+d[k][j]<d[i][j])
d[i][j]=d[i][k]+d[k][j];
Copy the codeThe advantages and disadvantages
Advantages: easy to understand, can calculate the shortest distance between any two nodes, the code is simple. It is best for dense graphs where the edge weights can be positive or negative.
Disadvantages: High time complexity, not suitable for calculating large amounts of data.
Implementation process
For an undirected weighted graph with seven vertices, each vertex of the graph is represented by 0-6, and the number on each edge is the corresponding weight.
First, the distance matrix is initialized according to the weight of each edge, which is a [7×7] matrix. The row and column respectively correspond to two vertices. For example, row 0 and column 1 represent vertices 0 to 1, and the corresponding value is 3, that is, the weight is 3. And so on, the other elements represent the weight of the corresponding edge.
When vertex 0 is the transit point
Look for one by one to see if there’s a transition point of zero that makes the distance shorter, and you don’t really have to compare all the elements of the matrix, you just have to compare if (I! = j && j ! = k && i ! = k) the elements of the condition, that is, the diagonal lines which are both 0, do not need to be compared with the row and column corresponding to the transition point, because the elements on the diagonal represent the distance between the vertex and itself, so there is no need to compare, while the row and column corresponding to the transition point represent the distance between the vertex and the transition point, so there is no need to compare.
Compare d[1][2] with D [1][0]+ D [0][2], because 1<3+5, do not update D [1][2].
Down, compare d [1] [1] and [3] d + d [0] [0] [3], because 4 < 3 + INF, so don’t update d [1] [3].
Down, compare d [1] [4] and [1] d + d [0] [0] [4], because INF < 3 + INF, so don’t update d [1] [4]. Then d[1][5] and D [1][6] have similar conditions.
Compare d[2][1] with D [2][0]+ D [0][1], because 1<3+5, do not update D [2][1].
Down, compare d [2] [3] and [2] d + d [0] [0] [3], because 4 < 5 + INF, so don’t update d [2] [3].
Down, compare d [2] [4] and [2] d + d [0] [0] [4], because eight < 5 + INF, so don’t update d [2], [4].
Down, compare d [2] [5] and [2] d + d [0] [0] [5], because 2 < 5 + INF, so don’t update d [2] [5].
Down, compare d [2] [6] and [2] d + d [0] [0] [6], because INF < 5 + INF, so don’t update d [2] [6].
D [3][1]; d[3][0]+ D [0][1];
Similarly, all the remaining elements are not updated. Finally, after comparing D [6][5] with D [6][0]+ D [0][5], all the comparison work with 0 as the transfer point is completed.
When vertex 1 is the transit point
Search one by one to see if the transit point 1 makes the distance shorter, compare D [0][2] with D [0][1]+ D [1][2],
Because 5>3+1, update the value of d[0][2] to 4.
Compare d[0][3] with D [0][1]+ D [1][3],
Update d[0][3] to 7 because INF>3+4.
After the second line, compare d[2][0] with d[2][1]+ D [1][0],
Because 5>1+3, update the value of d[2][0] to 4. The rest of the second line does not need to be updated.
Start line 3, compare d[3][0] with D [3][1]+ D [1][0],
Update d[3][0] to 7 because INF>4+3.
Then all the remaining elements do not need to be updated when vertex 1 is used as the transit point.
When vertex 2 is the transit point
Search one by one to see if 2 is used as the transit point to make the distance shorter, compare d[0][1] and D [0][2]+ D [2][1], because 3<4+1, so D [0][1] is not updated.
D [0][3] and D [0][2]+ D [2][3], because 7<4+4, so d[0][3] does not update.
Compare d[0][4] with D [0][2]+ D [2][4],
Update d[0][4] to 12 because INF>4+8.
Similarly, all remaining elements with vertex 2 as the transit point are compared and updated.
When vertex 3 is the transit point
Search one by one to see if 3 is used as the transit point to make the distance shorter, compare d[0][1] and D [0][3]+ D [3][1], because 3<7+4, so D [0][1] is not updated.
D [0][2] and D [0][3]+ D [3][2], because 4<7+4, so d[0][2] does not update.
Similarly, all remaining elements with vertex 3 as the transit point are compared and updated.
When vertex 4 is used as the transit point
Search one by one to see if 4 is used as the transit point to make the distance shorter, compare D [0][1] and D [0][4]+ D [4][1], because 3<12+9, so D [0][1] is not updated.
Compare d[0][2] with D [0][4]+ D [4][2], d[0][2] is not updated because 4<12+8.
Similarly, all remaining elements with vertex 4 as the transit point are compared and updated.
When vertex 5 is used as the transit point
Search one by one to see if 5 is used as the transit point to make the distance shorter, compare d[0][1] and D [0][5]+ D [5][1], because 3<6+3, so D [0][1] is not updated.
D [0][2] and D [0][5]+ D [5][2], because 4<6+2, so d[0][2] does not update.
Similarly, all remaining elements with vertex 5 as the transit point are compared and updated.
When vertex 6 is used as the transit point
Search one by one to see if 6 is used as the transit point to make the distance shorter, compare D [0][1] with D [0][6]+ D [6][1], because 3<9+6, so D [0][1] is not updated.
D [0][2] and D [0][6]+ D [56][2], because 4<9+5, so d[0][2] is not updated.
Similarly, all remaining elements with vertex 6 as the transit point are compared and updated.
Eventually matrix
After treating all vertices as transit points, a matrix is finally obtained, which is the shortest distance matrix of each vertex of the graph in pairs. For example, if a[0][4]=12, the shortest distance from vertex 0 to vertex 4 is 12. It can also be seen that the distance matrix is axially symmetric on the diagonal.
————- Recommended reading ————
Summary of my open Source projects (Machine & Deep Learning, NLP, Network IO, AIML, mysql protocol, Chatbot)
Why to write “Analysis of Tomcat Kernel Design”
My 2017 article summary – Machine learning
My 2017 article summary – Java and Middleware
My 2017 article summary – Deep learning
My 2017 article summary — JDK source code article
My 2017 article summary – Natural Language Processing
My 2017 Article Round-up — Java Concurrent Article
Talk to me, ask me questions:
Welcome to:
