Basic algorithms for finding the shortest paths in weighted graphs
Surely many of the game developers (or just people who are addicted to programming) will be interested to hear these four most important algorithms that solve the problem of the shortest paths.
We formulate the definitions and the problem.
A graph will be called several points (vertices), some pairs of which are connected by segments (edges). A graph is connected if from each vertex one can reach any other along these segments. A cycle is a path along the edges of a graph starting and ending at the same vertex. And another graph is called weighted, if each edge corresponds to some number (weight). There cannot be two edges connecting the same vertices.
Each of the algorithms will solve some problem about the shortest paths on the weighted connected. The shortest path from one vertex to another is such a path along the edges that the sum of the weights of the edges along which we have passed will be minimal.
For clarity, I will give an example of such a task in real life. Suppose there are several cities and roads connecting these cities. In addition, each road has a length. You want to get from one city to another, traveling as little as possible.
We assume that in the graph n vertices and m edges.
Let's go from simple to complex.
Finds the distance from each vertex to each for the number of operations of the order of n ^ 3 . Weights can be negative, but we can not have cycles with a negative sum of the weights of the ribs (otherwise we can walk on it as much as we please and reduce the amount each time, so it’s not interesting).
In the array d [0 ... n - 1] [0 ... n - 1] at the i-th iteration we will store the answer to the original problem with the restriction that we will use vertices with the number strictly less than i - 1 (vertices are numbered from zero). Let the i-th iteration go, and we want to update the array to i + 1-th. To do this, for each pair of vertices, we simply try to take i - the 1st vertex as a transfer point, and if this improves the answer, then leave it as well. In total, we will do n + 1 iteration, after its completion we will be able to use any one as a “interchange”, and array d will be the answer.
n iterations over n iterations over n iterations, total order n ^ 3 operations.
Pseudocode:
Finds the distance from one vertex (we give it the number 0) to all others for the number of operations of order n * m . Similar to the previous algorithm, weights can be negative, but we cannot have cycles with a negative sum of edge weights.
Let's create an array d [0 ... n - 1] in which at the i-th iteration we will store the answer to the original problem with the restriction that the path should include strictly less than i edges. If there are no such paths to the vertex j, then d [j] = 2000000000 (this must be some unreachable constant, “infinity”). At the very beginning of d, 2000000000 is filled. To update an array at the i-th iteration, you just need to go through each edge and try to improve the distance to the vertices it connects. The shortest paths do not contain cycles, since all cycles are non-negative, and we can remove the cycle from the path, and the path length does not deteriorate (I would also like to note that this is how you can find negative cycles in the graph: you need to do another iteration and see whether the distance to any vertex has improved). Therefore, the length of the shortest path is not greater than n - 1, which means that after the nth iteration, d will be the answer to the problem.
n iterations with m iterations, total order n * m operations.
Pseudocode:
Finds the distance from one vertex (give it the number 0) to all the others for the number of operations of order n ^ 2 . All weights are non-negative.
At each iteration, some vertices will be marked, and some will not. Let's get two arrays: mark [0 ... n - 1] - True, if the vertex is marked, False otherwise, d [0 ... n - 1] - the length of the shortest path that passes only along the marked vertices as "interchange" will be stored for each vertex . Also supported is the invariant of the fact that for marked vertices the length indicated in d is the answer. At first, only vertex 0 is marked, and g [i] is x, if 0 and i connects an edge with weight x, equals 2,000,000,000 if they are not joined by an edge, and equal to 0 if i = 0.
At each iteration, we find a vertex, with the smallest value in d among unlabeled, let it be the vertex v. Then d [v] is the answer for v. We prove. Suppose that the shortest path to v from 0 passes not only along labeled vertices as “interchange”, and it is shorter than d [v]. Take the first unmarked vertex on this path, we call it u. The length of the covered part of the path (from 0 to u) is d [u]. len> = d [u], where len is the shortest path length from 0 to v (since there are no negative edges), but we assume len is less than d [v]. Therefore, d [v]> len> = d [u]. But then v does not fit its description - it has not the smallest value d [v] among unlabeled ones. Contradiction.
Now boldly mark the vertex v and recalculate d. We do this until all the vertices become marked, and d is not the answer to the problem.
n iterations of n iterations (to search for a vertex v), a total of order n ^ 2 operations.
Pseudocode:
It does the same thing as the Dijkstra algorithm, but for the number of operations of the order of m * log (n) . It should be noted that m can be of the order of n ^ 2, that is, this variation of the Dijkstra algorithm is not always faster than the classical one, but only for small m.
What do we need in Dijkstra's algorithm? We need to be able to find the minimum vertex by the value of d and be able to update the value of d at some vertex. In the classical implementation, we use a simple array, we can find the minimum vertex with respect to d in the order of n operations, and we can update it in 1 operation. We use the binary heap (in many object-oriented languages, it is embedded). The heap supports operations: add an element to the heap (for the order of log (n) operations), find the minimum element (for 1 operation), remove the minimal element (for the order of log (n) operations), where n is the number of elements in the heap.
Create an array d [0 ... n - 1] (its value is the same as before) and a bunch of q. In the heap, we will store pairs from the vertex number v and d [v] (pairs must be compared with d [v]). Also in the heap may be dummy items. This happens because the d [v] value is updated, but we cannot change it on the heap. Therefore, there can be several elements in the heap with the same vertex number, but with different d values ​​(but there will be no more than m vertices in the heap, I guarantee it). When we take the minimum value on the heap, we need to check whether this element is dummy. To do this, it is enough to compare the value of d in the heap and its real value. And to write the graph instead of a binary array, we use an array of lists.
m times we add an element to the heap, we get about m * log (n) operations.
Pseudocode:
We formulate the definitions and the problem.
A graph will be called several points (vertices), some pairs of which are connected by segments (edges). A graph is connected if from each vertex one can reach any other along these segments. A cycle is a path along the edges of a graph starting and ending at the same vertex. And another graph is called weighted, if each edge corresponds to some number (weight). There cannot be two edges connecting the same vertices.
Each of the algorithms will solve some problem about the shortest paths on the weighted connected. The shortest path from one vertex to another is such a path along the edges that the sum of the weights of the edges along which we have passed will be minimal.
For clarity, I will give an example of such a task in real life. Suppose there are several cities and roads connecting these cities. In addition, each road has a length. You want to get from one city to another, traveling as little as possible.
We assume that in the graph n vertices and m edges.
Let's go from simple to complex.
Floyd-Worshel Algorithm
Finds the distance from each vertex to each for the number of operations of the order of n ^ 3 . Weights can be negative, but we can not have cycles with a negative sum of the weights of the ribs (otherwise we can walk on it as much as we please and reduce the amount each time, so it’s not interesting).
In the array d [0 ... n - 1] [0 ... n - 1] at the i-th iteration we will store the answer to the original problem with the restriction that we will use vertices with the number strictly less than i - 1 (vertices are numbered from zero). Let the i-th iteration go, and we want to update the array to i + 1-th. To do this, for each pair of vertices, we simply try to take i - the 1st vertex as a transfer point, and if this improves the answer, then leave it as well. In total, we will do n + 1 iteration, after its completion we will be able to use any one as a “interchange”, and array d will be the answer.
n iterations over n iterations over n iterations, total order n ^ 3 operations.
Pseudocode:
g // g[0 ... n - 1][0 ... n - 1] - , , g[i][j] = 2000000000, i j d = g for i = 1 ... n + 1 for j = 0 ... n - 1 for k = 0 ... n - 1 if d[j][k] > d[j][i - 1] + d[i - 1][k] d[j][k] = d[j][i - 1] + d[i - 1][k] d Ford-Bellman algorithm
Finds the distance from one vertex (we give it the number 0) to all others for the number of operations of order n * m . Similar to the previous algorithm, weights can be negative, but we cannot have cycles with a negative sum of edge weights.
Let's create an array d [0 ... n - 1] in which at the i-th iteration we will store the answer to the original problem with the restriction that the path should include strictly less than i edges. If there are no such paths to the vertex j, then d [j] = 2000000000 (this must be some unreachable constant, “infinity”). At the very beginning of d, 2000000000 is filled. To update an array at the i-th iteration, you just need to go through each edge and try to improve the distance to the vertices it connects. The shortest paths do not contain cycles, since all cycles are non-negative, and we can remove the cycle from the path, and the path length does not deteriorate (I would also like to note that this is how you can find negative cycles in the graph: you need to do another iteration and see whether the distance to any vertex has improved). Therefore, the length of the shortest path is not greater than n - 1, which means that after the nth iteration, d will be the answer to the problem.
n iterations with m iterations, total order n * m operations.
Pseudocode:
e // e[0 ... m - 1] - , (first, second - , , value - ) for i = 0 ... n - 1 d[i] = 2000000000 d[0] = 0 for i = 1 ... n for j = 0 ... m - 1 if d[e[j].second] > d[e[j].first] + e[j].value d[e[j].second] = d[e[j].first] + e[j].value if d[e[j].first] > d[e[j].second] + e[j].value d[e[j].first] = d[e[j].second] + e[j].value d Dijkstra's Algorithm
Finds the distance from one vertex (give it the number 0) to all the others for the number of operations of order n ^ 2 . All weights are non-negative.
At each iteration, some vertices will be marked, and some will not. Let's get two arrays: mark [0 ... n - 1] - True, if the vertex is marked, False otherwise, d [0 ... n - 1] - the length of the shortest path that passes only along the marked vertices as "interchange" will be stored for each vertex . Also supported is the invariant of the fact that for marked vertices the length indicated in d is the answer. At first, only vertex 0 is marked, and g [i] is x, if 0 and i connects an edge with weight x, equals 2,000,000,000 if they are not joined by an edge, and equal to 0 if i = 0.
At each iteration, we find a vertex, with the smallest value in d among unlabeled, let it be the vertex v. Then d [v] is the answer for v. We prove. Suppose that the shortest path to v from 0 passes not only along labeled vertices as “interchange”, and it is shorter than d [v]. Take the first unmarked vertex on this path, we call it u. The length of the covered part of the path (from 0 to u) is d [u]. len> = d [u], where len is the shortest path length from 0 to v (since there are no negative edges), but we assume len is less than d [v]. Therefore, d [v]> len> = d [u]. But then v does not fit its description - it has not the smallest value d [v] among unlabeled ones. Contradiction.
Now boldly mark the vertex v and recalculate d. We do this until all the vertices become marked, and d is not the answer to the problem.
n iterations of n iterations (to search for a vertex v), a total of order n ^ 2 operations.
Pseudocode:
g // g[0 ... n - 1][0 ... n - 1] - , , g[i][j] = 2000000000, i j d = g d[0] = 0 mark[0] = True for i = 1 ... n - 1 mark[i] = False for i = 1 ... n - 1 v = -1 for i = 0 ... n - 1 if (not mark[i]) and ((v == -1) or (d[v] > d[i])) v = i mark[v] = True for i = 0 ... n - 1 if d[i] > d[v] + g[v][i] d[i] = d[v] + g[v][i] d Dijkstra's Algorithm for Sparse Graphs
It does the same thing as the Dijkstra algorithm, but for the number of operations of the order of m * log (n) . It should be noted that m can be of the order of n ^ 2, that is, this variation of the Dijkstra algorithm is not always faster than the classical one, but only for small m.
What do we need in Dijkstra's algorithm? We need to be able to find the minimum vertex by the value of d and be able to update the value of d at some vertex. In the classical implementation, we use a simple array, we can find the minimum vertex with respect to d in the order of n operations, and we can update it in 1 operation. We use the binary heap (in many object-oriented languages, it is embedded). The heap supports operations: add an element to the heap (for the order of log (n) operations), find the minimum element (for 1 operation), remove the minimal element (for the order of log (n) operations), where n is the number of elements in the heap.
Create an array d [0 ... n - 1] (its value is the same as before) and a bunch of q. In the heap, we will store pairs from the vertex number v and d [v] (pairs must be compared with d [v]). Also in the heap may be dummy items. This happens because the d [v] value is updated, but we cannot change it on the heap. Therefore, there can be several elements in the heap with the same vertex number, but with different d values ​​(but there will be no more than m vertices in the heap, I guarantee it). When we take the minimum value on the heap, we need to check whether this element is dummy. To do this, it is enough to compare the value of d in the heap and its real value. And to write the graph instead of a binary array, we use an array of lists.
m times we add an element to the heap, we get about m * log (n) operations.
Pseudocode:
g // g[0 ... n - 1] - , i- : first - , i- , second - d[0] = 0 for i = 0 ... n - 1 d[i] = 2000000000 for i in g[0] // python style d[i.first] = i.second q.add(pair(i.second, i.first)) for i = 1 ... n - 1 v = -1 while (v = -1) or (d[v] != val) v = q.top.second val = q.top.first q.removeTop mark[v] = true for i in g[v] if d[i.first] > d[v] + i.second d[i.first] = d[v] + i.second q.add(pair(d[i.first], i.first)) d ')
Source: https://habr.com/ru/post/119158/
All Articles