|
|
|
|
知识路径： > 应用数学 > 图论应用 > 图论应用 >
|
|
|
被考次数：2次
|
|
|
被考频率：
低频率
|
|
|
总体答错率：
54%
|
|
知识难度系数：
|
|
|
考试要求：
掌握
|
|
|
相关知识点：6个
|
|
|
|
|
带权图的最短路径问题即求两个顶点间长度最短的路径，其中路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。路径长度的具体含义取决于边上权值所代表的意义。
|
|
|
|
已知有向带权图（简称有向网）G=（V，E），找出从某个源点s∈V到V中其余各顶点的最短路径，称为单源最短路径。
|
|
|
|
目前，求单源最短路径主要使用迪杰斯特拉（Dijkstra）提出的一种按路径长度递增序列产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。
|
|
|
|
迪杰斯特拉算法的基本思想是：设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。
|
|
|
|
（1）初始化：初始化时，只有源点s的最短距离是已知的（SD（s）=0），故红点集S={s}，蓝点集为空。
|
|
|
|
（2）重复以下工作，按路径长度递增次序产生各顶点最短路径：在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。
|
|
|
|
若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径；从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD（v）。
|
|
|
|
根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：
|
|
|
|
|
|
距离为：源点到红点n最短距离+<红点n，蓝点k>的边长
|
|
|
|
为求解方便，可设置一个向量D[0..n-1]，对于每个蓝点v∈（V-S），用D[v]记录从源点s到达v且除v外中间不经过任何蓝点（若有中间点，则必为红点）的“最短”路径长度（简称估计距离）。若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i]i∈（V-S）}，则D[k]=SD（k）。
|
|
|
|
初始时，每个蓝点v的D[c]值应为权w<s，v>，且从s到v的路径上没有中间点，因为该路径仅含一条边<s，v>。
|
|
|
|
将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=<s，…，k，j>。且D[j]减小的新路径P只可能是由于路径<s，…，k>和边<k，j>组成。所以，当length（P）=D[k]+w<k，j>小于D[j]时，应该用P的长度来修改D[j]的值。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
因此，从s到t的最短路径长度为81，路径为s→2→3→5→6→t。
|
|
|
