教你在?Java?中實現(xiàn)?Dijkstra?最短路算法的方法
定義
最短路問題的定義為：
下圖左側(cè)是一幅帶權(quán)有向圖，以頂點 0 為起點到各個頂點的最短路徑形成的最短路徑樹如下圖右側(cè)所示：
帶權(quán)有向圖的實現(xiàn)
在實現(xiàn)最短路算法之前需要先實現(xiàn)帶權(quán)有向圖。在上一篇博客 《如何在 Java 中實現(xiàn)最小生成樹算法》 中我們實現(xiàn)了帶權(quán)無向圖，只需一點修改就能實現(xiàn)帶權(quán)有向圖。
帶權(quán)有向邊
首先應(yīng)該實現(xiàn)帶權(quán)有向圖中的邊 DirectedEdge，這個類有三個成員變量：指出邊的頂點 v、邊指向的頂點 w 和邊的權(quán)重 weight。代碼如下所示：
package com.zhiyiyo.graph;
/**
* 帶權(quán)有向邊
*/
public class DirectedEdge {
int v, w;
double weight;
public DirectedEdge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
public int from() {
return v;
public int to() {
return w;
public double getWeight() {
return weight;
@Override
public String toString() {
return String.format("%d->%d(%.2f)", v, w, weight);
}
帶權(quán)有向圖
帶權(quán)有向圖的實現(xiàn)非常簡單，只需將帶權(quán)無向圖使用的 Edge 類換成 DirectedEdge 類，并作出少許調(diào)整即可：
package com.zhiyiyo.graph;
import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;
public class WeightedDigraph {
private final int V;
protected int E;
protected LinkStack<DirectedEdge>[] adj;
public WeightedDigraph(int V) {
this.V = V;
adj = (LinkStack<DirectedEdge>[]) new LinkStack[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkStack<>();
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(DirectedEdge edge) {
adj[edge.from()].push(edge);
E++;
}
public Iterable<DirectedEdge> adj(int v) {
return adj[v];
}
public Iterable<DirectedEdge> edges() {
Stack<DirectedEdge> edges = new LinkStack<>();
for (int v = 0; v < V; ++v) {
for (DirectedEdge edge : adj(v)) {
edges.push(edge);
}
}
return edges;
}
}
最短路算法
API
最短路算法應(yīng)該支持起始點 \(v_s\) 到任意頂點 \(v_t\) 的最短距離和最短路徑的查詢：
package com.zhiyiyo.graph;
import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;
public class WeightedDigraph {
private final int V;
protected int E;
protected LinkStack<DirectedEdge>[] adj;
public WeightedDigraph(int V) {
this.V = V;
adj = (LinkStack<DirectedEdge>[]) new LinkStack[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkStack<>();
}
}
public int V() {
return V;
public int E() {
return E;
public void addEdge(DirectedEdge edge) {
adj[edge.from()].push(edge);
E++;
public Iterable<DirectedEdge> adj(int v) {
return adj[v];
public Iterable<DirectedEdge> edges() {
Stack<DirectedEdge> edges = new LinkStack<>();
for (int v = 0; v < V; ++v) {
for (DirectedEdge edge : adj(v)) {
edges.push(edge);
}
return edges;
}
Dijkstra 算法
我們可以使用一個距離數(shù)組 distTo[] 來保存起始點 \(v_s\) 到其余頂點 \(v_t\) 的最短路徑，且 distTo[] 數(shù)組滿足以下條件：
可以使用 Double.POSITIVE_INFINITY 來表示無窮大，有了這個數(shù)組之后我們可以實現(xiàn) ShortestPath 前兩個方法：
package com.zhiyiyo.graph;
public class DijkstraSP implements ShortestPath {
private double[] distTo;
@Override
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
為了實現(xiàn)保存 \(v_s\) 到 \(v_t\) 的最短路徑，可以使用一個邊數(shù)組 edgeTo[]，其中 edgeTo[v] = e_wv 表示要想到達(dá) \(v_t\)，需要先經(jīng)過頂點 \(v_w\)，接著從 edgeTo[w]獲取到達(dá) \(v_w\) 之前需要到達(dá)的上一個節(jié)點，重復(fù)上述步驟直到發(fā)現(xiàn) edgeTo[i] = null，這時候就說明我們回到了 \(v_s\)。 獲取最短路徑的代碼如下所示：
@Override
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new LinkStack<>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
算法流程
雖然我們已經(jīng)實現(xiàn)了上述接口，但是如何得到 distTo[] 和 edgeTo[] 還是個問題，這就需要用到 Dijkstra 算法了。算法的思想是這樣的：
- 初始化
distTo[]使得除了distTo[s] = 0外，其余的元素都為Double.POSITIVE_INFINITY。同時初始化edgeTo[]的每個元素都是null； - 將頂點 s 的所有相鄰頂點 \(v_j\) 加入集合 \(V'\) 中，設(shè)置
distTo[j] = l_sj即初始化最短距離為鄰邊的權(quán)重； - 從 \(V'\) 中取出距離最短即
distTo[m]最小的頂點 \(v_m\)，遍歷 \(v_m\) 的所有鄰邊 \((v_m, v_w)\)，如果有 \(l_{mw}+l_{sw}<l_{sw}\)，就說明從 \(v_s\) 走到 \(v_m\) 再一步走到 \(v_w\) 距離最短，我們就去更新distTo[m]，同時將 \(v_w\) 添加到 \(V'\) 中（如果 \(v_w\) 不在的話）；
重復(fù)上述過程直到 \(V'\) 變?yōu)榭眨覀兙鸵呀?jīng)找到了所有 \(v_s\) 可達(dá)的頂點的最短路徑。
上述過程中有個地方會影響算法的性能，就是如何從 \(V'\) 中取出最小距離對應(yīng)的頂點 \(v_m\)。如果直接遍歷 \(V'\) 最壞情況下時間復(fù)雜度為 \(O(|V|)\)，如果換成最小索引優(yōu)先隊列則可以將時間復(fù)雜度降至 \(O(\log|V|)\)。
最小索引優(yōu)先隊列
上一篇博客 《如何在 Java 中實現(xiàn)最小生成樹算法》 中介紹了最小堆的使用，最小堆可以在對數(shù)時間內(nèi)取出數(shù)據(jù)集合中的最小值，對應(yīng)到最短路算法中就是最短路徑。但是有一個問題，就是我們想要的是最短路徑對應(yīng)的那個頂點 \(v_m\)，只使用最小堆是做不到這一點的。如何能將最小堆中的距離值和頂點進(jìn)行綁定呢？這就要用到索引優(yōu)先隊列。
索引優(yōu)先隊列的 API 如下所示，可以看到每個元素 item 都和一個索引 k 進(jìn)行綁定，我們可以通過索引 k 讀寫優(yōu)先隊列中的元素。想象一下堆中的所有元素放在一個數(shù)組 pq 中，索引優(yōu)先隊列可以做到在對數(shù)時間內(nèi)取出 pq 的最小值。
package com.zhiyiyo.collection.queue;
/**
* 索引優(yōu)先隊列
*/
public interface IndexPriorQueue<K extends Comparable<K>> {
/**
* 向堆中插入一個元素
*
* @param k 元素的索引
* @param item 插入的元素
*/
void insert(int k, K item);
* 修改堆中指定索引的元素值
* @param item 新的元素值
void change(int k, K item);
* 向堆中插入或修改元素
void set(int k, K item);
* 堆是否包含索引為 k 的元素
* @param k 索引
* @return 是否包含
boolean contains(int k);
* 彈出堆頂?shù)脑夭⒎祷仄渌饕?
* @return 堆頂元素的索引
int pop();
* 彈出堆中索引為 k 為元素
* @return 索引對應(yīng)的元素
K delete(int k);
* 獲取堆中索引為 k 的元素，如果 k 不存在則返回 null
* @return 索引為 k 的元素
K get(int k);
* 獲取堆中的元素個數(shù)
int size();
* 堆是否為空
boolean isEmpty();
}
實現(xiàn)索引優(yōu)先隊列比優(yōu)先隊列麻煩一點，因為需要維護(hù)每個元素的索引。之前我們是將元素按照完全二叉樹的存放順序進(jìn)行存儲，現(xiàn)在可以換成索引，而元素只需根據(jù)索引值 k 放在數(shù)組 keys[k] 處即可。只有索引數(shù)組 indexes[] 和元素數(shù)組 keys[] 還不夠，如果我們想實現(xiàn) contains(int k) 方法，目前只能遍歷一下 indexes[]，看看 k 在不在里面，時間復(fù)雜度是 \(O(|V|)\)。何不多維護(hù)一個數(shù)組 nodeIndexes[]，使得它滿足下述關(guān)系：
如果能在 nodeIndexes[k] 不是 -1，就說明索引 \(k\) 對應(yīng)的元素存在與堆中，且索引 k 在 indexes[] 中的位置為 \(d\)，即有下述等式成立：
有了這三個數(shù)組之后我們就可以實現(xiàn)最小索引優(yōu)先隊列了：
package com.zhiyiyo.collection.queue;
import java.util.Arrays;
import java.util.NoSuchElementException;
/**
* 最小索引優(yōu)先隊列
*/
public class IndexMinPriorQueue<K extends Comparable<K>> implements IndexPriorQueue<K> {
private K[] keys; // 元素
private int[] indexes; // 元素的索引，按照最小堆的順序擺放
private int[] nodeIndexes; // 元素的索引在完全二叉樹中的編號
private int N;
public IndexMinPriorQueue(int maxSize) {
keys = (K[]) new Comparable[maxSize + 1];
indexes = new int[maxSize + 1];
nodeIndexes = new int[maxSize + 1];
Arrays.fill(nodeIndexes, -1);
}
@Override
public void insert(int k, K item) {
keys[k] = item;
indexes[++N] = k;
nodeIndexes[k] = N;
swim(N);
public void change(int k, K item) {
validateIndex(k);
swim(nodeIndexes[k]);
sink(nodeIndexes[k]);
public void set(int k, K item) {
if (!contains(k)) {
insert(k, item);
} else {
change(k, item);
}
public boolean contains(int k) {
return nodeIndexes[k] != -1;
public int pop() {
int k = indexes[1];
delete(k);
return k;
public K delete(int k) {
K item = keys[k];
// 交換之后 nodeIndexes[k] 發(fā)生變化，必須先保存為局部變量
int nodeIndex = nodeIndexes[k];
swap(nodeIndex, N--);
// 必須有上浮的操作，交換后的元素可能比上面的元素更小
swim(nodeIndex);
sink(nodeIndex);
keys[k] = null;
nodeIndexes[k] = -1;
return item;
public K get(int k) {
return contains(k) ? keys[k] : null;
public K min() {
return keys[indexes[1]];
/**
* 獲取最小的元素對應(yīng)的索引
*/
public int minIndex() {
return indexes[1];
public int size() {
return N;
public boolean isEmpty() {
return N == 0;
* 元素上浮
*
* @param k 元素的索引
private void swim(int k) {
while (k > 1 && less(k, k / 2)) {
swap(k, k / 2);
k /= 2;
* 元素下沉
private void sink(int k) {
while (2 * k <= N) {
int j = 2 * k;
// 檢查是否有兩個子節(jié)點
if (j < N && less(j + 1, j)) j++;
if (less(k, j)) break;
swap(k, j);
k = j;
* 交換完全二叉樹中編號為 a 和 b 的節(jié)點
* @param a 索引 a
* @param b 索引 b
private void swap(int a, int b) {
int k1 = indexes[a], k2 = indexes[b];
nodeIndexes[k2] = a;
nodeIndexes[k1] = b;
indexes[a] = k2;
indexes[b] = k1;
private boolean less(int a, int b) {
return keys[indexes[a]].compareTo(keys[indexes[b]]) < 0;
private void validateIndex(int k) {
throw new NoSuchElementException("索引" + k + "不在優(yōu)先隊列中");
}
注意對比最小堆和最小索引堆的 swap(int a, int b) 方法以及 less(int a, int b) 方法，在交換堆中的元素時使用的依據(jù)是元素的大小，交換之后無需調(diào)整 keys[]，而是交換 nodeIndexes[] 和 indexes[] 中的元素。
實現(xiàn)算法
通過上述的分析，實現(xiàn) Dijkstra 算法就很簡單了，時間復(fù)雜度為 \(O(|E|\log |V|)\)：
package com.zhiyiyo.graph;
import com.zhiyiyo.collection.queue.IndexMinPriorQueue;
import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;
import java.util.Arrays;
public class DijkstraSP implements ShortestPath {
private double[] distTo;
private DirectedEdge[] edgeTo;
private IndexMinPriorQueue<Double> pq;
private int s;
public DijkstraSP(WeightedDigraph graph, int s) {
pq = new IndexMinPriorQueue<>(graph.V());
edgeTo = new DirectedEdge[graph.V()];
// 初始化距離
distTo = new double[graph.V()];
Arrays.fill(distTo, Double.POSITIVE_INFINITY);
distTo[s] = 0;
visit(graph, s);
while (!pq.isEmpty()) {
visit(graph, pq.pop());
}
}
private void visit(WeightedDigraph graph, int v) {
for (DirectedEdge edge : graph.adj(v)) {
int w = edge.to();
if (distTo[w] > distTo[v] + edge.getWeight()) {
distTo[w] = distTo[v] + edge.getWeight();
edgeTo[w] = edge;
pq.set(w, distTo[w]);
}
// 省略已實現(xiàn)的方法 ...
}
后記
Dijkstra 算法還能繼續(xù)優(yōu)化，將最小索引堆換成斐波那契堆之后時間復(fù)雜度為 \(O(|E|+|V|\log |V|)\)，這里就不寫了（因為還沒學(xué)到斐波那契堆），以上~~
到此這篇關(guān)于教你在 Java 中實現(xiàn) Dijkstra 最短路算法的方法的文章就介紹到這了,更多相關(guān)Java實現(xiàn) Dijkstra 最短路算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了java異步方式實現(xiàn)登錄的相關(guān)資料，感興趣的朋友可以參考一下2016-05-05
Java編譯錯誤問題:需要class,interface或enum
這篇文章主要介紹了Java編譯錯誤問題:需要class,interface或enum,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-02-02
這篇文章主要給大家總結(jié)介紹了關(guān)于Mybatis-plus批量插入的2種方式,Mybatis-Plus提供了多種方式進(jìn)行批量插入優(yōu)化，文中通過代碼示例將實現(xiàn)的方法介紹的非常詳細(xì),需要的朋友可以參考下2023-08-08
這篇文章主要介紹了idea中如何使用(Undo Commit...)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
大家好，本篇文章主要講的是Spring?Boot整合郵箱發(fā)送郵件實例，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
這篇文章主要介紹了深入理解可視化JVM 故障處理工具，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
這篇文章主要介紹了Java8使用lambda實現(xiàn)Java的尾遞歸的相關(guān)資料,需要的朋友可以參考下2017-10-10
這篇文章主要介紹了JDK 14的新特性:instanceof模式匹配的使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05
這篇文章主要介紹了Java之策略模式比較器案例講解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
Springboot新建項目Spring Initializr Error問題及解決
這篇文章主要介紹了Springboot新建項目Spring Initializr Error問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11