图- 最短路径 (一)
发布网友
发布时间：2023-10-15 02:39
共1个回答
热心网友
时间：2023-11-12 18:20
带权图的最短路径问题
带权图的最短路径问题
带权图的最短路径问题即求两个顶点间长度最短的路径
其中 路径长度不是指路径上边数的总和 而是指路径上各边的权值总和
路径长度的的具体含义取决于边上权值所代表的意义
【例】交通网络中常常提出的如下问题就是带权图中求最短路径的问题
( )两地之间是否有路相通?
( )在有多条通路的情况下 哪一条最短?
其中:交通网络可以用带权图表示 图中顶点表示城镇 边表示两个城镇之间的道路 边上的权值可表示两城镇间的距离 交通
费用或途中所需的时间等等
交通网络的表示
由于交通网络存在有向性 所以一般以有向网络表示交通网络
【例】设A城到B城有一条公路 A城的海拔高于B城 若考虑到上坡和下坡的车速不同 则边和边 上表示行驶时间的权
值也不同 即和 应该是两条不同的边
源点和终点
习惯上称路径的开始顶点为源点(Source) 路径的最后一个顶点为终点(Destination)
为了讨论方便 设顶点集V={ … n } 并假定所有边上的权值均是表示长度的非负实数
单源最短路径问题
(Single Source Shortest PathsProblem)
单源最短路径问题 已知有向带权图(简称有向网)G=(V E) 找出从某个源点s∈V到V中其余各顶点的最短路径
边上权值相等的有向网的单源最短路径
用求指定源点的BFS生成树的算法可解决
迪杰斯特拉(Dijkstra)算法求单源最短路径
由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法
( )按路径长度递增序产生各顶点最短路径
若按长度递增的次序生成从源点s到其它顶点的最短路径 则当前正在生成的最短路径上除终点以外 其余顶点的最短路径均已生
成(将源点的最短路径看作是已生成的源点到其自身的长度为 的路径)
【例】在有向网G 中 假定以顶点 为源点 则它则其余各顶点的最短路径按路径递增序排列如右表所示
lishixin/Article/program/sjjg/201311/23823
