Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to realize the shortest path of C# chart algorithm". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn how to realize the shortest path of the C# chart algorithm.

The least expensive path from one vertex to another.

We use a general model, that is, weighted digraph. In a weighted directed graph, each directed path has a path weight associated with it, which is the sum of the weights of all edges in the path. This important measure enables us to sum up the problem as "finding the directed path with the least weight from one vertex to another".

Single point shortest path. Given a weighted digraph and a starting point s, "is there a directed path from s to a given destination vertex v? if so, find the shortest path (with the least total weight)."

Related questions:

1. API and implementation of weighted digraph and API of single point shortest path

two。 Classical Dijkstra algorithm for solving the shortest path problem with non-negative weight of edges

3. A fast method to solve this problem in acyclic weighted digraphs, where the weight of edges can be negative.

4. The classical Bellman-Ford algorithm is suitable for general cases, where the graph can contain rings and the weight of edges can also be negative.

Algorithms are also needed to find out the rings with negative weights and the shortest paths in the weighted digraphs without such rings.

1. Properties of the shortest path

1. The path is directed. The shortest path needs to consider the direction of each side.

two。 Weight is not necessarily equivalent to distance.

3. Not all vertices are reachable. In order to simplify the problem, the sample graphs here are strongly connected.

4. Negative weighting complicates the problem.

5. The shortest path is usually simple. The algorithm here ignores the zero weight edges that make up the ring, so the shortest path found will not contain a ring.

6. The shortest path is not necessarily unique. There may be multiple shortest paths from one vertex to another, and we just need to find one of them.

7. There may be parallel edges and self-rings. Only the edge with the least weight among the parallel edges is selected, and the shortest path cannot contain a self-loop unless the weight of the self-ring is zero, but it is ignored.

The shortest path

We focus on the single point shortest path problem, where the starting point s is given, and the calculated result is a shortest path tree (SPT), which contains the shortest path from vertex s to all reachable vertices.

Such a tree must exist: generally speaking, there may be two paths of equal length from s to a vertex, and the last edge of one of the paths can be deleted. In this way, there is only one path (that is, a tree) from the starting point to each vertex. By constructing this shortest path tree, you can provide the use case with the shortest path from s to any vertex in the graph, represented by a set of links to the parent node.

two。 Data structure of weighted digraphs API of edges of weighted digraphs

The starting point of the public class DirectedEdge {private int vrampact / the beginning of the edge private int the end of the edge the weight of the private double weight;// edge public DirectedEdge (int vmaeint wMagna double weight) {this.v = v; this.w = w; this.weight = weight } public double Weight () {return weight;} public int From () {return v;} public int To () {return w;}} API of weighted digraphs

Public class EdgeWeightedDigraph {private int adj / Total number of vertices private List [] adj;// adjacency table public EdgeWeightedDigraph (int v) {this.v = v; this.e = 0; adj = new List [v]; for (int I = 0; I

< v; i++) { adj[i] = new List(); } } public int V() { return v; } public int E() { return e; } public void AddEdge(DirectedEdge _e) { adj[_e.From()].Add(_e); e++; } public IEnumerable Adj(int v) { return adj[v]; } public IEnumerable Edges() { List edges = new List(); foreach (var _adj in adj) { edges.AddRange(_adj); } return edges; } } 最短路径的API 最短路径的数据结构 最短路径树中的边。和深度优先搜索，广度优先搜索一样，使用一个顶点索引的 DirectedEdge 对象的父链接数组 edgeTo[ ] ，其中 edgeTo[v] 的值为树中连接 v 和它的父结点的的边（也是从 s 到 v 的最短路径上的最后一条边）。 到达起点的距离。我们需要一个由顶点索引的数组 distTo[ ] ，其中 distTo[v] 为从 s 到 v 的已知最短路径的长度。 我们约定，edgeTo[s] 的值为 null，distTo[s] 的值为 0，从起点到不可达的顶点的距离为Double.MaxValue。 边的松弛 我们的最短路径 API 的实现都基于一个被称为松弛（relaxation）的简单操作。一开始我们只知道图的边和它们的权重，distTo[ ] 中只有起点所对应的元素的值为 0 ，其余元素的值均被初始化为Double.MaxValue 。 随着算法的执行，它将起点到其他顶点的最短路径信息存入 edgeTo[ ] 和 distTo[ ] 数组。在遇到新的边时，通过更新这些信息就可以得到最短路径。特别是，我们在其中会用到边的松弛技术，定义为：放松边 v ->

