图解算法 第7章 狄克斯特拉算法
本章内容
加权图--使广度优先搜索失效,提高或增加某边权重(相当于公交地图的时间)
环&负权重--让狄克斯特拉算法不管用
狄克斯特拉算法(BFS:)
狄克斯特拉算法4个步骤:
- 找出最“便宜”的节点,最短时间内到达的节点
- 更新节点的邻居的开销
- 重复,直到对每个节点完成此操作
- 计算最终路径
权重weight:每条边的数字
加权图weight graph,非加权图unweight graph.
狄克斯特拉算法的适用范围:有向无环图(要不他会循环运行,没办法结束)