Finding the shortest paths from a given vertex to all other vertices Dijkstra's algorithm
Statement of the Problem
Dan directed or undirected weighted graph with vertices and edges. The weights of all edges are non-negative.Contains some starting vertex . Required to find the length of the shortest paths from the vertex to all other vertices, as well as provide a way to output the shortest paths themselves.
This problem is called "the problem of the shortest paths from a single source" (single- source shortest paths problem).
Algorithm
Here we describe an algorithm that offered Dutch researcher Dijkstra (Dijkstra) in 1959 Zavedёm array in which each vertex will store the current length of the shortest path in . Initially , and for all the other vertices, this length is equal to infinity (when implemented on a computer usually as infinity simply choose a sufficiently large number, certainly more possible path length):
In addition, for each vertex we store, it is still labeled or not, i.e. zavedёm boolean array . Initially, all vertices are labeled, ie
Dijkstra's algorithm itself consists of iterations . At the next iteration of the selected vertex with the lowest value among the not yet marked, ie .:
(It is understood that on the first iteration will be selected starting vertex .)
Selected so the top notes marked. Further, in the current iteration, from the top are made of relaxation : Browse all edges emanating from a vertex , and for each such vertex algorithm tries to improve value . Let the length of this edge is then in the form of relaxation code looks like:
At the ends the current iteration, the algorithm proceeds to the next iteration (again selects the lowest peak value , the relaxation produced from it, etc.). In the end, after iterations, all the vertices of the graph will be marked, and the algorithm completes its work. It is alleged that the obtained values are the desired length of the shortest paths from a . It is worth noting that, if not all vertices reachable from a vertex , then the values for them will remain endless. It is clear that the last few iterations of the algorithm will just select these vertices, but no useful work to produce these iterations will not (because an infinite distance can not prorelaksirovat others, too, even infinite distance). Therefore, the algorithm can be immediately stopped as soon as the selected vertex is taken from the top of an infinite distance.
Recovery paths . Of course, you usually need to know not only the length of the shortest path, but get yourself way. We show how to maintain sufficient information to restore the shortest path from any vertex to. It's enough to so-called array ancestors : an array in which each vertex is stored vertex number , which is the penultimate in the fast track to the top . Here we use the fact that if we take the shortest path to some vertex , and then remove from the last vertex of this path, you get way, ending a vertex , and this will be the shortest path for the top . So, if we have this array of ancestors, the shortest path can be restored to him, each time just taking ancestor of the current node until we arrive at the starting vertex - so we get the desired shortest path, but spelled
backwards. Thus, the shortest way to the top is:
It remains to understand how to build the array ancestors. However, this is very simple: at every successful relaxation, ie when the selected vertex is improving distance to a vertex , we record that ancestor vertex is a vertex :
Proof
The main assertion , based on which the correctness of Dijkstra's algorithm is as follows. It is alleged that after some vertex becomes marked, the current distance to it is already the shortest, and, consequently, more will not change.
The proof will be producing by induction. For the first iteration of the justice of his obvious - for the top , we have , which is the length of the shortest path to it.Now suppose that it holds for all previous iterations, ie, all already labeled vertices; prove that it is not broken after the current iteration. Let - top chosen for the current iteration, ie vertices that
are going to mark the algorithm. We will prove that indeed is the length of the shortest path to it (we denote this length through ).
Consider the shortest way to the top . Clearly, this path can be divided into two paths:
consisting only of marked vertices (at least the starting vertex is in the way), and the rest of the way (it can also include a marked peak, but begins always with untagged). Denoted by the first vertex of the path , and through - the last point of the path .
We first prove the assertion for the top , ie, prove equality . However, it is almost obvious: after all, one of the previous iterations we chose the top and perform the relaxation of it. Since (by virtue of the choice of the vertex ) to the shortest path is the shortest path to the plus edge , then if the relaxation of the value really set the desired value.
Due to the non-negativity values ribs length of the shortest path (and she just proved equal ) does not exceed the length of the shortest path to the top .Given
that (after all, Dijkstra's algorithm could not find a shorter path than it is at all possible), as a result we obtain the relations:
On the other hand, and as and - unmarked vertices, so that both the current iteration vertex been chosen instead of a vertex , then obtain another inequality:
From these two inequalities we conclude equality , and then found out before we receive and relations:
QED.
Implementation
Thus, the Dijkstra's algorithm is iterative, each of which is selected unlabeled vertex with the lowest value , this vertex is marked, and then played all edges emanating from that vertex, and along each edge is an attempt to improve the value at the other end of the edge.
Time of the algorithm consists of:
• Just search the top with the lowest value among all unlabelled vertices, ie, among vertices
• relaxation time an attempt is made
At the simplest implementation of these operations on the top of the search will be
spent operations and one relaxation - operations, and the resultingasymptotic behavior of the algorithm is as follows:
Implementation :
const int INF = 1000000000;
int main() { int n;
... чтение n ...
vector < vector < pair<int,int> > > g (n);
... чтение графа ...
int s = ...; // стартовая вершина vector<int> d (n, INF), p (n);
d[s] = 0;
vector<char> u (n);
for (int i=0; i<n; ++i) { int v = -1;
for (int j=0; j<n; ++j)
if (!u[j] && (v == -1 || d[j] < d[v])) v = j;
if (d[v] == INF) break;
u[v] = true;
for (size_t j=0; j<g[v].size(); ++j) { int to = g[v][j].first,
len = g[v][j].second;
if (d[v] + len < d[to]) { d[to] = d[v] + len;
p[to] = v;
} }
} }
Here the graph is stored in the form of adjacency lists: for each vertex list contains a list of edges emanating from the vertex, ie, a list of pairs , where the first element of the pair - the vertex which leads the edge, and the second element - the weight of the edge.
After reading infest arrays distances , marks and ancestors . Then executed iterations. At each iteration, first is the vertex having the smallest distance among unlabelled vertices. If the distance to the selected vertex is equal to infinity, then the
algorithm stops. Otherwise, the vertex is marked as tagged, and viewed all edges emanating from that vertex, and along each edge run relaxation. If relaxation is successful (ie, the distance varies), the distance is converted and stored ancestor .
After all the iterations in the array are the length of the shortest paths to all vertices in the array - the ancestors of all vertices (except home page ). Restore the path to any node can be as follows:
vector<int> path;
for (int v=t; v!=s; v=p[v]) path.push_back (v);
path.push_back (s);
reverse (path.begin(), path.end());
Literature
• Thomas feed, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005]
• Edsger Dijkstra. A Note on two Problems in connexion with graphs [1959]
Finding the shortest paths from a given vertex to all other vertices Dijkstra algorithm for
sparse graphs
Statement of the problem, the algorithm and its proof can be found. In the article on the general Dijkstra's algorithm .
Algorithm
Recall that the complexity of Dijkstra's algorithm consists of two basic operations: Time Spent vertex with the lowest distance and time of relaxation, ie while changing the value .
In a simple implementation of these operations require, respectively , and
time. Given that the first operation is performed just once, and the second - , we obtain the asymptotic behavior of the simplest implementation of Dijkstra's
algorithm: .
It is clear that this asymptotic behavior is optimal for dense graphs, ie, when . The more sparse graph (ie less than the maximum number of edges ), the less optimal becomes this estimate, and the fault of the first term. Thus, it is necessary to improve the operating times of the first type are not strongly compromising the operating times of the second type.
To do this, use a variety of auxiliary data structures. The most attractive are the Fibonacci heap , which allows operation of the first kind and the second - for
. Therefore, when using Fibonacci heaps time of Dijkstra's algorithm will
be , which is almost the theoretical minimum for the algorithm to find the shortest path. By the way, this estimate is optimal for algorithms based on Dijkstra's
algorithm, ie, Fibonacci heap are optimal from this point of view (this is about the optimality actually based on the impossibility of the existence of such an "ideal" data structure - if it existed, it would be possible to perform sorting in linear time, which, as you know, in the general case impossible; however, it is interesting that there is an algorithm Torup (Thorup), who is looking for the shortest path to the optimal linear, asymptotic behavior, but it is based on a completely different idea than Dijkstra's algorithm, so no contradiction here). However, Fibonacci heap rather difficult to implement (and, it should be noted, have a considerable constant hidden in the asymptotic).
As a compromise, you can use the data structures that enable you to both types of
operations (in fact, is the removal of the minimum and update element) for . Then the time of Dijkstra's algorithm is:
In the data structure such as C ++ programmers conveniently take a standard container or . The first is based on a red-black tree, the second - on the binary heap. Therefore has a smaller constant hidden in the asymptotic behavior, but it has a drawback: it does not support the delete operation element, because of what is necessary to do "workaround" that actually leads to the substitution in the asymptotics for (in terms of the asymptotic behavior of this really really does not change anything, but the hidden constant increases).
Implementation
set
Let's start with the container . Since the container we need to keep the top, sorted by their values , it is convenient to put in a container couples: the first member of the pair - the distance, and the second - the number of vertices. As a result, the pair will be stored automatically sorted by the distance that we need.
const int INF = 1000000000;
int main() { int n;
... чтение n ...
vector < vector < pair<int,int> > > g (n);
... чтение графа ...
int s = ...; // стартовая вершина vector<int> d (n, INF), p (n);
d[s] = 0;
set < pair<int,int> > q;
q.insert (make_pair (d[s], s));
while (!q.empty()) {
int v = q.begin()->second;
q.erase (q.begin());
for (size_t j=0; j<g[v].size(); ++j) { int to = g[v][j].first,
len = g[v][j].second;
if (d[v] + len < d[to]) {
q.erase (make_pair (d[to], to));
d[to] = d[v] + len;
p[to] = v;
q.insert (make_pair (d[to], to));
} }
} }
Unlike conventional Dijkstra's algorithm, the array becomes unnecessary . His role as the function of finding the vertex with the smallest distance performs .Initially, he put the starting vertex with its distance. The main loop of the algorithm is executed in the queue until there is at least one vertex. Removed from the queue vertex with the smallest distance, and then run it from the relaxation. Before performing each successful relaxation we first removed from an old pair, and then, after relaxation, add back a new pair (with a new distance ).
priority_queue
Fundamentally different from here there is, except for the point that removed from the arbitrary elements is not possible (although theoretically heap support such an operation, in the standard library is not implemented). Therefore it is necessary to make "workaround": the relaxation just will not remove the old couple from the queue. As a result, the queue can be simultaneously several pairs of the same vertices (but with different distances). Among these pairs we are interested in only one for which the element
is , and all the rest are fictitious. Therefore it is necessary to make a slight modification:
the beginning of each iteration, as we learn from the queue the next pair, will check fictitious or not (it is enough to compare and ). It should be noted that this is an important modification: if you do not make it, it will lead to a significant deterioration of the asymptotics
(up ).
More must be remembered that organizes the elements in descending order, rather than ascending, as usual. The easiest way to overcome this feature is not an indication of its comparison operator, but simply putting as elements of distance with a minus sign. As a result, at the root of the heap will be provided with the smallest elements of the distance that we need.
const int INF = 1000000000;
int main() {
... чтение n ...
vector < vector < pair<int,int> > > g (n);
... чтение графа ...
int s = ...; // стартовая вершина vector<int> d (n, INF), p (n);
d[s] = 0;
priority_queue < pair<int,int> > q;
q.push (make_pair (0, s));
while (!q.empty()) {
int v = q.top().second, cur_d = -q.top().first;
q.pop();
if (cur_d > d[v]) continue;
for (size_t j=0; j<g[v].size(); ++j) { int to = g[v][j].first,
len = g[v][j].second;
if (d[v] + len < d[to]) { d[to] = d[v] + len;
p[to] = v;
q.push (make_pair (-d[to], to));
} } }
}
As a rule, in practice version is slightly faster version .
Getting rid of the pair
You can still slightly improve performance if the container is still not keep couples, and only the numbers of vertices. At the same time, of course, you have to reboot the comparison operator for the vertices: compare two vertices must be over distances up to them . As a result of the relaxation of the magnitude of the distance from the top of some changes, it should be understood that "in itself" data structure is not rebuilt. Therefore, although it may seem that remove / add items in a container in the relaxation process is not necessary, it will lead to the destruction of the data structure. Still before the relaxation should be removed from the top of the data structure , and after relaxation insert it back - then no relations between the elements of the data structure are not violated.
And since you can remove items from , but not of , it turns out that this technique is only applicable to . In practice, it significantly increases performance, especially when the distances are used for storing large data types (such as
or ).
Bellman-Ford algorithm
Let a directed weighted graph with vertices and edges, and contains some vertex . You want to find the length of the shortest path from the top to all other vertices.
Unlike Dijkstra's algorithm , the algorithm can also be applied to graphs containing the edges of negative weight. However, if the graph contains a negative cycle, then, of course, some of the shortest path to the vertices might not exist (due to the fact that the weight of a shortest path to be equal to minus infinity); however, this algorithm can be modified to signal the presence of the negative cycle of the weight, or even He concludes the cycle.
The algorithm is named after two American scientists: Richard Bellman (Richard Bellman) and Leicester Ford (Lester Ford). Ford actually invented this algorithm in 1956 in the study of other mathematical problem, which has been reduced to sub-task of finding the shortest path in the graph, and Ford gave a sketch of the algorithm to solve this problem. Bellman in 1958 published an article devoted specifically the problem of finding the shortest path, and in this article he clearly formulated the algorithm in the form in which we know it now.
Description of the algorithm
We believe that the graph contains no cycles of negative weight. The case of the presence of a negative cycle will be discussed below in a separate section.
Zavedёm array of distances that after execution of the algorithm will contain the answer to the problem. At the beginning of the work we fill it as follows: and all other elements are equal to infinity .
The algorithm itself Bellman-Ford is a few phases. At each phase to view all edges of the graph and the algorithm tries to produce relaxation (relax, easing) along each edge cost . Relaxation along the edge - is an attempt to improve the value of value . In fact, it means that we are trying to improve the response for the top , using the edge and the current response for the top .
It is argued that sufficient phase algorithm to correctly calculate the length of the shortest paths in the graph (again, we believe that the negative weight cycles available). For inaccessible vertex distance will be equal to infinity .
Implementation
Algorithm Bellman-Ford, unlike many other graph algorithms, it is more convenient to represent the graph in the form of a list of all the edges (not lists of edges - the edges of each vertex). The table of realization of the data structure for the edge. The inputs to the algorithm are the number , a list of edges and the number of the starting vertex . All rooms vertices are numbered on .
The simplest implementation
The constant is the number of "infinity" - it must be chosen in such a way that it is certainly superior to all possible lengths of the paths.
struct edge {
int a, b, cost;
};
int n, m, v;
vector<edge> e;
const int INF = 1000000000;
void solve() {
vector<int> d (n, INF);
d[v] = 0;
for (int i=0; i<n-1; ++i) for (int j=0; j<m; ++j)
if (d[e[j].a] < INF)
d[e[j].b] = min (d[e[j].b], d[e[j].a] + e[j].cost);
// вывод d, например, на экран }
Checking the "if (d [e [j] .a] <INF)" is needed only if the graph contains edges of negative weight: without such a test would be a relaxation of the vertices to which the path is not found, and would appear incorrect type of distance , etc.
Improved implementation
This algorithm can speed up a few: often the answer is already in several phases, and the remaining phases of any useful work does not happen only in vain to view all
edges. Therefore, we will keep the flag that something has changed in the current phase or not, and if at some stage nothing has happened, then the algorithm can be stopped. (This optimization does not improve the asymptotic behavior, ie on some graphs will still need all the phase, but significantly accelerates the behavior of the algorithm "on average", ie random graphs.)
With this enhancement, it becomes unnecessary to restrict all by hand the number of phases of the algorithm number - he stops after the desired number of phases.
void solve() {
vector<int> d (n, INF);
d[v] = 0;
for (;;) {
bool any = false;
for (int j=0; j<m; ++j) if (d[e[j].a] < INF)
if (d[e[j].b] > d[e[j].a] + e[j].cost) { d[e[j].b] = d[e[j].a] +
e[j].cost;