[SOLVED] 有向图为道路网络模型

• 有向图 为道路网络模型

其中网络中节点集合表示实际道路网络的交叉路口集合，是网络中连接节点的有向弧段集合，为节点的属性值集合，为弧的属性值集合。

对于任意节点，定义集合为节点的后继节点所构成的集合，集合为节点的前任节点所构成的集合。

表示网络中各弧段的属性值集合，，表示弧段属性值(车辆在该弧段(路段)上行驶所需要的时间)。

表示网络中各节点的属性值集合,，其中为节点的属性值，表示当车辆从路段行驶到路段过程中在节点(路口)处停留等待所耗费的时间。

• 算法基本思想

从终点D出发，逐步向外探寻从网络中经过以某一（或某些）节点i为出发点的一条（或几条）弧段(i，j)到终点D的最小行车时间路径。

• 符号说明

：在算法执行过程中具有B标号的弧段集合，是有向图的弧段集合的一个子集，对于任意，经过该弧段到终点的最小行车时间已经明确可知。

：在算法执行过程中具有R标号的弧段集合，是有向图的弧段集合的一个子集，对于任意，经过该弧段到终点的最小行车时间未知，但该弧段已经存在于构建的广度优先搜索树中；该集合是一个栈集合，即该集合中的任一弧段在算法的执行过程中按照“先进后出”的顺序进行处理。

：在算法执行过程中节点集合的一个子集，对于任意，弧段不具有B标号。

：在算法执行过程中节点集合的一个子集，对于任意，弧段不具有B标号。

：在算法执行过程中有向图的节点集合的一个子集合，该集合是一个队列集合，即该集合中任一节点在算法的执行过程中按照“先进先出”的顺序进行处理。

• 具体步骤

表4-4表示每段弧的属性值；表4-5表示每个节点的属性值；

表4-6表示算法执行过程

表4-4 弧的属性值

Time Cost	Time Cost	Time Cost	Time Cost	Time Cost	Time Cost
3.4	3	1	4.5	2.5	4.5

表4-5 节点的属性值

Time Cost	Time Cost	Time Cost	Time Cost	Time Cost	Time Cost
1	3.2	3.5	1	4	5

算法过程：

• 利用公式求的值
• 记录其后继弧段 ，其中

下面为路径弧段向量的更新过程，逆序进行。n表示循环次数。

n=1	逆序来看，先计算不同时间段，节点5到终点的最小行车时间。
结果

n=2
结果

n=3
结果

n=4
结果

n=5
结果

n=6
结果	算法结束

算法结果为：从节点1到节点5的最短路径为1->2->3->4->5 ,最短时间为18.4

要求：

• 代码模块化
• 输入格式

图的边数m和节点数n为： 输入图的m条边： 输入图的n个节点： 输入起始节点： 输入终点：

3 输出格式为

起始节点到终点的最短时间为： 起始节点到终点的最短路径为：