文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

Dijkstrala算法查找圖中從一個節點到另一個節點的最短路徑，輸出結果是最短路徑以及長度。算法執行的前提條件是權重不能是負數。

起始頂點記為sid，目的節點記為tid。

數組predecessor記錄了最短路徑上一個節點的前驅節點。例如predecessor[3]=5，就是從節點5到節點3的路徑最短。

節點Vertext，保存節點id、當前節點距離sid的最短路徑值。

優先隊列queue按照節點的距離排序，在堆頂的是距離值最小的節點。

每次處理一個節點node的時候，處理其每條邊，計算每條邊的目的節點vertexts[to].dist。如果vertexts[to].dist>vertexts[node.id].dist + 邊的權重，則表示有新的最短路徑，更新，并且將目的節點加入到隊列中。

因為可能有多條邊達到同一個節點，所以隊列中可能有多個元素表示同一個節點，會有多余的操作。解決此問題可以自己寫一個優先隊列，實現更新元素。參考代碼。

import java.util.*;public class Graph {//頂點數量private int v;//鏈接表private LinkedList<Edge> adjacency[];/*** 構造頂點數為v的圖* @param v*/public Graph(int v) {this.v = v;adjacency = new LinkedList[v];for(int i=0;i<v;i++){adjacency[i] = new LinkedList<>();}}/*** 添加一條邊* @param sid* 源節點id* @param tid* 目的節點id* @param weight* 權重*/public void addEdge(int sid, int tid,int weight){Edge edge = new Edge(sid,tid,weight);adjacency[sid].add(edge);}/*** 計算從sid到tid的最短路徑。返回值是經過路徑的節點id* @param sid* @param tid* @return*/public List<Integer> dijkstrala(int sid ,int tid){Vertext[] vertexts = new Vertext[v];for(int i=0; i < v;i++){vertexts[i] = new Vertext(i);}vertexts[sid].dist = 0;//predecessor[i]=得到i的前驅節點int[] predecessor = new int[v];predecessor[sid] = -1;PriorityQueue<Vertext> queue = new PriorityQueue<>(this.v,new Comparator<Vertext>(){public int compare(Vertext o1, Vertext o2){return o1.dist - o2.dist;}});//隊列中可能存在重復節點,會存在多余操作queue.offer(vertexts[sid]);while(! queue.isEmpty()){Vertext node = queue.poll();if(node.id == tid) break;if(adjacency[node.id]!=null){for(Edge edge : adjacency[node.id]){int to = edge.tid;if(vertexts[node.id].dist + edge.weight < vertexts[to].dist){vertexts[to].dist = vertexts[node.id].dist + edge.weight;queue.add(vertexts[to]);predecessor[to] = node.id;}}}}List<Integer> path = new ArrayList<Integer>();if(vertexts[tid].dist < Integer.MAX_VALUE){visitPredecessor(predecessor,tid,path);Collections.reverse(path);}return path;}private void visitPredecessor(int[] predecessor, int tid,List<Integer> path) {path.add(tid);if(predecessor[tid] != -1){visitPredecessor(predecessor,predecessor[tid],path);}}private class Vertext{//編號private int id;//距離private int dist = Integer.MAX_VALUE;public Vertext(int id) {this.id = id;}}private class Edge{private int sid;private int tid;private int weight;public Edge(int sid, int tid, int weight) {this.sid = sid;this.tid = tid;this.weight = weight;}} }

時間復雜度是:O(ElogV)。程序主體是一個while循環，里面是一個for循環。因為每次for循環次數不定，但是所有for循環執行次數之和不會超過E（邊的個數）。換句話說第一個執行E0、第二次執行E1、…第V次執行EV，E0+E1+…+Ev=E。（這里先假設隊列中每個節點只有一個元素）
for循環里面是隊列的入隊、出隊操作。假設隊列中每個節點只有一個元素，那么隊列不會超過V。所以入隊、出隊操作時間復雜度logV。那么總的時間復雜度是O(ElogV)。

隊列中有重復元素，隊列的最大不會超過E。那入隊、出隊操作時間復雜度是logE。$E<=V^2$,$logE<=2logV$。總時間復雜度還是O(E*logV)這個級別。如果在稀疏圖中，這個時間復雜度是可以接受的。但在某些情況下會很糟糕。可以考慮在隊列中更新節點。參考代碼。

總結

以上是生活随笔為你收集整理的Dijkstrala算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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