最短路径
最短路径(Shortest Paths ) ) ) ) ) ) ) ) )。
最短路径问题一直是图论研究的热点问题。 例如，在现实生活中的路径规划、地图导航等领域有重要的应用。 虽然求解图的最短路径法也相继问世，但本论文将对图的最短路径算法进行详细说明。 最短路径问题的背景问题一般是相似的。 因为知道各城市之间的距离，所以从城市a到城市b的最短行驶方案or各城市之间的距离一致，表明需要最小的中继方案。 简而言之，固定起始点的情况下，求最短路
引用子在下面的例子中，有向图，使用邻接矩阵存储图表信息，求出任意2点之间的最短路径。
浮动封装算法
对于I、j这两个节点，考虑一下如果想缩短路径，只能在第三个节点k上中继的逻辑。 虽然离1-5的距离是10，但离1-2-5的距离变成了9。 实际上，**各顶点可能会缩短其他两个顶点之间的路程，**这种中转移的短操作称为松弛。
Code Floyd-Warshall算法的原理是动态规划。 让我们看看那个代码：
deffloydwarshall(graph ) :n=len ) graph ) distance=[ graph [ I ] [ j ] forjinrange (n ) ] for i in range(n ) ] p for j in range(n ) n )、forIinrange ) n )、forkinrange ) n ) 3360forIinrange )、n )、3360forIinrange=j and i！=k and j！=Kan distance [ I ] [ j ] distance [ I ] [ k ] [ j ] : distance [ I ] [ j ]=distance [ I ] [ k ] distance 更新为precursor三层环、第一层环的中间点k，二、三层环的起点、终点I，j，算法思想不难理解。 如果I到k的距离加上K到j的距离很小的话，就使用吧：
graph data=[ 0，2，float(INF )，float )，INF )，10 )，[ float ]，INF )，0，3，float )，7]，float(INF )，float float )，0 ) ] shorr at path=floydwarshall (graph data ) foriteminshortest : print (item ) print ) ) foriteminpath:print
复杂度分析
Floyd-Warshall算法的时间复杂度为O(N3 )，空间复杂度为O(N2 )。
Dijkstra算法
在某种情况下，我们可能只是想找到从原点到某个顶点的最短路径。 例如，在我们开车的时候查一下地图，只需要知道从我现在的位置到目的地的最短路径就可以了。 戴克斯特拉法用于计算从一点到其他所有点的最短路径问题，是单源最短路径算法。 也就是说，只能计算只有一个起点的情况。
针对图G=V，e上的加权单源最短路径问题，戴克斯特拉法为了记录已经求出最短路径的顶点而设定集合s，初始时将起点v放入s，每当集合s编入新的顶点v时，计算从原点v到集合V-S中的顶点的当前最短路径长度的
代码Dijkstra算法基于贪婪策略。 让我们看一下代码：
defDijkstra(graph，node ) : n，queue，visit=Len ) gr
aph), list(), set() heapq.heappush(queue, (0, node)) distance, precursor = [float("inf") for _ in range(n)], {node: None} distance[node] = 0 while queue: dist, vertex = heapq.heappop(queue) visit.add(vertex) for i in range(n): val = graph[vertex][i] if val != float("inf") and val not in visit and dist + val < distance[i]: precursor[i] = vertex distance[i] = dist + val heapq.heappush(queue, (dist + val, i)) return distance, precursor我们来分析一下这个算法，从起点到一个顶点的最短路径一定会经过至少一个“中转点”（我们认为起点也是一个“中转点”），如果我们想要求出起点到一个顶点的最短路径，那我们必须要先求出从起点到中转点的最短路径。
对于图G=<V, E>，将所有的点分为两类，一类是已经确定最短路径的点，称为“白点”，另一类是未确定最短路径的点，称为“蓝点”。如果我们要求出一个点的最短路径，就是把这个点由蓝点变为白点，从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。
Dijkstra算法的思想：首先将起点的距离标记为0，而后进行n此循环，每次找出一个到起点距离最短的点，将它从蓝点变为白点，随后枚举所有的蓝点，如果以此白点为中转到达某个蓝点的路径更短的话，那么就更新。我们可以来使用一下：
在SciPy中有一个官方提供的dijkstra函数，我们可以通过调用它来验证一下我们写的Dijkstra算法是否正确。
注意：Dijkstra算法不能处理存在负边权的情况。
时间复杂度为O(V)。
Bellman-Ford算法与Dijkstra算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。
Bellman - Ford算法基于动态规划，反复用已有的边来更新最短距离，Bellman-Ford算法的核心就是松弛。简单地对所有边进行松弛操作，共|V|-1次，其中|V|是图中顶点的数量。对于点 v 和 u，如果 dist[u] 和 dist[v] 满足 dist[v] > dist[u] + map[u][v]，那么dist[v] 就应该被更新为 dist[u] + map[u][v]。反复地利用上式对每条边进行松弛，从而更新 dist[] 数组，如果没有负权回路的话，应当会在 n - 1 次松弛之后结束算法。
SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算，它的主要思想是：初始时将起点加入队列，每次从队列中取出一个元素，并对所有与它相邻的点进行修改，炙热的路灯个相邻的点修改成功，则将其入队，直到队列为空时算法结束。
我们同样也通过scipy提供的bellman_ford函数来验证一下：
graphData = [[0, 2, float("inf"), float("inf"), 10], [float("inf"), 0, -3, float("inf"), 7], [4, float("inf"), 0, 4, float("inf")], [float("inf"), float("inf"), float("inf"), 0, 5], [float("inf"), float("inf"), 3, float("inf"), 0]] shortest, path = spfa(graphData, 0) print(shortest, path) print('-' * 75) graphData = csr_matrix(graphData) distMatrix = bellman_ford(csgraph=graphData, directed=True, indices=0, return_predecessors=True) print(distMatrix)
注意：Bellman-Ford算法不能处理存在负权回路的情况。
时间复杂度为O(kE)，k是常数，平均值为2，E是边数。
中等
LeetCode 1631. 最小体力消耗路径
POJ 1062.昂贵的聘礼
LeetCode 778. 水位上升的泳池中游泳