W means to check whether the shortest path from s to w is from s to v and then from v to w. If so, update the contents of the data structure according to this situation. The shortest path from v to w is the sum of distTo [v] and e.Weight ()-if this value is not less than distTo [w], this edge is invalidated and ignored.

Private void Relax (DirectedEdge e) {int v = e.From (), w = e.To (); if (distto [w] > distTo [v] + e.Weight ()) {distTo [w] = distTo [v] + e.Weight (); edgeTo [w] = e;}}

The following figure shows that two situations may occur after the edge relaxation operation. In one case, the edge fails (on the left) and no data is updated; in the other case, v-> w is the shortest path to w (right), which will update edgeTo [w] and distTo [w] (this may invalidate other edges, but may also produce some new valid edges).

Relaxation of vertices

In fact, the implementation relaxes all edges indicated from a given vertex. It is valid to point to the edge of any distTo [v] infinite vertex from vertex v where distTo [v] is finite. If v is relaxed, then these valid edges are added to edgeTo []. An edge indicated from the starting point will be the first edge to be added to edgeTo []. The algorithm will carefully select vertices so that each vertex relaxation operation can get a shorter path to a vertex, and finally gradually find out the shortest path to each vertex.

Private void Relax (EdgeWeightDigraph DirectedEdge e in G.Adj int v) {foreach (DirectedEdge e in G.Adj (v)) {int w = e.To (); if (distto [w] > distTo [v] + e.Weight ()) {distTo [w] = distTo [v] + e.Weight (); edgeTo [w] = e;}} 3. The theoretical basis of the shortest path algorithm

Edge relaxation is an important operation that is very easy to implement, and it is the basis for implementing the shortest path algorithm. At the same time, it is also the theoretical basis for understanding the algorithm and enables us to prove the correctness of the algorithm completely.

Optimality condition

The optimality condition of the shortest path: let G be a weighted digraph, vertex s is the starting point of G, and distTo [] is an array indexed by vertices, which preserves the length of the path in G. For all vertices v that are reachable from s, the value of distTo [v] is the length of a path from s to v, and for all vertices v that are not reachable from s, the value is infinite. If and only if for any edge e from v to w, these values satisfy distTo [w] w must set the value of distTo [w] to the length of a path from s to w and set edgeTo [w] to the last edge on that path. For any vertex w reachable from s, as long as distTo [w] is still infinitely reachable, an edge on the shortest path to w must still be valid, so the operation of the algorithm will continue until the distTo [] value of each vertex reachable by s becomes the length of a path to the vertex. For any vertex v that has found the shortest path, the value of distTo [v] is the length of a path from s to v and must be monotonously decreasing in the calculation process of the algorithm. Therefore, the number of decrements must be limited (decreasing once for each simple path from s to v). When there is no efficient edge, the optimality condition is established.

The key reason why the optimality condition and the general algorithm are discussed together is that the general algorithm does not specify the relaxation order of the edges. Therefore, to prove that these algorithms can calculate the shortest path, we only need to prove that they will relax all edges until all edges fail.

4.Dijkstra algorithm

In the minimum spanning tree, we share the Prim algorithm for finding the minimum spanning tree in the weighted undirected graph: each step of constructing the minimum spanning tree adds a new edge to the tree. Dijkstra algorithm uses a similar method to calculate the shortest path tree. First initialize the distTo [s] to 0meme distTo [] and initialize the other elements to positive infinity. Then relax the non-tree vertices with the smallest distTo [] and add them to the tree, and so on, until all the vertices are in the tree or the distTo [] values of all non-tree vertices are infinite.

Dijkstra algorithm can solve the single starting point shortest path problem of weighted digraphs with non-negative edge weights. Prove that if v is reachable from the starting point, then all edges of v-> w will be relaxed only once. When v is relaxed, there must be distto [w] distTo [v] + e.Weight () {distTo [w] = distTo [v] + e.Weight (); edgeTo [w] = e; if (pq.Contains (w)) {pq.Change (w, distTo [w])) } else {pq.Insert (wreft distTo [w]);}}

Locus

1. Add vertex 0 to the tree and add vertex 2 and 4 to the priority queue

two。 Remove vertex 2 from the priority queue, add 0-> 2 to the tree, and add vertex 7 to the priority queue

3. Remove vertex 4 from the priority queue, add 0-> 4 to the tree, add vertex 5 to the priority queue, and edge 4-> 7 fails.

4. Remove vertex 7 from the priority queue, add 2-> 7 to the tree, add vertex 3 to the priority queue, and edge 7-> 5 fails.

