溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“C#圖表算法之最短路徑怎么實現”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C#圖表算法之最短路徑怎么實現”吧!
從一個頂點到達另一個頂點的成本最小的路徑。
我們采用一個一般性的模型，即加權有向圖。在加權有向圖中，每條有向路徑都有一個與之關聯的路徑權重，它是路徑中的所有邊的權重之和。這種重要的度量方式使得我們能夠將這個問題歸納為 “找到有個頂點到達另一個頂點的權重最小的有向路徑”。
單點最短路徑。給定一幅加權有向圖和一個起點 s ，“從 s 到給定的目的頂點 v 是否存在一條有向路徑？如果有，找出最短（總權重最小）的那條路徑”。
相關問題：
1.加權有向圖的 API 和實現以及單點最短路徑的 API；
2.解決邊的權重非負的最短路徑問題的經典 Dijkstra 算法；
3.在無環加權有向圖中解決該問題的一種快速方法，邊的權重可以是負數；
4.適用于一般情況的經典 Bellman-Ford 算法，其中圖可以含有環，邊的權重也可以是負數；
還需要算法來找出負權重的環，以及不含有這種環的加權有向圖中的最短路徑。
1.路徑是有向的。最短路徑需要考慮各條邊的方向。
2.權重不一定等價于距離。
3.并不是所有頂點都是可達的。為了簡化問題，這里的樣圖都是強連通的。
4.負權重會使問題更復雜。
5.最短路徑一般都是簡單的。這里的算法會忽略構成環的零權重邊，因此找到的最短路徑都不會含有環。
6.最短路徑不一定是惟一的。從一個頂點到達另一個頂點的最短路徑可能有多條，我們只要找到其中一條即可。
7.可能存在平行邊和自環。平行邊中權重最小的邊才會被選中，最短路徑也不可能包含自環，除非自環的權重為零，但會忽略它。
我們的重點是單點最短路徑問題，其中給出起點 s ，計算的結果是一棵最短路徑樹（SPT），它包含了頂點 s 到所有可達的頂點的最短路徑。
這樣一棵樹一定存在的：一般來說，從 s 到一個頂點有可能存在兩條長度相等的路徑，可以刪除其中一條路徑的最后一條邊。如此這般，直到從起點到每個頂點都只有一條路徑相連（即一棵樹）。通過構造這棵最短路徑樹，可以為用例提供從 s 到圖中任何頂點的最短路徑，表示方法為一組指向父結點的鏈接。
public class DirectedEdge
{
private int v;//邊的起點
private int w;//邊的終點
private double weight;//邊的權重
public DirectedEdge(int v,int w,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;
}
}
public class EdgeWeightedDigraph
{
private int v;//頂點總數
private int e;//邊的總數
private List<DirectedEdge>[] adj;//鄰接表
public EdgeWeightedDigraph(int v)
{
this.v = v;
this.e = 0;
adj = new List<DirectedEdge>[v];
for (int i = 0; i < v; i++)
{
adj[i] = new List<DirectedEdge>();
}
}
public int V()
{
return v;
}
public int E()
{
return e;
}
public void AddEdge(DirectedEdge _e)
{
adj[_e.From()].Add(_e);
e++;
}
public IEnumerable<DirectedEdge> Adj(int v)
{
return adj[v];
}
public IEnumerable<DirectedEdge> Edges()
{
List<DirectedEdge> edges = new List<DirectedEdge>();
foreach (var _adj in adj)
{
edges.AddRange(_adj);
}
return edges;
}
}
最短路徑樹中的邊。和深度優先搜索，廣度優先搜索一樣，使用一個頂點索引的 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 意味著檢查從 s 到 w 的最短路徑是否是先從 s 到 v，然后再由 v 到 w 。如果是，則根據這個情況更新數據結構的內容。由 v 到 w 的最短路徑是 distTo[v] 與 e.Weight() 之和 —— 如果這個值不小于 distTo[w] ，則這條邊失效并忽略。
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;
}
}下圖是邊的放松操作之后可能出現兩種情況。一種情況是邊失效（左邊），不更新任何數據；另一種情況是 v -> w 就是到達 w 的最短路徑（右邊），這將會更新 edgeTo[w] 和 distTo[w] （這可能會使另一些邊失效，但也可能產生一些新的有效邊）。
實際上，實現會放松從一個給定頂點指出的所有邊。從任意 distTo[v] 為有限值的頂點 v 指向任意 distTo[ ] 為無窮的頂點的邊都是有效的。如果 v 被放松，那么這些有效邊都會被添加到 edgeTo[ ] 中。某條從起點指出的邊將會是第一條被加入 edgeTo[ ] 中的邊。算法會謹慎選擇頂點，使得每次頂點松弛操作都能得出到達某個頂點的更短路徑，最后逐漸找出到達每個頂點的最短路徑。
private void Relax(EdgeWeightDigraph 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;
}
}
}邊的放松一項非常容易實現的重要操作，它是實現最短路徑算法的基礎。同時，它也是理解這個算法的理論基礎并使我們能夠完整地證明算法的正確性。
最短路徑的最優性條件：令 G 為一幅加權有向圖，頂點 s 是 G 中的起點，distTo[ ] 是一個由頂點索引的數組，保存的是 G 中路徑的長度。對于從 s 可達的所有頂點 v ，distTo[v] 的值是從 s 到 v 的某條路徑的長度，對于從 s 不可達的所有頂點 v ,該值為無窮大。當且僅當對于從 v 到 w 的任意一條邊 e ，這些值都滿足 distTo[w] <= distTo[v] + e.Weight() 時（換句話說，不存在有效邊時），它們是最短路徑的長度。
上面最優性條件的一個重要的實際應用是最短路徑的驗證。無論一種算法會如何計算 distTo[ ] ，都只需要遍歷圖中的所有邊一邊并檢查最優性條件是否滿足就能夠知道該數組中的值是否是最短路徑的長度。最短路徑的算法可能會很復雜，因此能夠快速驗證計算的結果就很重要。后面會有 Check（） 方法。
通用最短路徑算法：將 distTo[s] 初始化為 0 ，其他 distTo[ ] 元素初始化為無窮達，繼續如下操作：
放松 G 中的任意邊，直到不存在有效邊為止。
對于任意從 s 可達的頂點 w ，在進行這些操作之后，distTo[w] 的值即為從 s 到 w 的最短路徑的長度且 edgeTo[w] 的值即為該路徑上的最后一條邊。
證明：放松邊 v -> w 必然會將 distTo[w] 的值設為從 s 到 w 的某條路徑的長度且將 edgeTo[w] 設為該路徑上的最后一條邊。對于從 s 可達的任意頂點 w，只要 distTo[w] 仍然是無窮達，到達 w 的最短路徑上的某條邊肯定仍然是有效的，因此算法的操作會不斷繼續，直到由 s 可達的每個頂點的 distTo[ ] 值均變為到達頂點的某條路徑的長度。對于已經找到最短路徑的任意頂點 v ，在算法的計算過程中 distTo[v] 的值都是從 s 到 v 的某條路徑的長度且必然是單調遞減的。因此，它遞減的次數必然是有限的（每切換一條 s 到 v 簡單路徑就遞減一次）。當不存在有效邊的時候，最優性條件就成立了。
將最優性條件和通用算法放在一起討論的關鍵原因是，通用算法并沒有指定邊的放松順序。因此，要證明這些算法都能通過計算得到最短路徑，只需要證明它們都會放松所有的邊直到所有邊都失效即可。
在最小生成樹中，分享了尋找加權無向圖中的最小生成樹的 Prim 算法：構造最小生成樹的每一步都向這棵樹中添加一條新的邊。Dijkstra 算法采用了類似的方法來計算最短路徑樹。首先將 distTo[s] 初始化為 0，distTo[ ] 中的其他元素初始化為正無窮大。然后將distTo[ ]最小的非樹頂點放松并加入樹中，如此這般，直到所有的頂點都在樹中或者所有的非樹頂點的distTo[ ] 值均為無窮大。
Dijkstra 算法能夠解決邊權重非負的加權有向圖的單起點最短路徑問題。證明：如果 v 是從起點可達的，那么所有 v -> w 的邊都只會被放松一次。當 v 被放松時，必有distTo[w] <=distTo[v] + e.Weight() 。該不等式在算法結束前都會成立，因此 distTo[v] 則不會改變（因為邊的權重非負且在每一步中算法都會選擇 distTo[ ] 最小的頂點，之后的放松操作不可能使任何 distTo[ ] 的值小于 distTo[v]）。因此，在所有從 s 可達的頂點均被添加到樹中之后，最短路徑的最優性條件成立。
要實現Dijkstra 算法，除了 distTo[ ] 和 edgeTo[ ] 數組之外還需要一條索引優先隊列 pq ，以保存需要被放松的頂點。 IndexMinPQ 可以將索引和鍵（優先級）關聯起來并且可以刪除并返回優先級最低的索引。在這里，只要將頂點 v 和 distTo[v] 關聯起來就立即可以得到Dijkstra 算法的實現。edgeTo[ ] 中的元素所對應的可達頂點構成了一棵最短路徑樹。
如下圖，根據算法的證明，已知樹節點所對應的 distTo[ ] 值均為最短路徑的長度。對于優先隊列中的任意頂點 w ，distTo[w] 是從 s 到 w 的最短路徑的長度，該路徑上的中間頂點在樹中且路徑結束于橫切邊 edgeTo[w] 。優先級最小的頂點的 distTo[ ] 值就是最短路徑的權重，它不會小于已經放松過的任意頂點的最短路徑的權重，也不會大于還未被放松過的任意頂點的最短路徑的權重。這個頂點就是下一個要被放松的頂點。所有從 s 可達的頂點都會按照最短路徑的權重順序被放松。
public class DijkstraSP
{
private DirectedEdge[] edgeTo;
private double[] distTo;
private IndexMinPQ<Double> pq;
public DijkstraSP(EdgeWeightedDigraph G,int s)
{
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
pq = new IndexMinPQ<double>(G.V());
for (int v = 0; v < G.V(); v++)
{
distTo[v] = Double.MaxValue;
}
distTo[0] = 0.0;
pq.Insert(s,0.0);
while (!pq.IsEmpty())
{
Relax(G,pq.DelMIn());
}
}
private void Relax(EdgeWeightedDigraph G, int v)
{
foreach (var 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 (pq.Contains(w))
{
pq.Change(w, distTo[w]);
}
else
{
pq.Insert(w,distTo[w]);
}
}
}
}
}軌跡
1.將頂點 0 添加到樹中，將頂點 2 和 4 加入優先隊列；
2.從優先隊列中刪除頂點 2，將 0 -> 2 添加到樹中，將頂點 7 加入優先隊列；
3.從優先隊列中刪除頂點 4，將 0 -> 4 添加到樹中，將頂點 5 加入優先隊列，邊 4 -> 7 失效；
4.從優先隊列中刪除頂點 7，將2 -> 7添加到樹中，將頂點 3 加入到優先隊列，邊 7 -> 5 失效；
5.從優先隊列中刪除頂點 5，將 4 -> 5添加到樹中，將頂點 1 加入優先隊列，邊 5 -> 7 失效；
6.從優先隊列中刪除頂點 1，將 5 -> 1添加到樹中，邊 1 -> 3 失效；
7.從優先隊列中刪除頂點 6，將 3 -> 6 添加到樹中。
算法按照頂點到起點的最短路徑的長度的增序將它們添加到最短路徑樹中。
在一幅含有 V 個頂點和 E 條邊的加權有向圖中，使用 Dijkstra 算法計算結點為給定起點的最短路徑樹所需的空間與 V 成正比，時間與 ElogV 成正比（最壞情況下）。
只需對Dijkstra 算法的實現稍作修改就能解決這個問題的其他版本。例如，加權無向圖中的單點最短路徑。
如果將無向圖看做有向圖，創建一幅由相同頂點構成的加權有向圖，且對于無向圖中的每條邊，相應地創建兩條方向不同的有向邊。有向圖中的路徑和無向圖中的路徑存在一一對應的關系，路徑的權重也是相同的——最短路徑的問題是等價的。
給定一幅加權有向圖以及一個起點 s 和一個終點 t，找到從 s 到 t 的最短路徑。
要解決這個問題，可以使用Dijkstra 算法并在從優先隊列中取到 t 之后終止搜索。
下面的代碼解決了任意頂點對之間的最短路徑問題，所需的時間和空間都與 EVlogV 成正比。它構造了DijkstraSP 對象的數組，每個元素都將相應的頂點作為起點。在用例進行查詢時，代碼會訪問起點所對應的單點最短路徑對象并將目的頂點作為參數進行查詢。
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<DirectedEdge> Path(int s, int t)
{
return all[s].Path(t);
}
public double Dist(int s, int t)
{
return all[s].Dist(t);
}
}在頂點為平面上的點且邊的權重于頂點歐幾里得間距成正比的圖中，解決單點，給定兩點和任意頂點對之間的最短路徑。
下圖是Dijkstra 算法在處理歐幾里得圖時用若干不同的起點產生最短路徑樹的過程。
下面，將會考慮加權無環圖中的最短路徑算法并且將在線性時間內解決該問題。然后是負權重的加權有向圖中的最短路徑問題，Dijkstra 算法并不適用于這種情況。
許多應用中的加權有向圖都是不含有有向環的。現在來看一種比Dijkstra 算法更快，更簡單的在無環加權有向圖中找出最短路徑的算法，它的特點是：
1.能夠在線性時間內解決單點最短路徑的問題；
2.能夠處理負權重的邊；
3.能夠解決相關的問題，例如找出最長的路徑。
這種算法是在有向圖中學過的無環有向圖的拓撲排序算法的簡單擴展。
特別的是，只要將頂點的放松和拓撲排序結婚起來，馬上就能夠得到一種解決無環加權有向圖中的最短路徑問題 的算法。首先，將 distTo[s] 初始化為 0 ，其他 distTo[ ] 元素初始化為無窮大，然后一個一個地按照拓撲順序放松所有頂點。
命題 S ：按照拓撲順序放松頂點，就能在和 E+V 成正比的時間內解決無環加權有向圖的單點最短路徑問題。每條邊 v --> w 都只會被放松一次。當 v 被放松時，得到：distTo[w] <= distTo[v] + e.Weight() 。在算法結束前該不等式都成立，因為distTo[v] 是不會變化的（因為是按照拓撲順序放松頂點，在 v 被放松之后算法不會再處理任何指向 v 的邊）而distTo[w] 只會變小（任何放松操作都只會減小 distTo[ ] 中元素的值）。因此，在所有從 s 可達的頂點都被加入到樹中后，最短路徑的最優性條件成立。
namespace ShortestPaths
{
/// <summary>
/// 基于拓撲的無環加權有向圖的最短路徑算法
/// </summary>
public class AcyclicSP
{
private DirectedEdge[] edgeTo;
private double[] distTo;
public AcyclicSP(EdgeWeightedDigraph G, int s)
{
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
for (var i = 0; i < G.V(); i++)
{
distTo[i] = Double.MaxValue;
}
distTo[0] = 0;
Topological top = new Topological(G);
foreach (var v in top.Order())
{
Relax(G,v);
}
}
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;
}
}
}
}
}示例軌跡：
1.用深度優先搜索得到圖的頂點的拓撲排序 5 1 3 6 4 7 0 2；
2.將頂點 5 和從它指出的所有邊添加到樹中；
3.將頂點 1 和邊 1->3 添加到樹中；
4.將頂點 3 和邊 3->6 添加到樹中，邊 3->7 失效；
5.將頂點 6 和邊 6->2, 6->0 添加到樹中，邊 6->4 失效；
6.將頂點 4 和邊 4->0 添加到樹中，邊 4->7 和 6->0 失效；
7.將頂點 7 和邊 7->2 添加到樹中，邊 6->2 失效；
8.將頂點 0 添加到樹中，邊 0->2 失效；
9.將頂點 2 添加到樹中。
命題 S 很重要，因為它的 “無環” 能夠極大地簡化問題的論斷。對于最短路徑問題，基于拓撲排序的方法比 Diijkstra 算法快的倍數與Diijkstra 算法中所有優先隊列操作的總成本成正比。另外，命題 S 的證明和邊的權重是否非負無關，因此無環加權有向圖不會受任何限制。用這個特點可以解決邊的負權重問題。
考慮在無環加權有向圖中尋找最長路徑的問題，邊的權重可正可負。
實現：復制原始無環加權有向圖得到一個副本并將副本中的所有邊的權重變為負值。這樣，副本中的最短路徑即為原圖中的最長路徑。要將最短路徑問題的答案轉換為最長路徑問題的答案，只需將方案中的權重變為正值即可。所需時間與 E+V 成正比。
軌跡：
在一般的加權有向圖（邊的權重可能為負）中尋找最長簡單路徑的已知最好算法在最壞情況下所需的時間是指數級別。出現環的可能性似乎使這個問題的難度以指數級別增長。
這里再次考慮有向圖中出現過的任務調度問題，這次解決一下調度問題：
優先級限制下的并行任務調度。給定一組需要完成的任務和每個任務所需的時間，以及一組關于任務完成的先后次序的優先級限制。在滿足限制條件的前提下應該如何在若干相同的處理器（數量不限）安排任務并在最短時間內完成所有任務？
有向圖中調度的模型默認只有單個處理器：將任務按照拓撲順序排序，完成任務的總耗時就是所有任務所需要的總時間。現在假設有足夠多的處理器并能夠同時處理任意多的任務，受到的只有優先級的限制。
存在一種線性時間的算法 —— 一種叫做“關鍵路徑”的方法能夠證明這個問題與無環加權有向圖中的最長路徑問題是等價的。
假設任意可用的處理器都能在任務所需的時間內完成它，那么我們的重點就是盡早安排每一個任務。例如，下面表給出了一個任務調度問題。下圖給出了解決方案，顯示了這個問題所需的最短時間 173.0 。
這份調度方案滿足了所有限制條件，沒有其他調度方案比這耗時更少，因為任務必須按照 0 -> 9 -> 6 -> 8 -> 2 的順序完成。這個順序就是這個問題的關鍵路徑。由優先級限制指定的每一列任務都代表了調度方案的一種可能的時間下限。如果將一系列任務的長度定義為完成所有任務的最早可能時間，那么最長的任務序列就是問題的關鍵路徑，因為在這份任務序列中任何任務的啟動延遲都會影響到整個項目的完成時間。
解決：
解決并行任務調度問題的關鍵路徑方法的步驟如下：創建一幅無環加權有向圖，其中包含一個起點 s 和一個終點 t 且每個人物都對應著兩個頂點（一個起始頂點和一個結束頂點。對于每個任務都有一條從它的起始頂點指向結束頂點的邊，邊的權重為任務所需要的時間。對于每條優先級限制 v -> w ，添加一條從 v 的結束頂點指向 w 的起始頂點的權重為零的邊。我們還需要為每個任務添加一條從起點指向該任務的起始頂點的權重為零的邊以及一條從該任務的結束頂點到終點的權重為零的邊。這樣，每個任務預計的開始時間即為從起點到它的起始頂點的最長距離。
接下來就是在無環加權有向圖中尋找一個最長路徑——關鍵路徑。
static void Main(string[] args)
{
string[] strs = File.ReadAllLines(@"jobs.txt");
var N = Int32.Parse(strs[0]);//任務數
EdgeWeightedDigraph G = new EdgeWeightedDigraph(2*N+2);//2*N+2 為節點數，每個任務兩個我節點，再加上起始兩個節點
int s = 2 * N, t = 2 * N + 1;//起點和終點
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 個時間單位）-> 6（21 個時間單位）-> 8（32 個時間單位）-> 2，2 號任務最早也只能在 0 號任務啟動后的 123 個時間單位之內開始。
相對最后期限限制下的并行任務調度問題是一個加權有向圖中的最短路徑問題（可能存在環和負權重邊）。根據任務調度的描述構造加權有向圖，為每條最后期限限制添加一條邊：如果任務 v 必須在任務 w 啟動后的 d 個單位時間內開始，則添加條從 v 指向 w 的負權重為 d 的邊。將所有邊的權重取反即可將該問題轉化為一個最短路徑問題。如果存在可行的調度方案，證明也就完成了。判斷一個調度方案是否可行也是計算的一部分。
上面的示例說明了負權重的邊在實際應用的模型中也能起到重要作用。它說明，如果能夠有效解決負權重邊的最短路徑問題，那就能夠找到相對最后期限限制下的并行任務調度問題的解決方案。之前學過的算法都無法完成這個任務：Dijkstra 算法只適用于正權重的邊，AcylicSP 算法要求有向圖是無環的。下面解決含有負權重且不一定是無環的有向圖中的最短路徑問題。
上面討論的最后期限限制下的任務調度問題告訴我們負權重的邊不僅僅是一個數學問題。相反，它能夠極大地擴展解決最短路徑問題模型的應用范圍。接下來，考慮既可能含有環也可能含有負權重的邊的加權有向圖中的最短路徑算法。
開始之前，先學習一下這種有向圖的基本性質以及更新我們對最短路徑的認識。下圖展示的是負權重的邊對有向圖中的最短路徑的影響。也許最明顯的改變就是當存在負權重的邊時，權重較小的路徑含有的邊可能會比權重較大的路徑更多。在只存在正權重的邊時，我們的重點在于尋找近路；但當存在負權重的邊時，我們可能會為了經過負權重的邊而繞遠。這種效應使得我們要將查找 “最短” 路徑的感覺轉變為對算法本質的理解。因此需要拋棄直覺并在一個簡單，抽象的層面上考慮這個問題。
第一個想法是先找到權重最小（最小負值）的邊，然后將所有邊的權重加上這個負值的絕對值，這樣原有向圖就轉變成了一幅不含有負權重邊的有向圖。但這種做法不會解決任何問題，因為新圖中的最短路徑和原圖中的最短路徑毫無關系。
第二個想法是改造 Dijkstra 算法。這種算法最根本的缺陷在于原算法的基礎在于根據距離起點的遠近依次檢查路徑，添加一條邊會使路徑變得更長。但添加任意負權重的邊只會使得路徑更短。
當我們在研究含有負權重邊的有向圖時，如果該圖中含有一個權重為負的環，那么最短路徑的概念就失去意義了。如下圖，除了邊 5 -> 4 的權重為 -0.66 外，它和前面的示例完全相同。這里，環 4-> 7 -> 5 -> 4 的權重為：
0.37 + 0.28 - 0.66 = -0.01；
我們只要圍著這個環兜圈子就能得到權重任意短的路徑！注意，有向環的所有邊的權重并不一定都必須是負的，只要權重之和是負的即可。
定義：加權有向圖中的負權重環是一個總權重為負的有向環。
現在，假設從 s 到可達的某個頂點 v 的路徑上的某個頂點在一個負權重環上。在這種情況下，從 s 到 v 的最短路徑是不可能存在的，因為可以利用這個負權重環構造權重任意小的路徑。換句話說，在負權重環存在的情況下，最短路徑問題是沒有意義的。
當且僅當加權有向圖中至少存在一條從 s 到 v 的有向路徑且所有從 s 到 v 的有向路徑上的任意頂點都不存在于任何負權重環中時，s 到 v 的最短路徑才是存在的。
注意，要求最短路徑上的任意頂點都不存在于負權重環中意味著最短路徑是簡單的，而且與正權重邊的圖一樣都能夠得到此類頂點的最短路徑樹。
無論是否存在負權重環，從 s 到可達的其他頂點的一條最短的簡單路徑都是存在的。為什么不定義最短路徑以方便尋找呢？但是，已知解決這個問題的最好算法在最壞情況下所需的時間是指數級別的（后面會降到）。一般來說，這種問題太難了，只會研究它的簡單版本。
因此，一個定義明確且可以解決加權有向圖最短路徑的算法要能夠：
1.對于從起點不可達的頂點，最短路徑為正無窮；
2.對于從起點可達但路徑上的某個頂點屬于一個負權重環的頂點，最短路徑為負無窮；
3.對于其他所有頂點，計算最短路徑的權重。
從文章的開始到現在，我們為最短路徑問題加上了各種限制，使得我們能夠找到解決相應問題的辦法。首先，我們不允許負權重邊的存在；其次不接受有向環。現在我們放寬所有這些條件并重點解決一般有向圖中的問題。
負權重環的檢測。給定的加權有向圖中含有負權重環嗎？如果有，找到它。
負權重環不可達時的單點最短路徑。給定一幅加權有向圖和一個起點 s 且從 s 瓦法到達任何負權重環。是否存在一條從 s 到給定的頂點 v 的有向路徑？如果有，找出最短的那條路徑。
總結：盡管在含有環的有向圖中最短路徑是一個沒有意義的問題，而且也無法有效解決在這種有向圖中高效找出最短簡單路徑的問題，在實際應用中仍然需要能夠識別其中的負權重環。例如，在最后期限限制下的任務調度問題中，負權重環的出現可能相對較少；限制條件和最后期限都是從現實世界中的實際限制得來的，因此負權重環大多可能來自于問題陳述中的錯誤。找出負權重環，改正相應的錯誤，找到沒有負權重環問題的調度方案才是解決問題的正確方式。在其他情況下，找到負權重環就是計算的目標。
Bellman-Ford 算法能夠有效解決這些問題并且同樣適用于正權重邊的有向圖。
Bellman-Ford 算法。在任意含有 V 個頂點的加權有向圖中給定起點 s ，從 s 無法到達任何負權重環，以下算法能夠解決其中的單點最短問題：將 distTo[s] 初始化為 0 ，其他 distTo[ ] 元素初始化為無窮大。以任意順序放松有向圖所有邊，重復 V 輪。
這個方法非常通用，因為它沒有指定邊的放松順序。下面將注意力集中在一個通用性稍遜的方法上，其中只放松從任意頂點指定的所有邊（任意順序）：
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 條邊且只需稍作修改即可使算法在一般情景下更高效。
其實，根據經驗我們很容易知道在任意一輪中許多邊的放松都不會成功：只有上一輪中的 distTo[ ] 值發生變化的頂點指出的邊才能夠改變其他 distTo[ ] 元素的值。為了記錄這樣的頂點，我們使用了一條 FIFO 隊列。算法在處理正權重標準樣圖中進行的操作軌跡如下圖，在圖中，左側是每一輪中隊列中的有效頂點（紅色），緊接著是下一輪中的有效頂點（黑色）。首先將起點加入隊列，然后按照以下步驟計算最短路徑樹：
1.放松邊 1 -> 3 并將頂點 3 加入隊列；
2.放松邊 3 -> 6 并將頂點 6 加入隊列；
3.放松邊 6 -> 4, 6 -> 0 和 6 -> 2 并將頂點 4,0 和 2 加入隊列；
4.放松邊 4 -> 7，4 -> 5 并將頂點 7 和 5 加入隊列。放松已經失效的邊 0 -> 4 和 0 -> 2。然后再放松邊 2 -> 7 （并重新為 4 -> 7 著色）。
5.放松邊 7 -> 5 （并重新為 4 -> 5 著色）但不將頂點 5 加入隊列（它已經在隊列中了）。放松已經失效的邊 7 -> 3。然后放松已經失效的邊 5 -> 1， 5 -> 4 和 5 -> 7。此時隊列為空。
根據上面的描述實現 Bellman-Ford 算法所需的代碼很少，它基于以下兩種其他的數據結構：
1.一條用來保存即將被放松的頂點的隊列 Queue；
2.一個由頂點索引的 bool 數組 OnQ[ ] ，用來指示頂點是否已經存在于隊列中，以防止將頂點重復加入隊列。
首先，將起點 s 加入隊列中，然后進入一個循環，其中每次都從隊列中取一個頂點并將其放松。要將一個頂點插入隊列，需要修改之前的 Relax 方法實現，以便將被成功放松的邊所指向的頂點加入隊列中。這些數據結構能夠保證：
1.隊列中不會出現重復的頂點；
2.在某一輪中，改變了 edgeTo[ ] 和 distTo[ ] 的值得所有頂點都會在下一輪中處理。
要完整地實現該算法，我們就需要保證在 V 輪后算法能夠終止。實現它的一種方法是顯式記錄放松的輪數。下面的代碼使用了另一種算法，后面詳細說：它會在有向圖的 edgeTo[ ] 中檢測是否存在負權重環，如果找到則結束運行。
public class BellmanFordSP
{
private double[] distTo;//從起點到某個頂點的路徑長度
private DirectedEdge[] edgeTo;//從起點到某個頂點的最后一條邊
private bool[] onQ;//該頂點是否存在于隊列中
private Queue<int> queue;//正在被放松的頂點
private int cost;//relax 的調用次數
private IEnumerable<DirectedEdge> cycle;//edgeTo[] 中的是否有負權重環
public BellmanFordSP(EdgeWeightedDigraph G,int s)
{
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
onQ = new bool[G.V()];
queue = new Queue<int>();
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();
}
}
//查找負權重環
private void FindNegativeCycle()
{
throw new NotImplementedException();
}
}Relax 方法將成功放松的邊指向的所有頂點加入到一條 FIFO 隊列中（隊列中不出現重復的頂點）并周期性地檢查 edgeTo[ ] 表示的子圖中是否存在負權重環。
對于任意含有 V 個頂點的加權有向圖和給定的起點 s ，在最壞情況下基于隊列的 Bellman-Ford 算法解決最短路徑問題（或者找到從 s 可達的負權重環）所需的時間與 EV 成正比，空間和 V 成正比。
如果不存在從 s 可達的負權重環，算法會在進行 V-1 輪放松操作后結束（因為所有最短路徑含有的邊數都小于 V-1）。如果的確存在一個從 s 可達的負權重環，那么隊列永遠不可能為空。在第 V 輪放松之后，edgeTo[ ] 數組必然會包含一條含有一個環的路徑（從某個頂點 w 回到它自己）且該環的權重必然是負的。因為 w 會在路徑上出現兩次且 s 到 w 的第二次出現處的路徑長度小于 s 到 w 的第一次出現的路徑長度。在最壞情況下，該算法的行為和通用算法相似并會將所有的 E 條邊全部放松 V 輪。
基于隊列的 Bellman-Ford 算法對于相同的問題比較路徑長度的次數少于 Disjkstra 算法。
下圖顯示了Bellman-Ford 算法在處理含有負權重邊的有向圖的軌跡。首先將起點加入隊列 queue ，然后按照以下步驟計算最短路徑樹。
1.放松邊 0 -> 2 和 0 -> 4 并將頂點 2，4 加入隊列。
2.放松邊 2 -> 7 并將頂點 7 加入隊列。放松邊 4 -> 5 并將頂點 5 加入隊列。然后放松失效的邊 4 -> 7。
3.放松邊 7 -> 3 和 5 -> 1 并將頂點 3 和 1 加入隊列。放松失效的邊 5 -> 4 和 5 -> 7 。
4.放松邊 3 -> 6 并將頂點 6 加入隊列。放松失效的邊 1 -> 3 。
5.放松邊 6 -> 4 并將頂點 4 加入隊列。這條負權重的邊使得到頂點 4 的路徑變短，因此它的邊需要被再次放松。從起點到頂點 5 和 1 的距離已經失效并會在下一輪修正。
6.放松邊 4 -> 5 并將頂點 5 加入隊列。放松失效的邊 4 -> 7 。
7.放松邊 5 -> 1 并將頂點 1 加入隊列。放松失效的邊 5 -> 4 和 5 -> 7 。
8.放松失效的邊 1 -> 3 。隊列為空。
在這個例子中，最短路徑樹就是一條從頂點 0 到頂點 1 的路徑。從頂點 4，5 和 1 指出的所有邊都被放松了兩次。
實現 BellmanFordSP 會檢測負權重環來避免陷入無限的循環中。我們也可以將這段檢測代碼獨立出來使得用例可以檢查并得到負權重環。在 BellmanFordSP 的構造函數運行之后，在將所有邊放松 V 輪之后當且僅當隊列非空時有向圖中才存在從起點可達的負權重環。如果是這樣， edgeTo[ ] 數組所表示的子圖必然含有這個負權重環。我們修改有向圖中的 DirectedCycle 類來在加權有向圖中尋找環。這種檢查的成本分為以下幾個部分：
1.添加一個變量 cycle 和一個私有函數FindNegativeCycle 。如果找到負權重環，該方法會將 cycle 的值設為含有環中所有邊的一個迭代器（如果沒有找到則設為 null）。
2.每調用 V 次 Relax 方法后即調用FindNegativeCycle 方法。
這種方法能夠保證構造函數中的循環必然終止。另外，用例可以調用HasNegativeCycle 來判斷是否存在從起點可達的負權重環。
//查找負權重環
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<DirectedEdge> NegativeCycle()
{
return cycle;
}下圖是 Bellman-Ford 算法在一幅含有負權重環的有向圖中的運行軌跡。頭兩輪放松操作與前面的例子一樣，在第三輪中，算法放松了邊 7 -> 3 和 5 -> 1 并將頂點 3 和 1 加入隊列后開始放松負權重邊 5 -> 4 。在這次放松操作中算法發現了一個負權重環 4 -> 5 -> 4 。它將5 -> 4 加入最短路徑樹中并在 edgeTo[ ] 將環和起點隔離起來。從這時開始，算法沿著環繼續運行并減少到達所遇到的所有頂點的距離，直至檢測到環的存在，此時隊列非空。環被保存在 edgeTo[ ] 中，FindNegativeCycle 會在其中找到它。
到此，相信大家對“C#圖表算法之最短路徑怎么實現”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
