Min(a, b )=5 Min (b, c)=3 5 Min(aC=5+6=11 b(8 回顾上图 导致无法使用标准算法原因 Min(ab)和Min(b,c)之间需要计算附加耗时 不用换车的线路成为最佳路径 改进的想法:一次性地处理不用换车的情况
• 回顾上图 • 导致无法使用标准算法原因: – Min(a,b)和Min(b,c)之间需要计算附加耗时 – 不用换车的线路成为最佳路径 • 改进的想法:一次性地处理不用换车的情况 5 6 7 a c Min(a,b)=5 Min(b,c)=3 Min(a,c)=5+6=11 3 b(8)
模型的求解 标准算法: 每次选择一个新顶点进行扩展 所有顶点扩展完毕即为最优解 ·修改后的算法 每次对一个顶点所能选择的所有公交线路扩 展 -所有不用换乘就能到达的顶点均在一次中处 理 所有顶点扩展完毕即为最优解
模型的求解 • 标准算法: – 每次选择一个新顶点进行扩展 – 所有顶点扩展完毕即为最优解 • 修改后的算法 – 每次对一个顶点所能选择的所有公交线路扩 展 – 所有不用换乘就能到达的顶点均在一次中处 理 – 所有顶点扩展完毕即为最优解
算法描述 次将扩展出多个顶点用最小值堆保存 ·初始:起点对应的节点S入堆;并赋予标 志信息Tme(S)=0 取堆顶,对此定点,逐一枚举所有不用换乘 就能到达的顶点,更新堆中对应点的标志信 不断重复取堆顶的过程直到取出的顶点为 终目标T Tme(T即为所求
算法描述 • 一次将扩展出多个顶点,用最小值堆保存 • 初始: 起点对应的节点S入堆；并赋予标 志信息Time(S)=0 • 取堆顶,对此定点,逐一枚举所有不用换乘 就能到达的顶点,更新堆中对应点的标志信 息. • 不断重复取堆顶的过程,直到取出的顶点为 最终目标T • Time(T)即为所求
举例说明算法步骤 12 2 9 d 15 8 9 22 5 5 20 考虑顶点b到顶点g的路径
举例说明算法步骤 3 2 4 5 1 3 2 a b c d e f g 12 9 8 15 9 20 6 11 9 22 5 考虑顶点b到顶点g的路径
问题重述 加入步行的因素,即任意两个车站之间人器 可能通过步行到达,并给出步行的时间代价 C2
问题重述 • 加入步行的因素,即任意两个车站之间人都 可能通过步行到达,并给出步行的时间代价