最短路徑

1. 最短路徑定義以及性質

定義：

在一副加權有向圖中，從頂點s到頂點t的最短路徑是所有從頂點s到頂點t的路徑中總權重最小的那條路徑。

性質：

路徑具有方向性。

權重不一定等于距離。權重可以是距離、時間、花費等內容，權重最小指的是成本最低。

只考慮連通圖。一副圖中并不是所有的頂點都是可達的，如果s和t不可達，那么它們之間也就不存在最短路徑，所以只考慮連通圖。

最短路徑不一定是唯一的。從一個頂點到達另外一個頂點的權重最小的路徑可能會有很多條，所以只需要找出一條即可。

最短路徑樹：

給定一副加權有向圖和一個頂點s，以s為起點的一棵最短路徑樹是圖的一副子圖，它包含頂點s以及從s可達的所有頂點。這棵有向樹的根結點為s，樹的每條路徑都是有向圖中的一條最短路徑。

2. 最短路徑樹API設計

計算最短路徑樹的經典算法是dijstra算法

類名DijkstraSP

構造方法	public DijkstraSP(EdgeWeightedDigraph G, int s)：根據一副加權有向圖G和頂點s，創建一個計算頂點為s的最短路徑樹對象
成員方法	1.private void relax(EdgeWeightedDigraph G, int v)：松弛圖G中的頂點v 2.public double distTo(int v):獲取從頂點s到頂點v的最短路徑的總權重 3.public boolean hasPathTo(int v):判斷從頂點s到頂點v是否可達 4.public Queue pathTo(int v):查詢從起點s到頂點v的最短路徑中所有的邊
成員變量	1.private DirectedEdge[] edgeTo: 索引代表頂點，值表示從頂點s到當前頂點的最短路徑上的最后一條邊(也就是最短路徑中的連接上一個頂點的邊) 2.private double[] distTo: 索引代表頂點，值從頂點s到當前頂點的最短路徑的總權重 3.private IndexMinPriorityQueue pq:存放樹中頂點與非樹中頂點之間的有效橫切邊

3. 松弛技術

松弛這個詞來源于生活：一條橡皮筋沿著兩個頂點的某條路徑緊緊展開，如果這兩個頂點之間的路徑不止一條，還有存在更短的路徑，那么把皮筋轉移到更短的路徑上，皮筋就可以放松了。

松弛這種簡單的原理剛好可以用來計算最短路徑樹。

在API中，需要用到兩個成員變量edgeTo和distTo，分別存儲邊和權重。一開始給定一幅圖G和頂點s，我們只知道圖的邊以及這些邊的權重，其他的一無所知，此時初始化頂點s到頂點s的最短路徑的總權重disTo[s]=0；頂點s到其他頂點的總權重默認為無窮大，隨著算法的執行，不斷的使用松弛技術處理圖的邊和頂點，并按一定的條件更新edgeTo和distTo中的數據，最終就可以得到最短路勁樹。

邊的松弛：

頂點的松弛是基于邊的松弛完成的，只需要把某個頂點指出的所有邊松弛，那么該頂點就松弛完畢。例如要松弛頂點v，只需要遍歷v的鄰接表，把每一條邊都松弛，那么頂點v就松弛了。

如果把起點設置為頂點0，那么找出起點0到頂點6的最短路徑0->2->7>3->6的過程如下:

4.最短路徑(Dijstra算法)實現

Disjstra算法的實現和Prim算法很類似，構造最短路徑樹的每一步都是向這棵樹中添加一條新的邊，而這條新的邊是有效橫切邊pq隊列中的權重最小的邊

/*** 最短路徑(dijkstra算法)*/ public class DijkstraSP {// 索引代表頂點，值表示從頂點s到當前頂點的最短路徑上的最后一條邊private DirectedEdge[] edgeTo;// 索引代表頂點，值從頂點s到當前頂點的最短路徑的總權重private double[] distTo;// 存放樹中頂點與非樹中頂點之間的有效橫切邊private IndexMinPriorityQueue<Double> pq;// 根據一副加權有向圖G和頂點s，創建一個計算頂點為s的最短路徑樹對象public DijkstraSP(EdgeWeightedDigraph G, int s) {// 初始化edgeTothis.edgeTo = new DirectedEdge[G.V()];// 初始化distTo，并且初始化數組中的內容為無窮大，無窮大即表示不存在這樣的邊this.distTo = new double[G.V()];for (int i = 0; i < distTo.length; i++) {distTo[i] = Double.POSITIVE_INFINITY;}// 初始化有效橫切邊隊列this.pq = new IndexMinPriorityQueue<Double>(G.V());// 默認讓頂點s進入隊列，但s為最短路徑樹的根結點，所以初始化數組distTo為0.0distTo[s] = 0.0;pq.insert(s, 0.0);// 遍歷有效橫切邊隊列while (!pq.isEmpty()) {// 松弛圖G中的頂點relax(G, pq.delMin());}}// 松弛圖G中的頂點vprivate void relax(EdgeWeightedDigraph G, int v) {// 松弛頂點v就是松弛頂點v鄰接表中的每一條邊，遍歷鄰接表for (DirectedEdge e : G.adj(v)) {// 獲取邊e的終點int w = e.to();// 判斷起點s到w的總權重與s經過v到w的總權重，如果大于則修正數據if (distTo[w] > distTo[v] + e.weight()) {// 修改s->w的路徑edgeTo[w] = e;// 修改s到w的總權重distTo[w] = distTo[v] + e.weight();// 如果頂點w已經存在于優先隊列pq中，則重置頂點w的權重if (pq.contains(w)) {pq.changeItem(w, distTo[w]);} else {// 如果頂點w沒有出現在優先隊列pq中，則把頂點w及其權重加入到pq中pq.insert(w, distTo[w]);}}}}// 獲取從頂點s到頂點v的最短路徑的總權重public double distTo(int v) {return distTo[v];}// 判斷從頂點s到頂點v是否可達public boolean hasPathTo(int v) {return distTo[v] < Double.POSITIVE_INFINITY;}// 查詢從起點s到頂點v的最短路徑中所有的邊public Queue<DirectedEdge> pathTo(int v) {// 如果頂點s到v不可達，則返回nullif (!hasPathTo(v)) {return null;}// 創建隊列Queue保存最短路徑的邊Queue<DirectedEdge> edges = new Queue<>();// 從頂點v開始，逆向尋找，一直找到頂點s為止，而起點s為最短路勁樹的根結點，所以 edgeTo[s]=null;DirectedEdge e = null;while (true) {e = edgeTo[v];if (e == null) {break;}edges.enqueue(e);v = e.from();}return edges;} }

總結

以上是生活随笔為你收集整理的最短路径(加权有向图)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。