2009 年春季
图算法及其在通信网络中的应用
5 / 55
问题描述
单源最短路问题
给定有向加权图 G(V, E) ,给定源点 / 起始点 s ,
求从 s 出发到 V 中其它所有顶点的权重最小的路
径。
所有这些最短路构成的是一个怎样的子图?
树最短路径树
假设
1) 权重为正整数 ;
2) 连通图 ;
3) 存在多条最短路
时 , 只求 1 条 .
为什么一定是树?
最短路上的子路径也是最短路
最短路径树是生成树么?
是的
最短路径树是最小生成树么?
不一定
A
S
B
C
1
1
2
2
1
A
S
B
C
1
2
2
A
S
B
C
1
2
1