5. Remove vertex 5 from the priority queue, add 4-> 5 to the tree, add vertex 1 to the priority queue, and edge 5-> 7 fail.

6. Remove vertex 1 from the priority queue, add 5-> 1 to the tree, and edge 1-> 3 fails.

7. Remove vertex 6 from the priority queue and add 3-> 6 to the tree.

The algorithm adds them to the shortest path tree according to the increasing order of the length of the shortest path from the vertex to the starting point.

In a weighted digraph with V vertices and E edges, the space required to calculate the shortest path tree with a given starting point by using the Dijkstra algorithm is proportional to V and the time is proportional to ElogV (worst case).

Variety

Other versions of this problem can be solved with only minor modifications to the implementation of the Dijkstra algorithm. For example, the single point shortest path in a weighted undirected graph.

If you treat an undirected graph as a directed graph, create a weighted directed graph composed of the same vertices, and for each edge in the undirected graph, create two directed edges with different directions accordingly. There is an one-to-one correspondence between the paths in the directed graph and the paths in the undirected graph, and the weight of the path is the same-the problem of the shortest path is equivalent.

The shortest path for a given two points.

Given a weighted digraph, a starting point s and an end point t, find the shortest path from s to t.

To solve this problem, you can use the Dijkstra algorithm and terminate the search after getting t from the priority queue.

The shortest path between any pair of vertices

The following code solves the problem of the shortest path between any pair of vertices, and the time and space required is proportional to EVlogV. It constructs an array of DijkstraSP objects, with each element taking the corresponding vertex as the starting point. When the use case makes a query, the code accesses the single point shortest path object corresponding to the starting point and queries the destination vertex as a parameter.

Public class DijkstraAllPairsSP {private DijkstraSP [] all; public DijkstraAllPairsSP (EdgeWeightedDigraph G) {all = new DijkstraSP [G.V ()]; for (int v = 0; v)

< G.V(); v++) { all[v] = new DijkstraSP(G,v); } } public IEnumerable Path(int s, int t) { return all[s].Path(t); } public double Dist(int s, int t) { return all[s].Dist(t); } }欧几里得图中的最短路径 在顶点为平面上的点且边的权重于顶点欧几里得间距成正比的图中，解决单点，给定两点和任意顶点对之间的最短路径。 下图是Dijkstra 算法在处理欧几里得图时用若干不同的起点产生最短路径树的过程。 下面，将会考虑加权无环图中的最短路径算法并且将在线性时间内解决该问题。然后是负权重的加权有向图中的最短路径问题，Dijkstra 算法并不适用于这种情况。 5.无环加权有向图中的最短路径算法 许多应用中的加权有向图都是不含有有向环的。现在来看一种比Dijkstra 算法更快，更简单的在无环加权有向图中找出最短路径的算法，它的特点是： 1.能够在线性时间内解决单点最短路径的问题； 2.能够处理负权重的边； 3.能够解决相关的问题，例如找出最长的路径。 这种算法是在有向图中学过的无环有向图的拓扑排序算法的简单扩展。 特别的是，只要将顶点的放松和拓扑排序结婚起来，马上就能够得到一种解决无环加权有向图中的最短路径问题 的算法。首先，将 distTo[s] 初始化为 0 ，其他 distTo[ ] 元素初始化为无穷大，然后一个一个地按照拓扑顺序放松所有顶点。 命题 S ：按照拓扑顺序放松顶点，就能在和 E+V 成正比的时间内解决无环加权有向图的单点最短路径问题。每条边 v -->

W will only be relaxed once. When v is relaxed, you get: distto [w] distTo [v] + e.Weight ()) {distTo [w] = distTo [v] + e.Weight (); edgeTo [w] = e;}

Example tracks:

1. The topological sort of vertices of a graph obtained by depth-first search is 5 1 3 6 4 7 0 2.

two。 Add vertex 5 and all edges indicated from it to the tree

3. Add vertex 1 and edge 1-> 3 to the tree

4. Add vertex 3 and edge 3-> 6 to the tree, edge 3-> 7 is invalid

5. Add vertex 6 and edge 6-> 2, 6-> 0 to the tree, and edge 6-> 4 fails.

6. Add vertex 4 and edge 4-> 0 to the tree, and edge 4-> 7 and 6-> 0 fail.

7. Add vertex 7 and edge 7-> 2 to the tree, edge 6-> 2 is invalid

8. Add vertex 0 to the tree, edge 0-> 2 is invalid

