教你在?Java?中實(shí)現(xiàn)?Dijkstra?最短路算法的方法

更新時(shí)間：2022年04月08日 08:08:35 作者：之一Yo

這篇文章主要教你在?Java?中實(shí)現(xiàn)?Dijkstra?最短路算法的方法,在實(shí)現(xiàn)最短路算法之前需要先實(shí)現(xiàn)帶權(quán)有向圖，文章中給大家介紹的非常詳細(xì)，需要的朋友可以參考下

定義

最短路問題的定義為：

下圖左側(cè)是一幅帶權(quán)有向圖，以頂點(diǎn) 0 為起點(diǎn)到各個(gè)頂點(diǎn)的最短路徑形成的最短路徑樹如下圖右側(cè)所示：

帶權(quán)有向圖的實(shí)現(xiàn)

在實(shí)現(xiàn)最短路算法之前需要先實(shí)現(xiàn)帶權(quán)有向圖。在上一篇博客《如何在 Java 中實(shí)現(xiàn)最小生成樹算法》中我們實(shí)現(xiàn)了帶權(quán)無向圖，只需一點(diǎn)修改就能實(shí)現(xiàn)帶權(quán)有向圖。

帶權(quán)有向邊

首先應(yīng)該實(shí)現(xiàn)帶權(quán)有向圖中的邊 DirectedEdge，這個(gè)類有三個(gè)成員變量：指出邊的頂點(diǎn) v、邊指向的頂點(diǎn) 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)有向圖的實(shí)現(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)該支持起始點(diǎn) \(v_s\) 到任意頂點(diǎn) \(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 算法

我們可以使用一個(gè)距離數(shù)組 distTo[] 來保存起始點(diǎn) \(v_s\) 到其余頂點(diǎn) \(v_t\) 的最短路徑，且 distTo[] 數(shù)組滿足以下條件：

可以使用 Double.POSITIVE_INFINITY 來表示無窮大，有了這個(gè)數(shù)組之后我們可以實(shí)現(xiàn) ShortestPath 前兩個(gè)方法：

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;
}

為了實(shí)現(xiàn)保存 \(v_s\) 到 \(v_t\) 的最短路徑，可以使用一個(gè)邊數(shù)組 edgeTo[]，其中 edgeTo[v] = e_wv 表示要想到達(dá) \(v_t\)，需要先經(jīng)過頂點(diǎn) \(v_w\)，接著從 edgeTo[w]獲取到達(dá) \(v_w\) 之前需要到達(dá)的上一個(gè)節(jié)點(diǎn)，重復(fù)上述步驟直到發(fā)現(xiàn) edgeTo[i] = null，這時(shí)候就說明我們回到了 \(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)實(shí)現(xiàn)了上述接口，但是如何得到 distTo[] 和 edgeTo[] 還是個(gè)問題，這就需要用到 Dijkstra 算法了。算法的思想是這樣的：

