数据结构最短路径PPT教学课件

《最短路径算法》PPT课 件
探索最短路径算法的奥秘，了解其在各领域中的应用，以及选择最佳算法的 依据，展望最短路径算法的未来。
最短路径算法简介
最短路径问题的定义和最短路径算法的广泛应用。
单源最短路径算法
1
贝尔曼-福德算法2 Nhomakorabea算法思想：通过利用松弛操作，逐步更新节 点之间的最短路径。
算法步骤：进行N-1次松弛操作，其中N为节 点数，再进行一次检查负权边。
电路板布线
通过最短路径算法规划电路板 上元件的布线路径，减小电路 的延迟，提高性能。
应用最短路径算法的问题探讨
1 负权边问题
2 负环问题
遇到边权值为负数的情况，部分最短路径算法需 要特殊处理。
当图中存在负权环时，部分最短路径算法无法得 到准确的最短路径。
最短路径算法总结
1 各种算法的优劣
不同最短路径算法在不同场景下有不同的优劣，需要根据具体情况进行选择。
算法复杂度分析：时间复杂度为O(V*E)，V 为节点数，E为边数。
迪杰斯特拉算法
算法思想：通过记录已知最短路径和待确认 节点，逐步更新最短路径。
算法步骤：从起点出发，不断更新最短路径， 直到所有节点都被确认为最短路径。
算法复杂度分析：时间复杂度为O(V^2)，V 为节点数。
多源最短路径算法
1
弗洛伊德算法
算法思想：通过动态规划，逐步更新节点间 的最短路径。
算法步骤：利用矩阵记录节点间最短路径， 逐步更新矩阵，得到所有节点的最短路径。
算法复杂度分析：时间复杂度为O(V^3)，V为 节点数。
最短路径算法的应用实例
地图导航
使用最短路径算法规划最佳行 驶路线，提供准确的导航指引。
网络路由

vj
v2
v4
v3
v5
s
{v0,v2} {v0 ,v2 ,v4} {v0 ,v2 ,v4 ,v3} {v0 ,v2 ,v4 ,v3 ,v5}
S之外的当前最 短路径之顶点
(v0,v2)+ (v2,v3)<(v0,v3)
与最小生成树的不同点：路径是累加的！
§7.6 最短路径
所有顶点对之间的最短路径(Floyd算法)
V2
3
V1
2
-4 7
V5
6
4
V3
8
-5 1
V4
D4
12345 1 0 3 -1 4 -4 2 3 0 -4 1 -1 37 4 0 5 3 4 2 -1 -5 0 -2 58 5 1 6 0
P4
12345 1 nil 1 4 2 1 2 4 nil 4 2 1 3 4 3 nil 2 1 4 4 3 4 nil 1 5 4 3 4 5 nil
V2
3
V1
2
-4 7
V5
6
4
V3
8
-5 1
V4
D1
12345 1 0 3 8 ∞ -4 2∞0∞1 7 3∞4 0∞∞ 4 2 5 -5 0 -2 5∞∞∞6 0
P1
12345 1 nil 1 1 nil 1 2 nil nil nil 2 2 3 nil 3 nil nil nil 4 4 1 4 nil 1 5 nil nil nil 5 nil
E ① F→A：
24
② F→B→A： 5＋18=23
5
6 18
9
12 15
③ F→B→C→A：5+7+9=21

❖ 知识就是财富 ❖ 丰富你的人生
71、既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。——康德 72、家庭成为快乐的种子在外也不致成为障碍物但在旅行之际却是夜间的伴侣。——西塞罗 73、坚持意志伟大的事业需要始终不渝的精神。——伏尔泰 74、路漫漫其修道远，吾将上下而求索。——屈原 75、内外相应，言行相称。——韩非
数据结构：最短路径算法
•
46、寓形宇内复几时，曷不委心任去 留。
•
47、采菊东篱下，悠然见南山。
•
48、啸傲东轩下，聊复得此生。
•
49、勤学如春起之苗，不见其增，日 有所长 。
•
50、环堵萧然，不蔽风日；短褐穿结 ，箪瓢 屡空， 晏如也 。
Байду номын сангаас 谢谢你的阅读

• void Dijkstra(MGraph *G,int v1,int n)
•{
•
int D2[MVNum],p2[MVNum];
•
int v,i,w,min;
•
enum boolean S[MVNum];
•
for(v=1;v<=n;v++)
•
S[v]=FALSE;
•
D2[v]=G->arcs[v1][v];
for(j=1;j<=n:j++)G->arcs[i][j]=Maxint;
•
printf("输入%d条边的i、j及w:\n",e);
•
for(k=1;k<=e;k++){
•
scanf("%d,%d,%d",&i,&j&w);
•
G->arcs[i][j]=w;
•
}printf("有向图的存储结构建立完毕!\n");
•
S[v]=TRUE;
•
for(w=1;w<=n;w++)
•
if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){
•
D2[w]=D2[v]+G->arcs[v][w];
•
p2[w]=v;
•
}
•}
• printf("路径长度 路径\n");
2020/12/11
7
费洛伊德算法
• （3）费洛伊德算法：
• 费洛伊德算法的思想:首先考虑路径<Vi,V1>和<V1,Vj>是否存 在。如果存在，则比较路径<Vi,Vj>和<Vi,V1,Vj>的路径长度， 取长度较短者为当前所求的最短路径。然后考虑从Vi到Vj是否含 有顶点V2为中间顶点的路径<Vi，…，V2…,Vj>,若没有，则其 最短路径为之前所求，若有，则<Vi，…，V2…,Vj>可以分解为 <Vi,…V2>和<V2,…,Vj>,而其为前一次找到的中间顶点序号不 大于一的最短路径，将两者相加记为路径长度，比较该长度与前 一次的中间顶点序号不大于一的，取其最短的作为当前求的从Vi 到Vj的中间顶点长度不大于二的最短路径，直到选出不大于N的 最短路径为止。