迪克斯特拉（Dijkstra）算法原理及实现（Java）

  迪克斯特拉（Dijkstra）算法：解决有权图中的最短路径（使用优先队列）问题；
  最短路径树（Shortest Path Tree）：所有节点的最短路径（相对于初始节点）组成的树。

算法原理
  1.使用优先队列（PQ）按照（节点，距离）的方式存储（优先跟踪距离较小的节点）；
  2.初始化edgeTo和disTo数组，初始化PQ；
  3.取出优先队列的第一个节点V，访问V已经被marked的邻接节点（disTo不为初始值），更新V的disTo和edgeTo信息；访问V未被marked的邻接节点W，更新W到source节点的距离（更新disTo数组），更新edgeTo，将W存入PQ。
  4.重复步骤3直至PQ为空。


java代码
  使用如下所示的有权图作为示例

  Dijkstra.java

import java.util.*;

public class Dijkstra {
    private PriorityQueue<Pair> priQueue;
    private int[] edgeTo; // 存储最短路径树中邻接的前一顶点
    private int[] disTo;  // 存储当前节点到source顶点的距离
    private int MAX_VALUE = Integer.MAX_VALUE;

    private class Pair {
        /* 存储顶点index和与source之间的最短距离信息
         */
        private int v;
        private int dis;

        Pair(int v, int dis) {
            this.v = v;
            this.dis = dis;
        }
    }

    private class selfComparator implements Comparator<Pair> {
        /* 自定义PQ中的Comparator
         */
        @Override
        public int compare(Pair o1, Pair o2) {
            if (o1.dis < o2.dis) {
                return -1;
            } else if (o1.dis > o2.dis) {
                return 1;
            }
            return 0;
        }
    }

    Dijkstra(Graph testGraph, int sourceIdx) {
        init(testGraph.V(), sourceIdx);  // 初始化edgeTo、disTO和PQ；
        while (priQueue.size() != 0) {
            Pair cur = priQueue.remove();
            visitAdjMarked(cur.v, testGraph);
            visitAdjUnMarked(cur.v, testGraph);
        }
    }

    private void init(int size, int s) {
        /* PQ初始存储source节点；
           edgeTo除source外设置为-1；
           disTo除source外设置为MAX_VALUE；
         */
        this.priQueue = new PriorityQueue<>(size, new selfComparator());
        this.edgeTo = new int[size];
        Arrays.fill(edgeTo, -1);
        edgeTo[s] = s;
        this.disTo = new int[size];
        Arrays.fill(disTo, MAX_VALUE);
        disTo[s] = 0;
        Pair cur = new Pair(s, disTo[s]);
        priQueue.add(cur);
    }

    private void visitAdjMarked(int idx, Graph graph) {
        /* 访问idx被visit过的邻接顶点
         */
        for (int adj : graph.adj(idx)) {
            int newDis = disTo[adj] + graph.disTO(idx, adj);
            if (disTo[adj] != MAX_VALUE && newDis < disTo[idx]) {
                disTo[idx] = newDis;
                edgeTo[idx] = adj;
            }
        }
    }

    private void visitAdjUnMarked(int idx, Graph graph) {
        /* 访问idx未被visit的邻接顶点
         */
        for (int adj : graph.adj(idx)) {
            int newDis = disTo[idx] + graph.disTO(idx, adj);
            if (disTo[adj] == MAX_VALUE) {
                disTo[adj] = newDis;
                edgeTo[adj] = idx;
                Pair cur = new Pair(adj, newDis);
                priQueue.add(cur);
            }
        }
    }

    public static void main(String[] args) {
        Graph test = new Graph(7);   // 按照实例初始化graph
        test.addEdge(0, 1, 2);
        test.addEdge(0, 2, 1);
        test.addEdge(1, 2, 5);
        test.addEdge(1, 3, 11);
        test.addEdge(1, 4, 3);
        test.addEdge(2, 4, 1);
        test.addEdge(2, 5, 15);
        test.addEdge(3, 4, 2);
        test.addEdge(4, 5, 4);
        test.addEdge(3, 6, 1);
        test.addEdge(4, 6, 5);
        test.addEdge(5, 6, 1);
        Dijkstra a = new Dijkstra(test, 0);
        List<Integer> route = new ArrayList<>();
        int t = 5;
        while (t != 0) {
            route.add(t);
            t = a.edgeTo[t];
        }
        System.out.print("到顶点5的最短路径为： 0");  // 验证最短路径是否正确
        for (int i = route.size() - 1; i >= 0; i--) {
            System.out.print(" ——> " + route.get(i));
        }
    }
}

  Graph.java

import java.util.ArrayList;
import java.util.List;

public class Graph {
    private List<Pair>[] ver;

    private class Pair {
        private int v;
        private int weight;

        Pair(int v, int weight) {
            this.v = v;
            this.weight = weight;
        }

        public int getV() {
            return v;
        }

        public int getWeight() {
            return weight;
        }
    }

    Graph(int v) {
        /* Create empty graph with v vertices
         */
        ver = new List[v];
    }

    public void addEdge(int v, int w, int n) {
        /* add an edge v-w with weight n
         */
        if (ver[v] == null) {
            ver[v] = new ArrayList<>();
        }
        if (ver[w] == null) {
            ver[w] = new ArrayList<>();
        }
        Pair pairV = new Pair(v, n);
        Pair pairW = new Pair(w, n);
        ver[v].add(pairW);
        ver[w].add(pairV);
    }

    Iterable<Integer> adj(int v) {
        /* vertices adjacent to v
         */
        List<Integer> res = new ArrayList<>();
        for (Pair p : ver[v]) {
            res.add(p.getV());
        }
        return res;
    }

    public int V() {
        /* number of vertices
         */
        return ver.length;
    }

    public int E() {
        /* number of edges
         */
        int res = 0;
        for (int i = 0; i < ver.length; i++) {
            res += ver[i].size();
        }
        return res / 2;
    }

    public int disTO(int v, int w) {
        /* the weight between v-w
         */
        int res = 0;
        for (Pair p : ver[v]) {
            if (p.getV() == w) {
                res = p.getWeight();
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Graph test = new Graph(7);
        test.addEdge(0, 1, 2);
        test.addEdge(0, 2, 1);
        test.addEdge(1, 2, 5);
        test.addEdge(1, 3, 11);
        test.addEdge(1, 4, 3);
        test.addEdge(2, 4, 1);
        test.addEdge(2, 5, 15);
        test.addEdge(3, 4, 2);
        test.addEdge(4, 5, 4);
        test.addEdge(3, 6, 1);
        test.addEdge(4, 6, 5);
        test.addEdge(5, 6, 1);
        for (int i = 0; i < test.V(); i++) {
            System.out.println("和" + i + "邻接的顶点为：" + test.adj(i));
        }
        System.out.println("顶点的数量：" + test.V());   // 顶点的数量应该为5
        System.out.println("边的的数量：" + test.E());   // 边的数量应该为6
    }
}

To be a sailor of the world bound for all ports.