9. Add vertex 2 to the tree.

Proposition S is important because its "acyclic" can greatly simplify the conclusion of the problem. For the shortest path problem, the number of times faster than the Diijkstra algorithm based on topological sorting is proportional to the total cost of all priority queue operations in the Diijkstra algorithm. In addition, the proof of proposition S has nothing to do with whether the edge weight is non-negative or not, so the acyclic weighted digraph will not be restricted. Using this feature, the problem of negative weight of edges can be solved.

Longest path

Consider the problem of finding the longest path in an acyclic weighted digraph, where the weight of edges can be positive or negative.

Implementation: copy the original acyclic weighted digraph to get a copy and change the weight of all edges in the copy to a negative value. In this way, the shortest path in the copy is the longest path in the original. To convert the answer to the shortest path question to the answer to the longest path question, simply change the weight in the scheme to a positive value. The time required is proportional to the EVs.

Track:

The known best algorithm for finding the longest simple path in a general weighted digraph (the weight of the edges may be negative) is exponential in the worst case. The possibility of a ring seems to increase the difficulty of the problem exponentially.

Parallel scheduling task

Here again consider the task scheduling problem that has appeared in the directed graph, this time to solve the scheduling problem:

Parallel task scheduling under priority constraints. Given a set of tasks that need to be completed and the time required for each task, as well as a set of priority restrictions on the priority in which the tasks are completed. How to schedule tasks on several identical processors (unlimited number) and complete all tasks in the shortest possible time if the constraints are met?

The scheduling model in the directed graph has only a single processor by default: the tasks are sorted in topological order, and the total time it takes to complete the tasks is the total time required for all tasks. Now assume that there are enough processors and can handle any number of tasks at the same time, subject to only priority restrictions.

There is a linear time algorithm, a method called "critical path", which can prove that this problem is equivalent to the longest path problem in acyclic weighted digraphs.

Assuming that any available processor can complete it in the time required for the task, our focus is to schedule each task as soon as possible. For example, the following table shows a task scheduling problem. The following figure shows the solution, showing the minimum time required for this problem of 173.0.

This scheduling scheme meets all the constraints, and no other scheduling scheme takes less time than this, because tasks must be completed in the order of 0-> 9-> 6-> 8-> 2. This order is the critical path of the problem. Each column of tasks specified by the priority limit represents a possible lower limit of time for the scheduling scheme. If the length of a series of tasks is defined as the earliest possible time to complete all tasks, then the longest task sequence is the critical path of the problem, because the start delay of any task in this task sequence will affect the completion time of the entire project.

Resolve:

The steps of the critical path method to solve the parallel task scheduling problem are as follows: create an acyclic weighted directed graph, which contains a starting point s and an end t, and each character corresponds to two vertices (a start vertex and an end vertex). For each task, there is an edge that points from its start vertex to the end vertex, and the weight of the edge is the time required by the task. For each priority limit v-> w, add an edge with zero weight from the end vertex of v to the starting vertex of w. We also need to add an edge with zero weight from the start point to the start vertex of the task and an edge with zero weight from the end vertex to the end of the task for each task. In this way, the estimated start time of each task is the longest distance from the starting point to its starting vertex.

The next step is to find the longest path-critical path in the acyclic weighted digraph.

