最短路径DIJKSTRA.ppt

三、经典问题最短路径问题
V0
V1
V2
V3
V4
V5
100
10
30
10
5
50
20
60
起点
终点
最短
路径
路径长度
V0
V1
无
V2
(V0,V2)
10
V3
(V0,V4,V3)
50
V4
(V0,V4)
30
V5
(V0,V4,V3,V5)
60
求最短路径的基本思想:
按照最短路径的长度递增的次序依次求得源点到其余各点的最短路径。
在这条路径上,必定只含一条弧,并且这条弧的权值最小。
路径长度最短的最短路径的特点:
假设,从源点到顶点V1的最短路径是所有最短路径中长度最短者。
路径长度次短的最短路径的特点:
它只可能有两种情况:或者是直接从源点到该点(只含一条弧);
或者是从源点经过顶点v1,再到达该顶点(由两条弧组成)。
路径长度第三短的路径特点:
它可能有三种情况:或者是直接从源点到该点(只含一条弧); 或者是从源点经过顶点v1,再到达该顶点(由两条弧组成);或者是从源点经过顶点v2,再到达该顶点。
其余最短路径的特点:
它或者是直接从源点到该点(只含一条弧); 或者是从源点经过已求得最短路径的顶点,再到达该顶点。
迪杰斯特拉算法:
0)准备工作:
设置辅助数组Dist,其中每个分量Dist[k] 表示:当前所求得的从源点到其余各顶点 k 的最短路径。
1)在所有从源点出发的弧中选取一条权值最小的弧,即为第一条最短路径。
V0和k之间存在弧
V0和k之间不存在弧
其中的最小值即为最短路径的长度。
2)修改其它各顶点的Dist[k]值。(为什么?)
具体操作:假设求得最短路径的顶点为u,若 Dist[u]+[u][k]<Dist[k]
则将 Dist[k] 改为 Dist[u]+[u][k]。
3)选出下一条最短路径,重复以上操作,直到求出所有的最短路径
搞定!!!
说明:求两点之间的最短路径和求一个点到其余所有点的最短路径工作量一样。