Dijkstra 最优避堵路线演示

返回主页
该算法即 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];动画演示到某楼栋时,其链表会高亮