该算法即 Dijkstra(迪杰斯特拉)最短路算法:每次从候选列表 pq 中取出当前用时最短的楼栋并确定其最短用时;图采用链式前向星(
head[] + routes[])存图。点击「下一步」单步观察,或「自动播放」。
0.9s/步
步骤 0 / 0
校园楼栋路线图(起点:宿舍,终点:校门)
已确定最短用时
当前处理
在候选列表 pq 中
尚未到达
最优避堵路线
双击边上的数字可修改通行时长(回车保存)
当前操作
算法核心步骤
候选列表 pq(按用时升序,队首最短)
各楼栋状态(time / vis / pre)
| 楼栋 | time 最短用时 | vis 已确定 | pre 前驱 |
|---|
链式前向星存图
routes[i] = [到达楼栋 v, 时长 t, 下一条边 next]
head[]:
| 边序号 | v | t | next |
|---|
每个楼栋一条链表(共 7 条)
head[u] 指向楼栋 u 的链表头,节点存 [v 直达楼栋, t 直达时长, next];动画演示到某楼栋时,其链表会高亮