k最短路径算法 前K条最短路径算法


k 条最短路径算法

戴维编译

一、算法说明

?Deletion
Algorithm
删除算法的核心是通过在有向图中已有的最短路径上删除某条弧,并寻找替换的弧来寻找下一条可选的最短路径。删除算法实际上是通过在有向图中增加附加节点和相应的弧来实现的。描述算法如下:

1.
利用 Dijkstra 算法求得有向图 (N,A) 中以开始节点 s 为根的最短路径树(注意,这里的最短路径树并不是最小生成树,因为 Dijkstra
算法并不保证能生成最小生成树),标记从开始节点 s 到结束节点 t 之间的最短路径为 pk , k=1 。

k最短路径算法 前K条最短路径算法

2.如果k小于要求的最短路径的最大数目K,并且仍然有候选路径存在,令当前路径
p=pk , 转3。否则,程序结束。

3.
找出当前路径 p 中从第一个节点开始的入度大于 1 的第一个节点,记为 nh 。如果 nh 的扩展节点 n’ h 不在节点集 N 中,则转 4 ,否则找出路径
p 中 nh 后面所有节点中,其对应的扩展节点不在 N 中的第一个节点,记为 ni ,转5 。

4.为节点
nh 构建一个扩展节点 n’ h ,并把其添加到集合 N 中,同时从图 (N,A) 中所有 nh 的前驱节点 连接一条到 n’ h
的弧,弧对应的权重不变,添加这些弧到弧集 A 中,但 nh 在 p 中的前一个节点 nh-1 除外。计算从开始节点 s 到 n‘h 的最短路径,并记 ni =
nh+1 。

5.
对于 p 中从 ni 开始的所有后续节点,不妨记为 nj ,依次执行如下操作:

5.1
添加 nj 的扩展节点 n’ j 到节点集合 N 中。

5.2
除了路径 p 中 nj 的前一个节点 nj-1 外,分别连接一条从 nj 前驱节点到其扩展节点 n’ j 的弧,弧上的权值保持不变,并把这些弧添加到弧集 A
中。另外,如果 p 中 nj 的前一个节点 nj-1具有扩展节点 n’ j-1 的话,也需要连接一条从 n’ j-1 到 n’ j 的弧,权值和弧 (nj-1
, nj ) 的权值相等。

5.3
计算从开始节点 s 到 n’ j 的最短路径。

6.
更新当前最短路径树,求得从开始节点 s 到结束节点的当前扩展节点 t(k)’ 之间的最短路径为第k 条最短路径,令 k=k+1 ,转 2 继续。

在上述步骤
4、5、6
中均需要计算从开始节点到当前扩展节点的最短路径,因为程序开始时便生成了以开始节点为根的最短路径树,那么只要在扩充节点时,记录下每个新节点相对于开始节点的最短路径中其前一个节点编号以及从开始节点到当前节点的最短路径长度,就可以很容易求得任意时刻有向图中从开始节点到结束节点(或其扩充节点)之间的最短路径。
?

?
?扩展节点 :上一条最短路径上的节点可能会在求取下一条最短路径的过程中进行扩展
,也就是在上次节点集合的基础上增加相应的新节点,这些新的节点均称为扩展节点,其会继承被扩展结点的邻接边关系(具体请参见上述步骤4,5)。一个扩展节点仍然可能会在求取下一条最短路径的时候进行扩展,表现在示例图中就是在一个节点标记后面加一撇表示是在原始节点上扩展,加两撇表示是在上次扩展节点上再扩展,依次类推。

前K条最短路径算法_最短路径算法

?
?前驱节点 :就是最短路径中某个节点的前一个节点。

  

爱华网本文地址 » http://www.413yy.cn/a/8104060103/166442.html

更多阅读

有向图的最短路径之Floyd算法 带权有向图最短路径

顶点对之间的最短路径是指:对于给定的有向网G=(V,E),要对G中任意一对顶点有序对V、W(V≠W),找出V到W的最短距离和W到V的最短距离。解决此问题的一个有效方法是:轮流以每一个顶点为源点,重复执行迪杰斯特拉算法n次,即可求得每一对顶

三角形内周长最短的内接三角形 圆内接三角形周长

问题是这样的:证明:在△ABC的每条边上各取一点D、E、F,△DEF称为△ABC的内接三角形。试在锐角三角形ABC的所有内接三角形中,求周长最短的三角形。证明:可将此题分三步来做(1)设D是BC上固定点,求此时的周长最短的内接三角形。  作D关于A

朝抵抗力最大的路径走(教案) 最短路径教案

朝抵抗力最大的路径走(教案)导入:诗人汪国真在《山高路远》一诗中写道:“既然选择了远方,便只顾风雨兼程。”人的一生将会经历无数的挫折和磨难。面对它,我们是退却,中途放弃,还是勇往直前、逆流而进?今天我们学习朱光潜先生写的《朝抵

第4节:人力资源规划主要知识点(4)

系列专题:《新编企业人力资源管理方案写作》  第二十五条人力资源部根据“考核表”发给《试用期满通知》。  第二十六条人力资源部发出《试用期满通知》后,并依不同的批示,分别办理下列事项:  (一)试用不合格者,另发给通知单。  (

声明:《k最短路径算法 前K条最短路径算法》为网友矫情男分享!如侵犯到您的合法权益请联系我们删除