Dijkstra算法

概念

Dijkstra 算法是一个可以解决单一源点最短路径问题的经典算法，本质上是对广度优先搜索（BFS）的一个推广，只是把 BFS 维护的栈换成了优先队列。

Dijkstra算法成立的前提条件是不存在负权的边，这意味任何一条路径，从起点开始到路径中每个点的距离都是依次递增的。所以按照递增的顺序来依次计算出最短路径也就是Dijkstra算法了

每次循环都会增多一个保证已经找到最短路的点。

直观来说，如果我们已经求出了k个离源点距离最近的点，以及它们各自的距离，那么到源点距离第k+1近的点，它到源点的最短路径只能经过这前k个点——如果经过了其他点，那么这个其他点显然离源点更近，那这个点一定不是第k+1近了。既然只经过这前k个点，那么只用这前k个点放缩就可以找到那个最短路径了。再加上前k-1个点上一轮已经放缩过，所以每一轮只需要用新加入的节点进行放缩就行了。

无法处理有负边的图

举例：

第一次贪心得到的点的路径s->v不是最短路

拓展

  1. 判断图中某一个点是否在最短路径中
    1. 回溯：计算最短路径过程中同时记录每个点的父节点们，最后得到最短路径后，从终点开始回溯
    2. 双边dijkstra：计算起点s到终点e和终点到起点的dijkstra最短路径dis[]和dis2[]，判断起点到这个点的最短路径 + 这个点到终点的最短路径 是否等于起点到终点的最短路径，即dis[v] + dis2[v] == dis[e]
  2. 判断图中某一个边是否在最短路径中
    1. 回溯：同理
    2. 双边dijkstra：对于边(u,v,w)，判断dis[x] + dis2[y] + w == dis[n-1] || dis[y] + dis2[x] + w == dis[n-1]

相关证明

题解