10行实现最短路算法——Dijkstra

今天是算法数据结构专题的第34篇文章，我们来继续聊聊最短路算法。

在上一篇文章当中我们讲解了bellman-ford算法和spfa算法，其中spfa算法是我个人比较常用的算法，比赛当中几乎没有用过其他的最短路算法。但是spfa也是有缺点的，我们之前说过它的复杂度是$O(kE)$，这里的E是边的数量。但有的时候边的数量很多，E最多能够达到$V^2$，这会导致超时，所以我们会更换其他的算法。这里说的其他的算法就是Dijkstra。

算法思想

在上一篇文章当中我们曾经说过Bellman-ford算法本质上其实是动态规划算法，我们的状态就是每个点的最短距离，策略就是可行的边，由于一共最多要松弛V-1次，所以整体的算法复杂度很高。当我们用队列维护可以松弛的点之后，就将复杂度降到了$O(kE)$，也就是spfa算法。

Dijkstra算法和Bellman-ford算法虽然都是最短路算法，但是核心的逻辑并不相同。Dijkstra算法的底层逻辑是贪心，也可以理解成贪心算法在图论当中的使用。

其实Dijstra算法和Bellman-ford算法类似，也是一个松弛的过程。即一开始的时候除了源点s之外，其他的点的距离都设置成无穷大，我们需要遍历这张图对这些距离进行松弛。所谓的松弛也就是要将这些距离变小。假设我们已经求到了两个点u和v的距离，我们用dis[u]表示u到s的距离，dis[v]表示v的距离。

假设我们有dis[u] < dis[v]，也就是说u离s更近，那么我们接下来要用一个新的点去搜索松弛的可能，u和v哪一个更有可能获得更好的结果呢？当然是u，所以我们选择u去进行新的松弛，这也就是贪心算法的体现。如果这一层理解了，算法的整个原理也就差不多了。

我们来整理一下思路来看下完整的算法流程：

1. 我们用一个数组dis记录源点s到其他点的最短距离，起始时dis[s] = 0，其他值设为无穷大
2. 我们从未访问过的点当中选择距离最小的点u，将它标记为已访问
3. 遍历u所有可以连通的点v，如果dis[v] < dis[u] + l[u] [v]，那么更新dis[v]
4. 重复上述2，3两个步骤，直到所有可以访问的点都已经访问过

怎么样，其实核心步骤只有两步，应该很好理解吧？我找到了一张不错的动图，大家可以根据上面的流程对照一下动图加深一下理解。

我们根据原理不难写出代码：

INF = sys.maxsize
edges = [[]] # 邻接表存储边
dis = [] # 记录s到其他点的距离
visited = {
   } # 记录访问过的点

while True:
    mini = INF
    u