初始化 distTo[] 使得除了 distTo[s] = 0 外，其余的元素都為 Double.POSITIVE_INFINITY。同時(shí)初始化 edgeTo[] 的每個(gè)元素都是 null；
將頂點(diǎn) s 的所有相鄰頂點(diǎn) \(v_j\) 加入集合 \(V'\) 中，設(shè)置 distTo[j] = l_sj 即初始化最短距離為鄰邊的權(quán)重；
從 \(V'\) 中取出距離最短即 distTo[m] 最小的頂點(diǎn) \(v_m\)，遍歷 \(v_m\) 的所有鄰邊 \((v_m, v_w)\)，如果有 \(l_{mw}+l_{sw}<l_{sw}\)，就說明從 \(v_s\) 走到 \(v_m\) 再一步走到 \(v_w\) 距離最短，我們就去更新 distTo[m]，同時(shí)將 \(v_w\) 添加到 \(V'\) 中（如果 \(v_w\) 不在的話）；

重復(fù)上述過程直到 \(V'\) 變?yōu)榭?，我們就已?jīng)找到了所有 \(v_s\) 可達(dá)的頂點(diǎn)的最短路徑。

上述過程中有個(gè)地方會影響算法的性能，就是如何從 \(V'\) 中取出最小距離對應(yīng)的頂點(diǎn) \(v_m\)。如果直接遍歷 \(V'\) 最壞情況下時(shí)間復(fù)雜度為 \(O(|V|)\)，如果換成最小索引優(yōu)先隊(duì)列則可以將時(shí)間復(fù)雜度降至 \(O(\log|V|)\)。

最小索引優(yōu)先隊(duì)列

上一篇博客《如何在 Java 中實(shí)現(xiàn)最小生成樹算法》中介紹了最小堆的使用，最小堆可以在對數(shù)時(shí)間內(nèi)取出數(shù)據(jù)集合中的最小值，對應(yīng)到最短路算法中就是最短路徑。但是有一個(gè)問題，就是我們想要的是最短路徑對應(yīng)的那個(gè)頂點(diǎn) \(v_m\)，只使用最小堆是做不到這一點(diǎn)的。如何能將最小堆中的距離值和頂點(diǎn)進(jìn)行綁定呢？這就要用到索引優(yōu)先隊(duì)列。

索引優(yōu)先隊(duì)列的 API 如下所示，可以看到每個(gè)元素 item 都和一個(gè)索引 k 進(jìn)行綁定，我們可以通過索引 k 讀寫優(yōu)先隊(duì)列中的元素。想象一下堆中的所有元素放在一個(gè)數(shù)組 pq 中，索引優(yōu)先隊(duì)列可以做到在對數(shù)時(shí)間內(nèi)取出 pq 的最小值。

package com.zhiyiyo.collection.queue;
/**
 * 索引優(yōu)先隊(duì)列
 */
public interface IndexPriorQueue<K extends Comparable<K>> {
    /**
     * 向堆中插入一個(gè)元素
     *
     * @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);
     * 獲取堆中的元素個(gè)數(shù)
    int size();
     * 堆是否為空
    boolean isEmpty();
}

實(shí)現(xiàn)索引優(yōu)先隊(duì)列比優(yōu)先隊(duì)列麻煩一點(diǎn)，因?yàn)樾枰S護(hù)每個(gè)元素的索引。之前我們是將元素按照完全二叉樹的存放順序進(jìn)行存儲，現(xiàn)在可以換成索引，而元素只需根據(jù)索引值 k 放在數(shù)組 keys[k] 處即可。只有索引數(shù)組 indexes[] 和元素?cái)?shù)組 keys[] 還不夠，如果我們想實(shí)現(xiàn) contains(int k) 方法，目前只能遍歷一下 indexes[]，看看 k 在不在里面，時(shí)間復(fù)雜度是 \(O(|V|)\)。何不多維護(hù)一個(gè)數(shù)組 nodeIndexes[]，使得它滿足下述關(guān)系：

如果能在 nodeIndexes[k] 不是 -1，就說明索引 \(k\) 對應(yīng)的元素存在與堆中，且索引 k 在 indexes[] 中的位置為 \(d\)，即有下述等式成立：

有了這三個(gè)數(shù)組之后我們就可以實(shí)現(xiàn)最小索引優(yōu)先隊(duì)列了：

package com.zhiyiyo.collection.queue;
import java.util.Arrays;
import java.util.NoSuchElementException;
/**
 * 最小索引優(yōu)先隊(duì)列
 */
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;
            // 檢查是否有兩個(gè)子節(jié)點(diǎn)
            if (j < N && less(j + 1, j)) j++;
            if (less(k, j)) break;
            swap(k, j);
            k = j;
     * 交換完全二叉樹中編號為 a 和 b 的節(jié)點(diǎn)
     * @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)先隊(duì)列中");
}

注意對比最小堆和最小索引堆的 swap(int a, int b) 方法以及 less(int a, int b) 方法，在交換堆中的元素時(shí)使用的依據(jù)是元素的大小，交換之后無需調(diào)整 keys[]，而是交換 nodeIndexes[] 和 indexes[] 中的元素。

實(shí)現(xiàn)算法

通過上述的分析，實(shí)現(xiàn) Dijkstra 算法就很簡單了，時(shí)間復(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]);
            }
    // 省略已實(shí)現(xiàn)的方法 ...
}

后記

Dijkstra 算法還能繼續(xù)優(yōu)化，將最小索引堆換成斐波那契堆之后時(shí)間復(fù)雜度為 \(O(|E|+|V|\log |V|)\)，這里就不寫了（~~因?yàn)檫€沒學(xué)到斐波那契堆~~），以上~~

到此這篇關(guān)于教你在 Java 中實(shí)現(xiàn) Dijkstra 最短路算法的方法的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn) Dijkstra 最短路算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: