最短路径Dijkstra算法学习教案.pptx

会计学
1
最短路径(lùjìng)Dijkstra算法
第一页，共9页。
1 最短路径(lùjìng)
两点之间的最短路径(lùjìng)问题：
求从某个(mǒu ɡè)源点到其余各点的最短路径
每一对顶点之间的最短路径
第1页/共9页
第二页，共9页。
求从源点到其余各点的最短路径的算法的基本(jīběn)思想:
依最短路径的长度(chángdù)递增的次序求得各条路径
源点
v1
v2
…
其中，从源点到顶点v的最短路径(lùjìng)是所有最短路径(lùjìng)中长度最短者。
第2页/共9页
第三页，共9页。
2 Dijkstra算法(suàn fǎ)
单源最短路径问题是：
给定带权的有向图G=（V，E），源点v∈V，求从v到V中其余(qíyú)各顶点的最短路径。
如何(rúhé)求解上图中的最短路径问题，Dijkstra提出了一种解决方案。
第3页/共9页
第四页，共9页。
即迪杰斯特拉算法(suàn fǎ)，其基本思想如下：
设置(shèzhì)辅助数组Dist，其中每个分量Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径的长度。
1）在所有从源点出发的弧中选取(xuǎnqǔ)一条权值最小的弧，即为第一条最短路径。
V0和k之间存在弧
V0和k之间不存在弧
第4页/共9页
第五页，共9页。
3）每次从集合V-S中取出具有最短特殊路径长度的顶点(dǐngdiǎn)u，将u加到S中，同时对数组Dist做必要的修改。若 Dist[u]+[u][k]<Dist[k]
则将 Dist[k] 改为 Dist[u]+[u][k]。
其中，特殊路径指从源点到u中间只经过S中顶点(dǐngdiǎn)的路径。
2）设置一个(yī ɡè)顶点集合S，存放最短路径的终点。顶点k为当前最短路径的终点,将Vk 加入集合S中，而Dist[k]为最短路径的长度。
4) 重复操作(cāozuò)2）、3）共n-1次。由此求得图上其余各顶点的最短路径是依路径长度递增的序列。
第5页/共9页
第六页，共9页。
若带权图G如下所示，根据上述算法(suàn fǎ)来求解源点v0到v2的最短路径。
第6页/共9页
第七页，共9页。
根据以上分析和举例，不难得出(dé chū)狄杰斯特拉算法，其描述如下：
Void shortestPath(MGraph G,int V0, PathMatrix &P, ShortPathTable &D)
//P[v]表示最短路径，D[v]表示带权长度
//P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点
//final[v]为TRUE，即已经(yǐ jing)求得从v0到v的最短路径
{ for（v=0;v<;v++）{
final[v]=FALSE;
D[v]=[v0][v];
for(w=0;w<;w++) P[v][w]=FALS