最短路径问题，经典算法问题。 概括了常用的最短路径算法，以及几种最短路径变种问题的解法，包括哈密顿路径。 对于有向图或有向图，假设v个节点、e条边、G[Vi，Vj]表示图中点Vi到Vj边的权重。 dist[i]表示从点s到点I的最短路径。
一.单源最短路径
给出图g，求出点对s-t之间的最短路径，这个问题可以用经典的dijkstra算法解决，时间复杂度o(v^2)。 基本思想：两个集合s、t、s表示已访问点的集合，t表示未访问点的集合，s首先为空，t包括所有点； 这是一种放松操作，每次选择从t集合到s到该点的距离最小的点cur，向s添加点cur以使s到s集合中的点之间的路径长度最小，然后使用cur点作为踏板更新从s到t集合中的其他点的距离
更新dist[cur] G[cur，j]，dist[j]=
dist[cur] G[cur，j]，其中j属于t集合； 算法在cur==t时结束。
二、负权边图的单源最短路径
关于(一)的戴克斯特拉法，可以用于求解负权重边缘的单源最短路径问题吗？ 在三元组(x、y、w )中表示边权为w的从点x到点y的有向边。 首先，假设图中包含三个节点，包含三条边。 (1，2，-3)，2，3，1 )，3，1 )。 从图中可以看到，如果在一个循环1-2-3-1中，循环的边权重的总和为-3)1=-1，则始终在循环中循环
处理负权重边缘的单源最短路径问题，可以采用bellman-ford算法、SPFA算法。
贝尔曼-福特算法思想： dist[s]=0，其他点I
，dist[i]=oo。 进行V-1循环，每循环(对图各边e(I，j )两侧的点进行松弛操作，在dist[j]的情况下
dist[i] G[i，j]，dist[j]=
dist[i] G[i，j]。 V-1循环完成后，存在边缘e[I，j]的情况下，在dist[i] G[i，j]的情况下进行判断
在dist[j]中，图中存在负权重循环。 在不存在负权重循环的情况下，dist[t]是从s到t的最短路径。 算法的复杂性o(ve )。
SFA算法思路：保持一个队列q。 队列初期只有s点。 标志数组flag、flag[i]=1表示节点I已排队。 否则，表示没有进入队列。 cnt序列，显示cnt[i]标志点I进入队列的次数。 求出队伍的起始要素cur，对边e(cur，j )，进行松弛操作： dist[j]
更新dist[cur] G[cur，j]，dist[j]=
dist[cur] G[cur，j]如果j不在队列中，则将j添加到队列末尾，同时判断j进入队列的次数是否大于V-1，如果大于V-1，则表示有负权重算法的复杂性o(2e )。
三.大图、多顶点稀疏图
Dijkstra算法的复杂度为o(v^2)，如果图的规模过大，肯定不能胜任。 实际上，对于规模较大的图，可以使用最小环优化、复杂度o () logV )。 思考：保持Dijkstrak中从t到s到t的路径最短的点，即用于优化堆顶部元素的最小堆。 这个方法是A*搜索。
四.全源最短路径问题
全部源最短路径求出图中的任意点对之间的最短路径。 方法(1) :列举任意点对，用dijkstra算法求解即可，复杂度为o(v )4)。 方法(2) :以各点为松弛操作中间点，列举其他两点进行松弛操作，得到全源最短路径。 这是一种有名的floyd算法，其状态转移方程如下。
G[i，j]=min{G[i，k] G[k，j]，G[i，j]}，时间复杂度o(v^3)。
五.最短哈密路
从s出发到达t，至少通过图中各点一次的最短路径长度。 这个问题是NPC问题，没有高效的解法。 假设有n个点，则n位标记这些点是已访问还是未访问。 假设f[I][J]表示从s出发到达j并且I的对应位为1的所有点的最短路径。 方程式如下
f[I1][J1]=min{f[I][j]g[j]，
列举I，j，j。 其中，(I(1
==0
(I|) 1
(I ) 1
初始f[(1) ]
从改进开始，使用上述方程式，推出包括结果f[(1])在内的所有中间变量
六、第k短传问题
求出从s到t的第k个短路径，如果k=1，直接采用dijkstra算法就可以求解。 如果k=2，首先用Dijkstra法求最短路径，然后列举删除最短路径，再次进行Dijkstra法，求最短路径是第k条短路径。
理论1:a*算法求解的路径最短。
理论表明可以很快用A*路径求出最短路径，比戴克斯特拉盲算法更有效率。
假设用A*算法求最短路径，即先搜索目标节点后不停止。 继续启发式搜索，根据理论1，第二次搜索目标节点的路径是第二次短路径。 依次类推得到第k短路径。
那么，A*算法的h’(x )是如何设计的呢？
众所周知，h’(x )和h ) x )越近，时间效率越高，h ) x )是从x到目标节点的实际长短短路长度。 如果这样直接取最佳值，则使用dijkstra算法计算从各点到目标节点的最短路径作为估计值h’() x，使效率极大。