概念

Dijkstra算法用于解决无向图或者有向图（有环无环皆可）中起点到各个顶点的最短路径，前提是该图的所有边权必须大于等于0。如果图的边有负权值，就需要用到Bellman-Ford算法。本篇博客仅介绍Dijkstra算法。

Dijkstra算法是基于贪心思想的算法。具体过程是：

• 将图中节点从0~n标号，定义起点为0。
• 定义一个数组way，长度为n + 1，记录从起点到某个点的最小距离。并将数组中全部元素赋值为Integer.MAX_VALUE。
• 从起点开始遍历每个图的节点（一般使用BFS），每遍历到一个节点x时，如果此时从起点开始走的路径长度小于way[x]，那么就将此时从起点开始走的路径长度赋值给way[x]，并在下次遍历时以该点继续遍历；如果大于忽略就不再遍历。
• 遍历完成后，数组way中的值也就记录了从起点开始到某个点的最小距离。

图解

给出上述有向正权图，起点为0，求出起点0到各个节点的最短路径。解题过程如下：

存储图的信息

首先我们得需要一个数据结构来存储图。图在内存中的存储有多种方法：

• 邻接矩阵
  简单地说就是定义一个二维数组map，其长度为图的节点数量，宽度也为图的节点数量，元素map[x][y]代表从图的节点x到节点y的边的长度，如果没有这条边，那么该元素的大小为 $+\infty$，这种方法空间复杂度为 $O(n^2)$，以上述图为例，构造好的二维数组内容为：
  
• 变长数组
  可以发现，邻接矩阵的表示方法对于稠密图而言空间浪费不算太严重，但是对于稀疏图而言就会有大量的空间浪费，如果有10万条边，那么构造一个这样的数组就需要150GB的内存空间，这显然是不合适的。
  在上述例子中，我们可以用变长数组来存储图，来减少空间的浪费，具体而言就是采用构造一个Map数组arr，arr[i]对应的Map保存了该点所有的边的数据（键为节点号码，值为边的长度）：
  

正式遍历

以上述例子为例，首先定义一个数组way，长度为6，保存从起点开始到各个点的最小距离，起点为0，然后将除0外的所有元素赋值为Integer.MAX_VALUE，下图中用 $+\infty$ 表示。

然后建立一个队列，队列中每个元素保存了下次访问的节点和走过的路径。

在这里我们采用广度优先遍历来遍历整个图，第一步从起点开始，遍历点1和点2：

（图中队列元素为节点编号，省略了路径长度）
遍历点1和点2时发现 $1<+\infty$ 并且 $10<+\infty$，此时将way[1]和way[2]分别赋值为1、10

然后取出队首元素1，代表此次访问节点1，节点1只有一个边连向4，并且 $1+4<+\infty$ ，所以将way[4]赋值为5，并将节点4入队。

取出队首元素2，代表此次访问节点2，节点2有两个边分别连接节点1和节点3。
首先看2 -> 1对应的边，由于10 + 9 > way[1]，所以节点1不能入队。
接下来查看2 -> 3对应的边，由于$10+5<+\infty$，所以将way[3]赋值为15，节点3入队。

取出队首元素4，代表此次访问节点4，节点4有两个边分别连接节点3和节点5。
首先看4 -> 3这条边，由于5 + 9 < way[3]，所以可以让节点3入队，并将5 + 9赋值给way[3]，并将节点3入队。
再来看4 -> 5这条边，由于5 + 15 < way[5]，所以将5 + 15赋值给way[5]。

取出队首元素3（注意本次的路径是0->2->3）。
首先看3->1这条边，由于15 + 3 < way[1] ，所以忽略。
再来看3->5这条边，由于15 + 5 == way[5]，所以忽略。

取出队首元素3（注意本次的路径是0->1->4->3）
首先看3->1这条边，由于15 + 3 < way[1] ，所以忽略。
再来看3->5这条边，由于14 + 5 < way[5]，所以将5入队，并将19赋给way[5]。

取出队首元素5，没有路径连向其它节点，忽略。

取出队首元素5，没有路径连向其它节点，忽略。

队列为空后跳出循环，此时way数组就记录了从0到其它节点的最短路径。

代码

首先定义一个类Node代表一个节点：

class Node { 
    int id; Map<Node, Integer> nodes = new LinkedHashMap<>(); } 

成员变量id为节点编号，nodes为与该节点相连的节点Map，这个Map的值为路径长度。

定义一个类Graph代表整个图：

