引言
在Prim算法和Kruskal算法中，我們學習了尋找權重無向圖的最小生成樹的Prim算法：構造最小生成樹的每一步都向生成樹中添加一條新的邊。
今天要學習類似的方法來計算最短路徑——Dijkstra算法。
Dijkstra算法
最短路徑樹中的邊：
edgeTo[v]
的值為樹中連接配接
v
和它的父節點的邊。
最短路徑樹：包含了頂點s到所有可達的頂點的最短路徑
distTo[v]
表示從
s
到
v
的已知最短路徑的長度
Dijkstra算法構造最小生成樹的每一步都向生成樹中添加一條新的邊。首先将
distTo[s]
初始化為0，
distTo[]
中的
其他元素初始化為正無窮。然後将
distTo[]
最小的非樹頂點加入樹中，如此，知道所有的頂點都在樹中。
下面通過執行個體圖解分析一下該算法。
對上篇文章圖論算法——權重有向圖的資料結構中的圖例求解最短路徑樹，過程如下：
初始将
加入優先隊列，然後将
增加到最短路徑樹，同時讓它出隊。它的鄰接點
2
和
4
加入到優先隊列中。從隊列中找到
distTo[]
值最小的為
distTo[2]=0.26
，将對應的邊
0→2
加粗标紅。
從隊列中删除頂點
2
，将0→2添加到樹中，将
7
加入優先隊列。此時
distTo[7] = 0.26 + 0.34 = 0.60
。圖中黑色粗線表示該條邊已經在樹中，如0→2。
從隊列中删除頂點
4
，将0→4添加到樹中，将
5
加入優先隊列。這裡沒有将
7
加入優先隊列是因為目前
distTo[7] = 0.60
小于從0->4,4->7的路徑權重和，意味着邊4->7失效。
從隊列中删除頂點
7
，将2→7添加到樹中，将
3
加入優先隊列。邊7->5失效。
從隊列中删除頂點
5
，将4→5添加到樹中，将
1
加入優先隊列。邊5->7失效。
從隊列中删除頂點
3
，将7→3添加到樹中，将
6
加入優先隊列。
從隊列中删除頂點
1
，将5→1添加到樹中，邊1->3失效。
從隊列中删除頂點
6
，将3→6添加到樹中。
代碼
package com.algorithms.graph;
import com.algorithms.heap.IndexMinPQ;
import com.algorithms.stack.Stack;
/**
* 最短路徑算法
* @author yjw
* @date 2019/6/6/006
*/
public class DijkstraSP {
/**
* edgeTo[v]表示從s到v的最短路徑上的最後一條邊
*/
private DirectedEdge[] edgeTo;
/**
* distTo[v]為從s到v的已知最短路徑的長度
*/
private double[] distTo;
private IndexMinPQ<Double> pq;
public DijkstraSP(EdgeWeightedDigraph g, int s) {
edgeTo = new DirectedEdge[g.vertexNum()];
distTo = new double[g.vertexNum()];
pq = new IndexMinPQ<>(g.vertexNum());
//初始化
for (int v = 0; v < g.vertexNum(); v++) {
distTo[v] = Double.POSITIVE_INFINITY;
}
//将起點到自己的距離聲明為0
distTo[s] = 0.0;
//入隊
pq.insert(s, 0.0);
while (!pq.isEmpty()) {
visit(g, pq.deleteMin());
}
}
private void visit(EdgeWeightedDigraph g, int v) {
for (DirectedEdge e : g.adj(v)) {
int w = e.to();
//distTo[w] > distTo[v] + e.weight()
//意思就是，如果經由v點到w點，權重比之前更小（路徑更短）,則選擇經由v點
if (Double.compare(distTo[w], distTo[v] + e.weight()) > 0) {
//更新從s到w的最短路徑長度
distTo[w] = distTo[v] + e.weight();
//更新邊
edgeTo[w] = e;
//pq中是否含有w
if (pq.contains(w)) {
//更新索引w對應的值，可能會調整索引堆的結構
pq.changeKey(w, distTo[w]);
} else {
//不存在則插入pq
pq.insert(w, distTo[w]);
}
}
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<DirectedEdge> path = new Stack<>();
//從終點開始，不斷的取上一條路徑,是以利用了棧來列印成起點到終點的正序
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
public static void main(String[] args) {
EdgeWeightedDigraph g = new EdgeWeightedDigraph(8);
g.addEdges(0,2,.26,4,.38);
g.addEdge(1,3,.29);
g.addEdge(2,7,.34);
g.addEdge(3,6,.52);
g.addEdges(4,7,.37,5,.35);
g.addEdges(5,1,.32,7,.28,4,.35);
g.addEdges(6,4,.93,0,.58,2,.40);
g.addEdges(7,3,.39,5,.28);
DijkstraSP dsp = new DijkstraSP(g,0);
for (int v = 0; v < g.vertexNum(); v++) {
if (dsp.hasPathTo(v)) {
System.out.print("0 to " + v + ": ");
for (DirectedEdge e : dsp.pathTo(v)) {
System.out.print(e +" ");
}
System.out.println();
}
}
}
}
其中用到的 IndexMinPQ
在一幅含有V個頂點和E條邊的權重有向圖中，使用Dijkstra算法計算根節點為給定起點的最短路徑樹所需的空間與V成正比，時間與ElogV成正比(最壞情況下)