Directory
algorithm thinking
Implementation steps
1. Dijkstra algorithm execution steps:
2. Bellman-Ford algorithm execution steps
3. Floyd algorithm execution steps
For example, in the figure above, find the shortest path from V1 to every other vertex.
There are 3 common algorithms for finding the shortest path, namely Dijkstra (Dijkstra), Bellman-Ford algorithm, and Floyd (Floyd) algorithm, among which Dijkstra algorithm is recognized as the optimal algorithm.
Algorithmic Thought
1. Dijkstra: Dijkstra’s algorithm uses the idea of greedy algorithm to spread from the initial vertex to the surrounding one by one, and adopts the idea of breadth first, each of which can obtain the shortest path of a point and a new confirmation point; the next time Just start from all confirmed points and continue until the last point is confirmed. Time complexity O(n);
2. Bellman-Ford: The idea of the Bellman-Ford algorithm is to number each change from 1 to n, and then traverse it in a loop. The traversal method is to calculate the end point data of the edge from the first edge [end point = starting point + edge The weight value] until the nth edge completes a traversal. When the graph has m vertices, it needs to traverse m – 1 times to ensure the correctness of the result.
3. Floyd: The Floyd algorithm is different from the previous two algorithms. It can calculate the shortest distance from each vertex to any other vertex. The idea is to start from any vertex i, whether it is possible to use any vertex j to reach any other vertex k, and the distance is less than vertex i to go directly to vertex k. For details, see the detailed steps below.
Implementation steps
1. Dijkstra algorithm execution steps:
a: Set all the vertices in the graph, the value of the starting point is set to 0, and all other values are set to infinity (∞), indicating the distance from each vertex to the starting point. The starting point is the first confirmation point.
b: Starting from the first confirmation point, spread to the surrounding according to breadth-first traversal, calculate the shortest distance of adjacent points, if the new shortest distance is smaller than the previous one, update it, and this traversal will find the second confirmation point.
c: According to the method of step b, starting from all the confirmation points, find the third, fourth, …, the last confirmation point.
The confirmation process in the above figure is as follows
Step 1: Initial situation: set the distance of V1 to 0 and the others to infinity.
Step 2: Obtain the first confirmation point V1, start from V1, calculate the shortest path of all adjacent points, and obtain the second confirmation point V2
Step 3: Get the third confirmation point V3
Step 4: Get Verification Point V6
Step 5: Get Confirmation Point V4
Step 6: Get Verification Point V5
2, Bellman-Ford algorithm execution steps
Step 1: Initially, number all edges
Step 2: Starting from the first table edge, calculate the new value of each node in order, and the results of the first traversal are as follows.
Step 3: Continue to execute step 2 until the number of traversals = the number of vertices – 1; we can find that the final correct result is obtained after one execution in the above figure. This is because we are lucky to number the edges. If the above figure If number 8 is changed to number 1, it needs to be executed many times to get the correct result.
3, Floyd algorithm execution steps
/**
* As in the following two-digit array, [vi][vj] represents the shortest distance from vi to vj in the above figure, and the initial conditions are as follows.
* v1 v2 v3
* v1 0 4 2
* v2 ∞ 0 1
* v3 2 1 0
*
*
* Step 1: Taking v1 as the starting point, can you reach other points with the help of v1. in spite of
* Step 2: Starting from v1, judge whether v2 can be used to make the distance from v1 to vj (j = 1,2,3) smaller than the initial situation.
* Analysis: v1 reaches v1 by means of v2, because v2 cannot reach v1, it is not considered. So v1 -> v1 = 0.
* v1 uses v2 to reach v2, the result is still v1 -> v2 = 4.
* v1 uses v2 to reach v3, because v2 to v3 is 1, and the new route size is v1v2 + v2v3 = 4 + 1 = 5 > v1v3 = 2, so the previous value can still be used.
* Step 3: Starting from v1, judge whether the distance from v1 to vj (j = 1,2,3) is smaller than the initial situation by using v3.
* Analysis: v1 reaches v1 through v3. Pass
* v1 reaches v2 with v3, v1v3 + v3v2 = 3 < v1v2 = 4, so update v1 -> v2 = 3
* v1 reaches v3 by means of v3. Pass.
* In this way, the new distance array can be obtained: v1v2 has changed
* v1 v2 v3
* v1 0 3 2
* v2 ∞ 0 1
* v3 2 1 0
*
* Step 4: Taking v2 as the starting point, judge that the distance to reach vj (j = 1, 2, 3) with the help of v1 is smaller than the initial situation.
* Analysis: v2 uses v1 to reach v1, don't worry
* v2 uses v1 to reach v2, don't care
* v2 uses v1 to reach v3, which needs to be compared. v2v1 + v1v3 = ∞ > v2v3 = 1, over
*
* Step 5: Taking v2 as the starting point, can you reach other points with the help of v2. Pass
*
* Step 6: Taking v2 as the starting point, can you reach other points with the help of v3
* Analysis: v2 reaches v1 by means of v3, v2v3 + v3v1 = 3 < v2v1 = ∞, so v2 -> v1 = 3
* v2 reaches v2 via v3, don't worry
* v2 reaches v3 via v3, don't worry
*
* In this way, the new distance array can be obtained: v2v1 has changed
* v1 v2 v3
* v1 0 3 2
* v2 3 0 1
* v3 2 1 0
*
* Step 7: Taking v3 as the starting point, can you reach other points with the help of v1
* Analysis: v3 uses v1 to reach v1, don't worry about it
* v3 uses v1 to reach v2, v3v1 + v1v2 = 2 + 3 = 5 > v3v2 = 1, after
* v3 uses v1 to reach v3, don't care
*
*
* Step 8: Taking v3 as the starting point, can you reach other points with the help of v2
* Analysis: v3 uses v2 to reach v1, v3v2 + v2v1 = 1 + 3 = 4 > v3v1 = 2, after
* v3 reaches v2 via v2, don't worry
* v3 reaches v3 via v2, don't worry
*
* Step 9: Take v3 as the starting point, whether you can reach other points with the help of v3, don’t worry about it.
*
* Finish
* So the final result is as follows: any [vi][vj] represents the shortest distance.
*
* v1 v2 v3
* v1 0 3 2
* v2 3 0 1
* v3 2 1 0
*
*/
As can be seen from the above steps, the time complexity of Floyd’s algorithm is O(n^2), where n is the number of vertices in the graph.