Static void Main (string [] args) {string [] strs = File.ReadAllLines (@ "jobs.txt"); var N = Int32.Parse (strs [0]); / / number of tasks EdgeWeightedDigraph G = new EdgeWeightedDigraph (2*N+2); / / 2*N+2 is the number of nodes, with two I nodes for each task, plus the first two nodes int s = 2n, t = 2n + 1 / / start and end for (var I = 0; I

< N; i++) { string[] a = strs[i].Split(" "); double duration = Double.Parse(a[0]); G.AddEdge(new DirectedEdge(i,i+N,duration));//任务起点指向任务终点 G.AddEdge(new DirectedEdge(s,i,0)); G.AddEdge(new DirectedEdge(i+N,t,0)); for (var j = 1; j < a.Length; j++) { int successor = Int32.Parse(a[j]); G.AddEdge(new DirectedEdge(i+N,successor,0)); } } AcyclicSP lp = new AcyclicSP(G,s); for (var i = 0; i < N; i++) Console.WriteLine($"{i} 开始时间:"+lp.DistTo(i)); Console.WriteLine("t distTo:" + lp.DistTo(t)); } 这里实现的任务调度问题的关键路径方法将问题归约为寻找无环加权有向图的最长路径问题。它会根据任务调度问题的描述用关键路径的方法构造一幅加权有向图，然后使用 AcylicLP 找到图中的最长路径，最后打印出各条最长路径的长度，也就是正好是每个任务的开始时间。 解决优先级限制下的并行任务调度问题的关键路径法所需的时间为线性级别。为什么 CPM 类能解决问题？算法的正确性依赖于两个因素。首先，在相应的有向无环图中，每条路径都是由任务的起始顶点和结束顶点组成的并由权重为零的优先级限制条件的边分隔 —— 从起点 s 到任意顶点 v 的任意路径的长度都是任务 v 的开始 / 结束时间的下限，因为这已经是在同一台处理器上顺序完成这些任务的最优的排列顺序了。因此，从起点 s 到终点 t 的最长路径就是所有任务的完成时间的下限。第二，由最长路径得到的所有开始和结束时间都是可行的 —— 每个任务都只能在优先级限制指定的先导任务完成之后开始，因为它的开始时间就是顶点到它的起始顶点的最长路径的长度。因此，从起点 s 到 终点 t 的最长路径长度就是所有任务完成时间的上限。 相对最后期限限制下的并行任务调度 一般的最后期限（deadline）都是相对于第一个任务的开始时间而言的。假设在任务调度问题中加入一种新类型的限制，需要某个任务必须在指定的时间点之前开始，即指定和另一个任务的开始时间的相对时间。这种类型的限制条件在争分夺秒的生产线上以及许多其他应用中都很常见，但它也会使得任务调度问题更难解决。如下表，假设要在前面的示例中加入一个限制条件，使 2 号任务必须在 4 号任务启动后的 12 个时间单位之内开始。实际上，在这里最后期限限制的是 4 号任务的开始时间：它的开始时间不能早于 2 号任务开始 12 个时间单位。在示例中，调度表中有足够的空档来满足这个最后期限限制：我们可以令 4 号任务开始于 111 时间，即 2 号任务计划开始时间前的 12 个时间单位处。需要注意的是，如果 4 号任务耗时很长，这个修改可能会延长整个调度计划的完成时间。同理，如果再添加一个最后期限的限制条件，令 2 号任务必须在 7 号任务启动后的 70 个时间单位内开始，还可以将 7 号任务的开始时间调整到 53，这样就不用修改 3 号任务和 8 号任务的计划开始时间。但是如果继续限制 4 号任务必须在 0 号任务启动后的 80 个时间单位内开始，那么就不存在可行的调度计划了：限制条件 4 号任务必须在 0 号任务启动后的 80 个时间单位内开始以及 2 号任务必须在 4 号任务启动后的 12 个时间单位之内开始，意味着 2 号任务必须在 0 号任务启动后的 93 个时间单位之内开始，但因为存在任务链 0（41 个时间单位）->

9 (29 time units)-> 6 (21 time units)-> 8 (32 time units)-> 2 No. 2 task can only start within 123 time units after the start of task 0 at the earliest.

Deadline limits added to the task scheduling problem

The parallel task scheduling problem under relative deadline is a shortest path problem in a weighted digraph (there may be cycles and negative weight edges). Construct a weighted directed graph according to the description of task scheduling, and add an edge to each deadline limit: if task v must start within d units of time after task w starts, add a bar from v to the edge with negative weight d of w. By inverting the weights of all edges, the problem can be transformed into a shortest path problem. If there is a feasible scheduling scheme, the proof is completed. It is also part of the calculation to determine whether a scheduling scheme is feasible.

The above example shows that edges with negative weights can also play an important role in practical models. It shows that if the shortest path problem with negative weight can be solved effectively, the solution to the parallel task scheduling problem under relative deadline can be found. None of the algorithms we have learned before can accomplish this task: the Dijkstra algorithm is only suitable for edges with positive weights, and the AcylicSP algorithm requires that the directed graph is acyclic. The following is to solve the shortest path problem in digraphs with negative weights and not necessarily acyclic.

6. The shortest path problem in General weighted digraphs

The task scheduling problem under the deadline discussed above tells us that the side with negative weight is more than just a mathematical problem. On the contrary, it can greatly expand the application scope of the model for solving the shortest path problem. Next, consider the shortest path algorithm in a weighted digraph that may contain either rings or edges with negative weights.

Before we begin, let's learn the basic properties of this digraph and update our understanding of the shortest path. The following figure shows the influence of negative weighted edges on the shortest path in a digraph. Perhaps the most obvious change is that when there are negative weighted edges, paths with lower weights may contain more edges than paths with higher weights. When there are only positive weighted edges, our focus is on finding shortcuts, but when there are negative weighted edges, we may detour in order to pass through the negative weighted edges. This effect makes us change the feeling of finding the "shortest" path into an understanding of the nature of the algorithm. So you need to abandon your intuition and think about it on a simple, abstract level.

Try one.

The first idea is to find the edge with the lowest weight (minimum negative value), and then add the weight of all edges to the absolute value of this negative value, so that the original digraph is transformed into a directed graph without negative weighted edges. However, this approach will not solve any problems, because the shortest path in the new diagram has nothing to do with the shortest path in the original image.

Try two

The second idea is to modify the Dijkstra algorithm. The most fundamental defect of this algorithm is that the basis of the original algorithm is to check the path according to the distance from the starting point, and adding an edge will make the path longer. But adding any edges with negative weights will only make the path shorter.

Ring with negative weight

When we study a digraph with negative weight edges, if the graph contains a ring with negative weights, then the concept of the shortest path is meaningless. As shown in the following figure, it is exactly the same as the previous example, except that the weight of edge 5-> 4 is-0.66. Here, the weight of ring 4-> 7-> 5-> 4 is:

0.37 + 0.28-0.66 =-0.01

As long as we circle around this circle, we can get any short path with weight! Note that the weights of all edges of a directed ring do not have to be negative, as long as the sum of the weights is negative.

Definition: a negative weight ring in a weighted digraph is a directed ring with a negative total weight.

Now, suppose a vertex on the path from s to some reachable vertex v is on a negative weight ring. In this case, the shortest path from s to v is impossible, because the negative weight ring can be used to construct a path with arbitrarily small weights. In other words, the shortest path problem is meaningless when there is a negative weight ring.

The shortest path from s to v exists if and only if there is at least one directed path from s to v in the weighted digraph and all vertices on the directed path from s to v do not exist in any negative weight ring.

Note that the requirement that any vertex on the shortest path does not exist in the negative weight ring means that the shortest path is simple, and the shortest path tree of such vertices can be obtained as well as the graph with positive weighted edges.

Try three.

Whether or not there is a negative weight ring, there is the shortest simple path from s to other reachable vertices. Why not define the shortest path to facilitate finding it? However, it is known that the time required by the best algorithm to solve this problem is exponential in the worst case (which will be reduced later). Generally speaking, this kind of problem is so difficult that only a simple version of it will be studied.

Therefore, an algorithm that is well defined and can solve the shortest path of a weighted digraph should be able to:

1. For vertices that cannot be reached from the starting point, the shortest path is positive infinity.

two。 For a vertex on a reachable path from the starting point that belongs to a negative weight ring, the shortest path is negative infinity

3. For all other vertices, the weight of the shortest path is calculated.

From the beginning of the article to the present, we have added various restrictions to the shortest path problem, so that we can find a solution to the corresponding problem. First of all, we do not allow the existence of negative weight edges; secondly, we do not accept directed rings. Now we relax all these conditions and focus on solving the problems in the general directed graph.

Detection of negative weight loop. Does a given weighted digraph contain a negative weight ring? If there is, find it.

The single point shortest path when the negative weight ring is unreachable. Given a weighted digraph and a starting point s and reach any negative weight ring from the s-watt method. Is there a directed path from s to a given vertex v? If so, find the shortest path.

Conclusion: although the shortest path is a meaningless problem in a directed graph with rings, and it can not effectively solve the problem of finding the shortest simple path efficiently in this directed graph, it is still necessary to be able to identify negative weight rings in practical applications. For example, in task scheduling problems under deadlines, negative weight loops may be relatively rare; constraints and deadlines are derived from actual restrictions in the real world, so negative weight loops may come from errors in the problem statement. Finding out the negative weight loop, correcting the corresponding errors, and finding the scheduling scheme without the negative weight loop is the correct way to solve the problem. In other cases, finding the negative weight ring is the goal of the calculation.

Bellman-Ford algorithm can effectively solve these problems and can also be applied to digraphs with positive weighted edges.

Bellman-Ford algorithm. Given the starting point s in any weighted digraph with V vertices, no negative weight ring can be reached from s. The following algorithm can solve the problem of single point shortest: initialize distTo [s] to 0 and other distTo [] elements to infinity. Relax all edges of the digraph in any order and repeat the V wheel.

This method is very general because it does not specify the relaxation order of the edges. Let's focus on a less general method in which only all edges specified from any vertex are relaxed (in any order):

For (int pass = 0; pass)

< G.V(); pass++) { for (v = 0; v < G.V(); v++) { foreach (DirectedEdge e in G.Adj(v)) Relax(e); } } 它总是会放松 VE 条边且只需稍作修改即可使算法在一般情景下更高效。 基于队列的 Bellman-Ford 算法 其实，根据经验我们很容易知道在任意一轮中许多边的放松都不会成功：只有上一轮中的 distTo[ ] 值发生变化的顶点指出的边才能够改变其他 distTo[ ] 元素的值。为了记录这样的顶点，我们使用了一条 FIFO 队列。算法在处理正权重标准样图中进行的操作轨迹如下图，在图中，左侧是每一轮中队列中的有效顶点（红色），紧接着是下一轮中的有效顶点（黑色）。首先将起点加入队列，然后按照以下步骤计算最短路径树： 1.放松边 1 ->

3 and add vertex 3 to the queue

two。 Relax Edge 3-> 6 and add Vertex 6 to the queue

3. Relax edges 6-> 4, 6-> 0 and 6-> 2 and add vertices 4 and 2 to the queue

4. Relax Edge 4-> 7 > 4-> 5 and add vertices 7 and 5 to the queue. Relax the invalid edges 0-> 4 and 0-> 2. Then relax the edge 2-> 7 (and re-color 4-> 7).

5. Relax edge 7-> 5 (and re-color 4-> 5) but do not queue vertex 5 (it is already in the queue). Relax the invalid side 7-> 3. Then relax the invalid edges 5-> 1, 5-> 4 and 5-> 7. The queue is empty at this time.

Realize

According to the above description, there is very little code required to implement the Bellman-Ford algorithm, which is based on two other data structures:

1. A queue Queue used to hold vertices that are about to be relaxed

two。 A bool array OnQ [] indexed by vertices to indicate whether vertices already exist in the queue to prevent vertices from being repeatedly queued.

First, add the starting point s to the queue, and then enter a loop in which each time you take a vertex from the queue and relax it. To insert a vertex into the queue, you need to modify the previous implementation of the Relax method to add the vertex pointed to by the successfully relaxed edge to the queue. These data structures ensure that:

1. There are no duplicate vertices in the queue.

two。 In one round, it is worthwhile that all vertices that change edgeTo [] and distTo [] will be processed in the next round.

To fully implement the algorithm, we need to ensure that the algorithm can be terminated after the V-turn. One way to do this is to explicitly record the number of rounds relaxed. The following code uses another algorithm, which, as detailed later, detects the existence of a negative weight loop in the edgeTo [] of the digraph and ends the run if it is found.

Public class BellmanFordSP {private double [] distTo;// the length of the path from the starting point to a vertex private DirectedEdge [] edgeTo;// from the starting point to the last edge of a vertex private bool [] onQ;// whether the vertex exists in the queue the number of calls to the vertex private int cost;//relax where private Queue queue;// is being relaxed / / whether there is a weight-bearing ring public BellmanFordSP in edgeTo [] {distTo = new double [G.V ()]; edgeTo = new DirectedEdge [G.V ()]; onQ = new bool [G.V ()]; queue = new Queue (); for (int v = 0; v)

< G.V(); v++) distTo[v] = Double.MaxValue; distTo[s] = 0; queue.Enqueue(s); onQ[s] = true; while (queue.Count != 0 && !HasNegativeCycle()) { int v = queue.Dequeue(); onQ[v] = false; Relax(G,v); } } //负权重环的检测 private bool HasNegativeCycle() { throw new NotImplementedException(); } private void Relax(EdgeWeightedDigraph G, int v) { foreach (DirectedEdge e in G.Adj(v)) { int w = e.To(); if (distTo[w] >

