一、有權圖的最短路徑：

1、概念：

??所謂的有權圖的最短路徑也就是圖中的每條邊都有一個權重，最短路徑就是經過的邊的權重和最小。

2、思路：

??用vertexes數(shù)組，記錄從起始頂點到每個頂點的距離（dist）。開始前，把所有頂點的dist都初始化為無窮大（也就是代碼中的Integer.MAX_VALUE）。把起始頂點的dist值初始化為0，然后將其放到優(yōu)先級隊列中。
??從優(yōu)先級隊列中取出dist最小的頂點minVertex，然后考察這個頂點可達的所有頂點（代碼中的nextVertex）。如果minVertex的dist值加上minVertex與nextVertex之間邊的權重w小于nextVertex當前的dist值，也就是說，存在另一條更短的路徑，它經過minVertex到達nextVertex。那就把nextVertex的dist更新為minVertex的dist值加上w。然后，把nextVertex加入到優(yōu)先級隊列中。重復這個過程，直到找到終止頂點t或者隊列為空。
??以上就是Dijkstra算法的核心邏輯。除此之外，代碼中還有兩個額外的變量， predecessor數(shù)組和inqueue數(shù)組。
??predecessor數(shù)組的作用是為了還原最短路徑，它記錄每個頂點的前驅頂點。最后，通過遞歸的方式，將這個路徑打印出來。
??inqueue數(shù)組是為了避免將一個頂點多次添加到優(yōu)先級隊列中。當更新了某個頂點的dist值之后，如果這個頂點已經在優(yōu)先級隊列中了，就不要再將它重復添加進去了。

3、圖示：

4、Dijkstra算法：

public class Graph { // 有向有權圖的鄰接表表示
    private LinkedList<Edge> adj[]; // 鄰接表
    private int v; // 頂點個數(shù)
    public Graph(int v) {
        this.v = v;
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            this.adj[i] = new LinkedList<>();
        }
    }
    public void addEdge(int s, int t, int w) { // 添加一條邊
        this.adj[s].add(new Edge(s, t, w));
    }
}

private class Edge {
    public int sid; // 邊的起始頂點編號
    public int tid; // 邊的終止頂點編號
    public int w; // 權重
    public Edge(int sid, int tid, int w) {
        this.sid = sid;
        this.tid = tid;
        this.w = w;
    }
}
// 下面這個類是為了dijkstra實現(xiàn)用的
private class Vertex {
    public int id; // 頂點編號ID
    public int dist; // 從起始頂點到這個頂點的距離
    public Vertex(int id, int dist) {
        this.id = id;
        this.dist = dist;
    }
}

// 因為Java提供的優(yōu)先級隊列，沒有暴露更新數(shù)據(jù)的接口，所以我們需要重新實現(xiàn)一個
private class PriorityQueue { // 根據(jù)vertex.dist構建小頂堆
    private Vertex[] nodes;
    private int count;
    public PriorityQueue(int v) {
        this.nodes = new Vertex[v+1];
        this.count = v;
    }
    public Vertex poll() {  
        // TODO: 待實現(xiàn)...
    }
    public void add(Vertex vertex) { 
        // TODO: 待實現(xiàn)...
    }
    // 更新結點的值，并且從下往上堆化，重新符合堆的定義。時間復雜度O(logn)。
    public void update(Vertex vertex) { 
        // TODO: 待實現(xiàn)...
    }
    public boolean isEmpty() { 
        // TODO: 待實現(xiàn)...
   }
    public void dijkstra(int s, int t) { // 從頂點s到頂點t的最短路徑
        int[] predecessor = new int[this.v]; // 用來還原最短路徑
        Vertex[] vertexes = new Vertex[this.v];
        for (int i = 0; i < this.v; ++i) {
            vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
        }
        PriorityQueue queue = new PriorityQueue(this.v);// 小頂堆
        boolean[] inqueue = new boolean[this.v]; // 標記是否進入過隊列
        vertexes[s].dist = 0;
        queue.add(vertexes[s]);
        inqueue[s] = true;
        while (!queue.isEmpty()) {
            Vertex minVertex= queue.poll(); // 取堆頂元素并刪除
            if (minVertex.id == t) break; // 最短路徑產生了
            for (int i = 0; i < adj[minVertex.id].size(); ++i) {
                Edge e = adj[minVertex.id].get(i); // 取出一條minVetex相連的邊
                Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
                if (minVertex.dist + e.w < nextVertex.dist) { // 更新next的dist
                    nextVertex.dist = minVertex.dist + e.w;
                    predecessor[nextVertex.id] = minVertex.id;
                    if (inqueue[nextVertex.id] == true) {
                        queue.update(nextVertex); // 更新隊列中的dist值
                    } else {
                        queue.add(nextVertex);
                        inqueue[nextVertex.id] = true;
                    }
                }
            }
        }
    // 輸出最短路徑
        System.out.print(s);
        print(s, t, predecessor);
    }

    private void print(int s, int t, int[] predecessor) {
        if (s == t) return;
        print(s, predecessor[t], predecessor);
        System.out.print("->" + t);
    }
}

5、Dijkstra算法時間復雜度：

??while循環(huán)最多會執(zhí)行 $V$ 次（ $V$ 表示頂點的個數(shù)），而內部的for循環(huán)的執(zhí)行次數(shù)不確定，跟每個頂點的相鄰邊的個數(shù)有關，我們分別記作 $E_0$ ， $E_1$ ， $E_2$ ， ……， $E_{V-1}$ 。如果把這 $V$ 個頂點的邊都加起來，最大也不會超過圖中所有邊的個數(shù) $E$ （ $E$ 表示邊的個數(shù)）。
??for循環(huán)內部的代碼涉及從優(yōu)先級隊列取數(shù)據(jù)、往優(yōu)先級隊列中添加數(shù)據(jù)、更新優(yōu)先級隊列中的數(shù)據(jù)，這樣三個主要的操作。由于優(yōu)先級隊列是用堆來實現(xiàn)的，堆中的這幾個操作，時間復雜度都是 $O(logV)$ （堆中的元素個數(shù)不會超過頂點的個數(shù) $V$ ）。
??所以，綜合這兩部分，再利用乘法原則，整個代碼的時間復雜度就是 $O(E*logV)$ 。