图解Dijkstra和Bellman-Ford的流程以及证明

说到寻路，在游戏里面应用最多的自然还是A寻路，但是这篇文章不讨论A寻路，主要是介绍Dijkstra和Bellman-Ford，因为这两个寻路核心代码少，但是正确性却不容易直接看出来，网上的博客也基本都是画步骤告诉大家怎么做，本文画一画其步骤，并且尝试用比较通俗易懂的话来证明其正确性。

Dijkstra

用于有向图的寻路，可以求出起点到图中任意点的最短路径。
递归n-1次，每次确定一个顶点的距离，依次遍历完所有顶点即完成寻路。
在这里插入图片描述

算法流程

在这里插入图片描述

证明

由于我们每次确定终点到一个点的最短路径，所以只要确定n-1次中每次确定的正确性即可得证。
在这里插入图片描述

缺陷：负权边在未来存在变小可能

在这里插入图片描述

Bellman-Ford

同样用于有向图的寻路，算法复杂度高于Dijkstra，但是适用于有向图可能存在负权边的时候。其舍弃了Dijkstra贪心的思路，用遍历所有可能路径的办法解决了这个问题。

过程

在这里插入图片描述
设一共n个点，m条边，则进行两次循环，外层循环n-1次，内层循环m次,
每次遍历所有的边，通过到边的起点的距离和边本身的距离，尝试对边的终点的距离进行更新,核心代码很简单，这里可以直接写一下，
大家跟着上图按照代码模拟就行，这里就不继续一步一步做了，比较多。

for i = 0; i < nodes.length - 1; i++ {for j = 0; j < edges.length ; j++ {int start = edges[j].start, end = edges[j].end, weight= edges[j].weight;if (path[end] > path[start] + w)  path[end] = path[start] + weight;}
}

证明

Bellman-Ford的实际原理就是能够遍历从起点到任意点之间的所有路径，
从而理所当然的得出最小的值，我们举一个例子，如下图，1-5的最短路径是1-3-2-5
在这里插入图片描述
我们让边数组中按照与最短路径1-3-2-5颠倒的顺序排序就会发现，无论如何排，Bellman-Ford都能遍历到所有点之间所有的路径。

侦查负权环

当我们外循环遍历node.length - 1次之后，所有的点的距离都不应该发生变化了，如果第node.length遍遍历还有点缩小，说明存在一个可以无限缩短距离的负权环，此时到任何点都不存在最短路径，因为可以无限次绕环减少路径再到其他点。
举个具体例子，这里图片大家放大卡，如果是截成两张的话需要往下来反而更麻烦。
在这里插入图片描述