Shortest path problem

In the graph structure, there are many algorithms to solve the shortest path problem, bellman-Ford is one of them, it can deal with the case with negative edge weight, also the single-source shortest path algorithm, but the Dijkstra algorithm mentioned earlier cannot deal with the case with negative edge weight. The corresponding cost is that the time complexity of the algorithm is higher. We’ll look at that later.

The ability to deal with negative weighted edges here is for directed graphs, because for undirected graphs, having negative weighted edges means having negative weighted loops, and finding the shortest path in this case with negative weighted loops is unsolvable, because every time you go through a negative weighted loop, the distance decreases, it keeps going forever.

Before we go any further, let’s add a property of graph shortest paths:Subpaths of shortest paths are also shortest pathsThe mathematical description is as follows: directed graphSet,For from the point ofpoint-to-pointA shortest path to, andSet,For the pathFrom the point ofpoint-to-pointOf the subpath, thenIt’s the shortest path between these two points. To prove by contradiction:

Proof: If will pathBroken down into, there are. Let’s say I have a delta fromtoA shorter path to.. The new path weight is, this has to do withIt’s the shortest path contradiction.

Bellman – Ford algorithm

Similar to Dijkstra’s algorithm, Bellman-Ford algorithm also obtains the final solution through continuous “relaxation” operations. Relaxation is the following operation:saidwithThe weight between,Represents from the source pointTo the limitIf there is an edgeThat:(that is, a better path than the current path is found), then updatesAnd update the path. You can see that each relaxation is getting closer to the optimal solution. Dijkstra algorithm relaxes the unprocessed edge of the vertex by selecting the smallest unprocessed vertex each time through the priority queue. Bellman-ford simply relaxes all the edges and repeatsTime (Is the number of vertices), time complexity. As you can see, bellman-Ford relaxation is much more frequent than Dijkstra, so its time complexity is higher than Dijkstra’s.

The pseudocode is as follows:

function BellmanFord(list vertices, list edges, vertex sourceDist [v] represents the distance between the source node and vertex V, and prev[v] represents the precursor vertex of vertex Vfor each vertex v in vertices
        dist[v] = inf
        prev[v] = null

    dist[source] = 0 / / step iterative relaxation | V | 1 2 timesfor i from 1 to size(vertices) -1 
        for each edge(u,v) with weight(u,v)  in edges
            ifDist [u] + weight(u,v) < dist[v] dist[v] dist[V] = Dist [U] + weight(u,v) prev[v] = u // Step 3 Check whether there is negative weight loopfor each edge(u,v) with weight(u,v) in edges
        if dist[u] + weight(u,v) < dist[v]
            error "Negative weight loop detected"

    return dist[], prev[]
Copy the code

Optimization of the algorithm:In practice, Bellman-Ford algorithm does not need iterative relaxationSecond, the maximum path length in the theoretical figure isActually, it’s usually less than that, that is, inIt has converged before the next iteration relaxation, and the shortest path has been calculated, so the judgment can be set in the cycle. When the relaxation is no longer carried out in a certain cycle, it indicates that the current convergence has been achieved, and step 2 can be quit to check whether there is a negative weight loop in the next step.

How do we understand this algorithm?If a vertex is not connected to the source vertex, that is, there are no edges, then the point will not be relaxed, the distance will not be updated, and it will remain infinite. If the vertex is connected to the source vertex, in the absence of a negative weight loop, there must be a shortest path, this shortest pathFor the source pointtoAny shortest path between (here.). How many edges are there at most? Suppose figure haveOne vertices, so there are. In the first round of relaxation, the relaxed edges must contain edgesCombined with the property that the subpath of the shortest path must also be the shortest path mentioned at the beginning of the article,I’ve got the shortest path, and in the second round of relaxation, one of the relaxed edges must containAfter this relaxation,I’ve got the shortest path. And so on, at noIn wheel relaxation, the relaxed edge must contain an edgeAfter,It also gets its shortest path. In other words, the number of edges in the shortest path to the source vertex isThe vertices of theta are at number oneWheel slack must be confirmed (shortest path found). So, how many rounds do we need to relax? At mostB: Once will do.

Mathematical proofs of algorithms can be found in graph theory or Introduction to Algorithms.

Code implementation seebellman_ford.cpp. Finally, let’s do the time complexity, worst-case scenarioThis is easier to understand. Best case, relax all edges at one time, corresponding to the order of edge relaxation is exactly the shortest path tree generation order.

Application of algorithm

One such application is the routing protocol (distance vector protocol), which implements a routing protocol test project, see router code. A routing algorithm based on routing table is implemented.

Finally, welcome to follow the wechat public account: one day thinking, learning and progress together.