最短路径算法

原文链接：https://blog.csdn.net/xiaoxi_hahaha/article/details/110257368

已知起始结点，求最短路径的问题。适合使用Dijkstra算法。迪杰斯特拉算法是由荷兰计算机科学家在1956年发现的算法，此算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。它是一个贪心算法。

全局最短路径问题- 求图中所有的最短路径。适合使用Floyd-Warshall算法

Dijkstra算法：

首先，可以设置两个集合分别是A和B，A用来存放已经求出最短路径的点，B用来存放还未计算出最短路径的点，

我们从图中任选一点来解题，假设我们将源点source选择在” 0 "这个点。一开始所有点到达源点0的距离我们假设为∞，代表不可达。源点0到自己本身的距离为0，初始化如下：此时A集合为：{0}，B集合为：{1，2，3，4，5，6}

第一步：从0点开始，更新和0邻接的所有点的距离，此时，因为与0邻接的有1和2，并且到这两个点的距离，小于原来的∞距离，所以要将这两个点到0的距离都进行更新如下图，

第二步：从B集合里面选择一个点加入A集合，这个点要满足距离0点的距离最短，因此我们选择2这个点添加到集合A，此时集合A变为：{0,2}，集合B变为：{1，3，4，5，6}，如下图

第三步：选择刚刚加入的这个2点，更新所有与2点邻接的点，因为与2邻接的点有3和5，并且这两个点到0点的距离小于原来它们到0点的距离∞

第四步：从B集合里面选择1这点加入到集合A中，因为1这个点在B集合中距离0最近，如下图，此时A集合变成：{0,1,2}，B集合变成：{3,4,5,6}

第五步：选择刚刚加入的1这个点，更新1所有的邻接点，它的邻接点有3和4，因为此刻从0到3的距离为6，小于原来0到3的距离8，因此这个时候到6的距离更新为6(5+1)，此时0到4的距离被更新为11