下载文档原格式
图论与网络模型一、最短路径1、问题 在加权图),,(W E V G =中求v u ,两点之间的路径),(v u P P =，使该路径上的边权之和最小。
例如，求下图中从1v 到其他顶点的最短路径。
2、模型 ∑E ∈=)()(w )(min P e e P W3、算法（1）求给定两点之间最短路径的Dijkstra 算法，计算复杂性为)(2n O ，其中V =n ; 例如，对上图，当i v 与j v 不相邻时，取∞=)(j i v v w 。
1） 标号∞========)()()()()(,14)(,10)(,0)(87654321v l v l v l v l v l v l v l v l ,取固定标号顶点集合为},{21v v S =，临时标号顶点集合为},,,,,,{876543v v v v v v T =得1v 到2v 的最短路径为21v v ，权为10。
2）令14}10,14min{)}()(),(min{)(32233=∞+=+=v v w v l v l v l∞=∞+∞=+=∞=∞+∞=+=∞=∞+∞=+==+∞=+==+∞=+=}10,min{)}()(),(min{)(}10,min{)}()(),(min{)(}10,min{)}()(),(min{)(20}1010,min{)}()(),(min{)(20}1010,min{)}()(),(min{)(8228872277622665225542244v v w v l v l v l v v w v l v l v l v v w v l v l v l v v w v l v l v l v v w v l v l v l取},,,,,{),,,{87654321v v v v v T v v v S ==得1v 到3v 的最短路径为,31v v 权为14。
重复上述步骤，可分别得1v 到87654,,,,v v v v v 的最短路径。