DistTo [v] + e.Weight () {distTo [w] = distTo [v] + e.Weight (); edgeTo [w] = e; if (! onQ [w]) {queue.Enqueue (w); onQ [w] = true }} if (cost++% G.V () = = 0) FindNegativeCycle ();}} / / find negative weight ring private void FindNegativeCycle () {throw new NotImplementedException ();}}

The Relax method adds all vertices pointed by successfully relaxed edges to a FIFO queue (there are no duplicate vertices in the queue) and periodically checks whether there is a negative weight ring in the subgraph represented by edgeTo [].

For any weighted digraph with V vertices and a given starting point s, in the worst case, the time it takes for the queue-based Bellman-Ford algorithm to solve the shortest path problem (or to find a negative weight ring reachable from s) is proportional to EV, and the space is proportional to V.

If there is no negative weight ring reachable from s, the algorithm ends after a round of Vmurl relaxation (because all the shortest paths contain less than VMu1). If there is a negative weight ring reachable from s, then the queue can never be empty. After the V round is relaxed, the edgeTo [] array must contain a path containing a ring (from a vertex w back to itself) and the weight of the ring must be negative. Because w will appear on the path twice and the path length at the second occurrence of s to w is less than the path length of the first occurrence of s to w. In the worst case, the behavior of the algorithm is similar to that of the general algorithm and relaxes all the E edges of the V wheel.

