一、有权图的最短路径：

1、概念：

  所谓的有权图的最短路径也就是图中的每条边都有一个权重，最短路径就是经过的边的权重和最小。

2、思路：

  用vertexes数组，记录从起始顶点到每个顶点的距离（dist）。开始前，把所有顶点的dist都初始化为无穷大（也就是代码中的Integer.MAX_VALUE）。把起始顶点的dist值初始化为0，然后将其放到优先级队列中。
  从优先级队列中取出dist最小的顶点minVertex，然后考察这个顶点可达的所有顶点（代码中的nextVertex）。如果minVertex的dist值加上minVertex与nextVertex之间边的权重w小于nextVertex当前的dist值，也就是说，存在另一条更短的路径，它经过minVertex到达nextVertex。那就把nextVertex的dist更新为minVertex的dist值加上w。然后，把nextVertex加入到优先级队列中。重复这个过程，直到找到终止顶点t或者队列为空。
  以上就是Dijkstra算法的核心逻辑。除此之外，代码中还有两个额外的变量， predecessor数组和inqueue数组。
  predecessor数组的作用是为了还原最短路径，它记录每个顶点的前驱顶点。最后，通过递归的方式，将这个路径打印出来。
  inqueue数组是为了避免将一个顶点多次添加到优先级队列中。当更新了某个顶点的dist值之后，如果这个顶点已经在优先级队列中了，就不要再将它重复添加进去了。

3、图示：

4、Dijkstra算法：

public class Graph { // 有向有权图的邻接表表示
    private LinkedList<Edge> adj[]; // 邻接表
    private int v; // 顶点个数
    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实现用的
private class Vertex {
    public int id; // 顶点编号ID
    public int dist; // 从起始顶点到这个顶点的距离
    public Vertex(int id, int dist) {
        this.id = id;
        this.dist = dist;
    }
}

// 因为Java提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
private class PriorityQueue { // 根据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: 待实现...
    }
    public void add(Vertex vertex) { 
        // TODO: 待实现...
    }
    // 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度O(logn)。
    public void update(Vertex vertex) { 
        // TODO: 待实现...
    }
    public boolean isEmpty() { 
        // TODO: 待实现...
   }
    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循环最多会执行次（表示顶点的个数），而内部的for循环的执行次数不确定，跟每个顶点的相邻边的个数有关，我们分别记作， ， ， ……， 。如果把这个顶点的边都加起来，最大也不会超过图中所有边的个数（表示边的个数）。
  for循环内部的代码涉及从优先级队列取数据、往优先级队列中添加数据、更新优先级队列中的数据，这样三个主要的操作。由于优先级队列是用堆来实现的，堆中的这几个操作，时间复杂度都是（堆中的元素个数不会超过顶点的个数）。
  所以，综合这两部分，再利用乘法原则，整个代码的时间复杂度就是。