嘉兴建站模板,东莞一站式网站建设,免费的网站申请,专业seo推广最短路径问题#xff0c;一个经典算法问题。本文粗略总结了一种常见的最短路径算法#xff0c;以及几个最短路径变种问题的解法#xff0c;其中包括哈密顿路。对于有向图或者无向图#xff0c;假设有V个节点#xff0c;E条边#xff0c;G[Vi,Vj]表示图中点Vi到Vj边的权值…最短路径问题一个经典算法问题。本文粗略总结了一种常见的最短路径算法以及几个最短路径变种问题的解法其中包括哈密顿路。对于有向图或者无向图假设有V个节点E条边G[Vi,Vj]表示图中点Vi到Vj边的权值。dist[i]表示点s到点i的最短路径。一、单源最短路径给定图G求点对s-t之间的最短路径该问题使用经典的dijkstra算法即可解决时间复杂度O(V^2)。基本思想两个集合S,TS表示已经访问的点集合T表示未访问的点集合S初始为空T包括所有点每次从T集合中选取从s到该点距离最小的点cur然后将点cur加入到S中(保证从s到S集合中的点之间的路径长度最小)并且基于cur点为跳板做松弛操作更新s到T集合中其他点的距离松弛操作即如果dist[j] dist[cur] G[cur,j]更新dist[j] dist[cur]G[cur,j]其中j属于T集合当curt时算法结束。二、有负权边的图的单源最短路径对于(一)中的dijkstra算法是否可以用于求解带负权边的单源最短路径问题呢用三元组(x,y,w)表示一条边权为w的从点x到点y的有向边。先举例看看假设图中包含3个节点包含3条边(12-3)、(231)、(311)从图可以看出为一个环1-2-3-1且环的边权总权值为-311-1那么通过一直循环那么图中任意两点之间的最短路径都为-oo大因此不能通过dijkstra来求解最短路径因为出现负环之后破坏了“从s到集合S中点之间路径长度最小”这点通过负环的循环s到S中点之间的路径长度还可以变小。对付有负权边的单源最短路径问题可以采用bellman-ford算法、SPFA算法。Bellman-ford算法思想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)。SPFA算法思想维护一个队列Q队列初始只有s点一个标记数组flagflag[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)如果图的规模太大那么无疑难以胜任。其实对与规模大的图可以使用min-heap优化复杂度O((VE)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位bit来标记那些点已经访问过哪些没有访问过。设f[I][J]表示从s出发达到J且经过了I中对应位标记为1的所有点的最短路径。有方程如下f[I1][J1] min{F[I][J] G[J][j],枚举I,J,j,其中(I(1 0 (I|(1(I(1初始只f[(1从改点出发利用上述方程推出所有的中间变量包括结果f[(1六、第K短路径问题求s到t的第k短路径如果k1直接采用dijkstra算法即可求解。如果k2的话首先采用dijkstra算法求解最短路径然后枚举删除最短路径上边再次进行dijkstra算法求解最短路径即为第k短路径。理论一A*算法求解到的路径是最短的。根据理论一就可以用A*路径求得最短路径比dijkstra盲目式算法效率高。假设用A*算法求得最短路径时即第一次搜索到目标节点后不停止。继续启发式搜索下去那么根据理论一可以得到第二次搜索到目标节点的路径是第二短路径。依次类推得到第k短路径。那么A*算法的h’(x)怎么设计呢已知h’(x)与h(x)越接近时间效率越好h(x)为x到目标节点的实际最短路长。既然这样那么直接取最好值先用dijkstra算法算出各点到目标节点的最短路径作为估价值h’(x)使效率到达极大。