The queue-based Bellman-Ford algorithm compares the path length less than the Disjkstra algorithm for the same problem.

Edge with negative weight

The following figure shows the trajectory of the Bellman-Ford algorithm in dealing with digraphs with negative weight edges. First add the starting point to the queue queue, and then follow these steps to calculate the shortest path tree.

1. Relax edges 0-> 2 and 0-> 4 and add vertex 2p4 to the queue.

two。 Relax edge 2-> 7 and queue vertex 7. Relax edge 4-> 5 and add vertex 5 to the queue. Then relax the failed side 4-> 7.

3. Relax edges 7-> 3 and 5-> 1 and add vertices 3 and 1 to the queue. Relax the failed edges 5-> 4 and 5-> 7.

4. Relax edge 3-> 6 and add vertex 6 to the queue. Relax the failed side 1-> 3.

5. Relax edge 6-> 4 and add vertex 4 to the queue. This weighted edge shortens the path to vertex 4, so its edge needs to be relaxed again. The distance from the start to vertices 5 and 1 has been invalidated and will be corrected in the next round.

6. Relax edge 4-> 5 and add vertex 5 to the queue. Relax the failed side 4-> 7.

7. Relax edge 5-> 1 and add vertex 1 to the queue. Relax the failed edges 5-> 4 and 5-> 7.