讯享网class Graph { 
    int nodeSum; Node start; } 

nodeSum为节点数量，start为起点。

public int[] dijkstra(Graph g) { 
    Queue<Node> queue = new LinkedList<>(); //记录访问的节点 Queue<Integer> wayQueue = new LinkedList<>(); //记录路径长度 int[] ans = new int[g.nodeSum]; Arrays.fill(ans, Integer.MAX_VALUE); queue.offer(g.start); wayQueue.offer(0); ans[0] = 0; while(!queue.isEmpty()) { 
    Node node = queue.poll(); int way = wayQueue.poll(); node.nodes.forEach((n, p) -> { 
    if(way + p >= ans[n.id]) { 
    //如果本次路径大于之前访问的路径长度，忽略 return; } ans[n.id] = way + p; queue.offer(n); wayQueue.offer(way + p); }); } return ans; } 

练习

2019搜狗校招笔试题：龟兔赛跑

定义如下图所示的比赛地图：

S表示比赛起点，E表示比赛终点。实线表示陆路，虚线表示水路。兔子只能走陆路，乌龟既可以走陆路也可以走水路。每条路径的长度在图中给出。假定兔子和乌龟足够聪明，问谁先到达终点。

输入描述:

第1行输入v1，v2。v1是兔子的速度，v2是乌龟的速度（水路、陆路速度相同）。第2行输入n,m，点的编号是1~n,然后是m行，其中1是 起点，n是终点（路径本身不限定方向）。下面m行4个数 a, b, d, c，表示a和b之间有一条边，且其长度为d，类型是c（0表示陆路，1表示水 路）。最后一行是end，表示输入结束。输入保证1和n之间至少有一条路径联通。(1<n<=10000, 0<m<=)。

输出描述：

输出-1,0,1中的一个数。-1表示乌龟获胜，1表示兔子获胜，0表示同时到达终点。

输入示例：

10 5
3 3
1 2 30 0
2 3 20 0
1 3 20 1
end

输出

-1

分析

代码

讯享网import java.util.*; public class Main { 
    static class Graph { 
    private Node start; private Node end; private final Map<Long, Node> map = new HashMap<>(); } static class Node { 
    final long id; final Map<Way, Node> wayMap = new HashMap<>(); Node(long id) { 
    this.id = id; } } static class Way implements Comparable<Way> { 
    long len; int type; Way(long len, int type) { 
    this.len = len; this.type = type; } @Override public int compareTo(Way o) { 
    return Long.compare(len, o.len); } } public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); long v1 = sc.nextLong(); long v2 = sc.nextLong(); long n = sc.nextInt(); long m = sc.nextInt(); Graph g = new Graph(); for (int i = 0; i < m; i++){ 
    long src = sc.nextInt(); long tar = sc.nextInt(); long d = sc.nextLong(); int type = sc.nextInt(); Node s = g.map.get(src); if(s == null) { 
    s = new Node(src); g.map.put(src, s); } Node t = g.map.get(tar); if(t == null) { 
    t = new Node(tar); g.map.put(tar, t); } s.wayMap.put(new Way(d, type), t); if(src == 1) { 
    g.start = s; } if(tar == 1) { 
    g.start = t; } if(src == n) { 
    g.end = s; } if(tar == n) { 
    g.end = t; } } if(g.start == null || g.end == null) { 
    System.out.println(0); } double t1 = bfs(g, v1, false); double t2 = bfs(g, v2, true); if(Math.abs(t1 - t2) < 0.001) { 
    System.out.println(0); } else { 
    System.out.println(t1 < t2 ? "1" : "-1"); } } private static double bfs(Graph g, long speed, boolean water) { 
    Map<Long, Long> vis = new HashMap<>(); Queue<Node> queue = new LinkedList<>(); Queue<Long> wayQueue = new LinkedList<>(); queue.offer(g.start); wayQueue.offer(0L); vis.put(g.start.id, 0L); while (!queue.isEmpty()) { 
    Node n = queue.poll(); long w = wayQueue.poll(); n.wayMap.forEach((way, nd) -> { 
    if(!water && way.type == 1) { 
    return; } Long before = vis.get(nd.id); if(before != null && w + way.len >= before) { 
    return; } vis.put(nd.id, w + way.len); queue.offer(nd); wayQueue.offer(w + way.len); }); } Long ans = vis.get(g.end.id); if(ans == null) { 
    ans = Long.MAX_VALUE; } return (double) ans / speed; } }