📦 Dial 算法(桶优化 Dijkstra)带节点/边染色
边权范围 0~10,适合小整数权值。点击节点选择起点,然后逐步执行算法。
染色说明: 当前正在处理的节点, 正在松弛的边。
📖 算法说明
- Dial算法使用“桶”代替优先队列,每个桶对应一个距离值。
- 初始化:源点放入桶0,其余距离无穷大。
- 按距离从小到大扫描桶:取出桶内所有节点,松弛其出边,将更新后的节点放入对应的新距离桶中。
- 因为边权小,桶数量有限,总复杂度 O(N·C + M),C为最大边权。
- 染色效果:每步处理时,当前节点变为橙色,被松弛的边变为红色,便于观察节点扩展顺序。