- 有向图为道路网络模型
其中网络中节点集合表示实际道路网络的交叉路口集合，是网络中连接节点的有向弧段集合，为节点的属性值集合，为弧的属性值集合。
对于任意节点，定义集合为节点的后继节点所构成的集合，集合为节点的前任节点所构成的集合。
表示网络中各弧段的属性值集合，，表示弧段属性值(车辆在该弧段(路段)上行驶所需要的时间)。
表示网络中各节点的属性值集合,，其中为节点的属性值，表示当车辆从路段行驶到路段过程中在节点(路口)处停留等待所耗费的时间。
- 算法基本思想
从终点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 输出格式为
| 起始节点到终点的最短时间为：
起始节点到终点的最短路径为：
|