ACM最短路径算法.ppt

《ACM最短路径算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最短路径算法问题引入：中二尚、菜鸡然和小水虎从哈尔滨出发去宁波参加第二届CCPC全国总决赛，但是因为没有直达的火车票，而且学校穷，不给报销飞机票。现在已知可以从任意车站中转，也知道任意两个车站之间的票价，聪明的你们能否算出他们能参加比赛的最小花费？求图中任意两点之间的最短路径。最近公共祖先LCADijkstra算法及其队列优化1Bellman-Ford算法2SPFA（Bellman-Ford队列优化）3BFS求单源最短路径4Floyd-Warshell算法5Dijkstra算法及其队列优化Dijkstra算法及其队列优化Dijkstra算法及

2、其队列优化Dijkstra算法及其队列优化Dijkstra算法优化：从算法过程和代码中我们可以知道，Dijkstra算法的时间浪费在了每次都要遍历所有点去寻找当前dist数组中的最小值，所以我们可以很轻易地想出利用堆或优先队列的方式对算法进行优化。优化后的Dijkstra算法时间复杂度为O（ElogV）Bellman-Ford算法Bellman-Ford算法中边权可正可负，并且可以判断图中是否存在负环，而Dijkstra算法无法处理边权为负数的情况。第一，初始化所有点。第二，进行循环，遍历所有的边，进行松弛计算。第三，遍历图中所有的边edge

3、（u，v），判断是否存在这样情况：d（v）>d(u)+w(u,v)有则返回false，表示途中存在从源点可达的权为负的回路。Bellman-Ford算法数组dist[i]记录从源点s到顶点i的路径长度初始化dist[i]为无穷大，表示不可达，dist[s]=0for(inti=1;i

4、994年发表的。设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。SPFA算法定理：只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短

5、路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。SPFA算法SPFA是这样判断负环的：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）期望的时间复杂度：O(ke)，其中k为所有顶点进队的平均次数，可以证明k一般小于等于2但是SPFA在最坏情况下会退化成Bellman算法。最坏时间复杂度为O（VE）SPFA算法SPFA算法有两个优化算法SLF和LLL：SLF：SmallLabelFirst策略，设要加入的节点是j，队首元素为i，若dis

6、t(j)nRELAX(u,i)；如果不在队列中，vis[i]=true，cnt[i]++，如果入队次数大于等于n，returnfalse，入队。BFS求单源

7、最短路径在我们学习图的基本算法BFS和DFS的时候，其实那就是一个求解每一步的权重都为1的最短路，那么权重不为1的情况我，我们是否继续使用呢？采用邻接表或前向星进行图的存储，则BFS的时间复杂度为：开始的初始化O(V)+BFS操作O(E)=O(V+E)BFS求单源最短路径源点入队且当前总距离为0While(队列非空){取队首元素并popif(队首为终点)返回总距离点标记为访问过遍历队首点相连的所有点{if(点没被访问)这个点和总距离加上这个边权入队}}Floyd-Warshell算法求传递闭包基本思想：dp[i][j]=min(dp[i][k

8、]+dp[k][j],dp[i][j])记得循环顺序：k--->i--->j!!!