8. Relax the failed side 1-> 3. The queue is empty.

In this example, the shortest path tree is a path from vertex 0 to vertex 1. All edges indicated from vertices 4, 5 and 1 are relaxed twice.

Detection of negative weight Loop

Implementing BellmanFordSP detects negative weight rings to avoid falling into an infinite loop. We can also separate this detection code so that the use case can be checked and get a negative weight loop. After the constructor of BellmanFordSP runs, a negative weight ring reachable from the starting point exists in the digraph if and only if the queue is non-empty after all edges are relaxed. If so, the subgraph represented by the edgeTo [] array must contain this negative weight ring. We modify the DirectedCycle class in the digraph to find rings in the weighted digraph. The cost of such an inspection is divided into the following parts:

1. Add a variable cycle and a private function FindNegativeCycle. If a negative weight ring is found, the method sets the value of cycle to an iterator that contains all the edges in the ring (or null if it is not found).

two。 The FindNegativeCycle method is called every time the Relax method is called.

This method ensures that the loop in the constructor must be terminated. In addition, the use case can call HasNegativeCycle to determine whether there is a negative weight loop that is reachable from the starting point.

/ / find negative weight ring private void FindNegativeCycle () {int V = edgeTo.Length; EdgeWeightedDigraph spt; spt = new EdgeWeightedDigraph (V); for (int v = 0; v)

< V; v++) { if (edgeTo[v] != null) spt.AddEdge(edgeTo[v]); } EdgeWeightedCycleFinder cf; cf = new EdgeWeightedCycleFinder(spt); cycle = cf.Cycle(); } //负权重环的检测 private bool HasNegativeCycle() { return cycle != null; } public IEnumerable NegativeCycle() { return cycle; } 下图是 Bellman-Ford 算法在一幅含有负权重环的有向图中的运行轨迹。头两轮放松操作与前面的例子一样，在第三轮中，算法放松了边 7 ->

3 and 5-> 1 and add vertices 3 and 1 to the queue and begin to relax the negative weight edge 5-> 4. In this relaxation operation, the algorithm finds a negative weight ring 4-> 5-> 4. It adds 5-> 4 to the shortest path tree and isolates the ring from the starting point at edgeTo []. From then on, the algorithm continues to run along the ring and reduces the distance to all the vertices encountered until the existence of the ring is detected and the queue is not empty. The ring is saved in edgeTo [], where FindNegativeCycle will find it.

At this point, I believe that everyone on the "C# chart algorithm how to achieve the shortest path" have a deeper understanding, might as well to the actual operation of it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.