Counts for the smallest: Ford & Bellman or how to understand that you got into the infinitely distant past

In the previous parts of the cycle, we looked at the DFS and BFS algorithms that allow us to find a path in a graph and have a number of other interesting properties. But in life it often turns out that the problem model looks much simpler in the form of a graph with unequal edge lengths. We will be engaged in search of the shortest way in the weighted column under a cat.

Formulation of the problem

The problem considers a weighted graph - that is, a graph, each edge of which is associated with a number, called its weight. The weight of the edge leading from the vertex u to the vertex v will be denoted by weight [u, v].

It is required to find a path from the vertex u to the vertex v, the sum of the edge weights of which is minimal. This sum of weights will be called the distance from the vertex u to the vertex v and denoted dist [u, v].

In life there are quite a large number of tasks that can be reformulated in the specified form - for example, the task of determining the time to travel in the subway (and the optimal route), subject to the availability of fines for transplants.

Let's think of something simple

Consider some edge (v, w). What can we say about the distance to its ends? Obviously, dist [u, w] ≤ dist [u, v] + weight [v, w].

Evidence

Let dist [u, v] = K. This means that there is a path from u to v with weight K. We add to this path an edge (v, w). Get the path from u to w with weight K + weight [v, w]. Since the distance from u to w is the minimum of the lengths of all paths connecting u and v, dist [u, w] ≤ K + weight [v, w]

Let's act iteratively. Initially, the distance is only known to the initial vertex - it is 0. At any time, we can check the property for some edge and, if it is broken, improve the existing estimate of the distance to the final vertex of the edge. This procedure is called relaxation.

')

Words are nothing, show me the code!

Ford & Bellman algorithm

The code assumes that the graph is stored in vector <vector <pair <int, int >>> edges, where edges [v] is the vector of all edges emanating from the vertex v. In the edge edges [v] [i], the first field is the final vertex of the edge, the second is its weight. INF is some constant, obviously larger than any resulting distance. Indicates the absence of a known path.

void ford_bellman(int start) { //  for (int i = 0; i < (int)edges.size(); ++i) { dist[i] = INF; } dist[start] = 0; // V     for (int iter = 0; iter < (int)edges.size(); ++iter) { //    for (int v = 0; v < (int)edges.size(); ++v) { //    for (int i = 0; i < (int)edges[v].size(); ++i) { //   if (dist[edges[v][i].first] > dist[v] + edges[v][i].second) { //   dist[edges[v][i].first] = dist[v] + edges[v][i].second; } } } } }

How many resources does the algorithm need?

In addition to the graph and the values outstanding in response, we store only a constant amount of memory, therefore, the amount of memory required by the algorithm is O (1) + <memory for storing the graph and response> = O (V + E) = O (E).

Relaxation of each edge takes a constant amount of action. Total ribs - E, relaxation of all ribs produced V times. Thus, the time complexity of the algorithm is O (VE).

And if I'm a pedant?

Let's prove that after k iterations, the algorithm will find all the shortest paths consisting of k edges or less. Then it turns out that at the end of the work he will find all the shortest paths from no more than V edges - that is, all the existing shortest paths.

For convenience, we denote the initial vertex u.

Base: k = 0 obviously, the path from the initial vertex to it is found correctly
Assumption: after k iterations for all vertices v, to which there is a shortest path consisting of no more than k edges, dist [v] is equal to the distance from the initial vertex to v
Step: Consider a vertex w, to which there is a shortest path consisting of k + 1 edges.
- Denote the penultimate vertex in the path from u to w, as v.
- For v, there is a shortest path from k vertices (for example, the beginning of the shortest path to w).
- Hence, the shortest path to v was found at the previous iteration. After relaxation of the edge (v, w) at the k + 1st iteration, we obtain the correct value of the distance to the vertex w.
- Note that during the relaxation of any other edge, we could not get a value smaller than the correct distance, since for each relaxation the edge (x, w) can be associated with the path from the initial vertex to w of the corresponding length.

What about time travel?

In the proof, it was not for nothing that a reservation was made - all the existing shortest paths are searched. There is a situation in which there is a path from u to v, but there is no shortest path from u to v — for example, if both of these vertices go into a cycle of negative weight. This is the mathematical equivalent of the case when the transitions between the vertices are portals, and those that can throw both into the past and into the future. The presence of a negative weight cycle means that after going through the right amount of revolutions, you can end up in the past as far as you want.

The Ford-Bellman algorithm also provides a method for finding such cycles: if there are no cycles, then all the shortest paths are no longer than from the V - 1 edge, and no relaxation will be performed at the last iteration. All edges, the relaxation of which was performed at the last iteration, lie in cycles of negative weight, reachable from the initial vertex.

Source: https://habr.com/ru/post/201588/

All Articles