第七章:狄克斯特拉算法

2018-10-15  本文已影响0人  杨殿生

找出图中最快路径(加权图)
1,找出最便宜的结点
2,检查是否有前往它们的更短路径,如果有,更新该结点邻居的开销
3,重复这个过程
4,计算最终路径

狄克斯特拉算法只适用于有向无环图。如果有负权边,就不能使用狄克斯特拉算法(负权边的图使用——贝尔曼-富德算法)

实现

1,需要三个列表,graph,costs,parents

上一篇下一篇

猜你喜欢

热点阅读