第七章:狄克斯特拉算法
2018-10-15 本文已影响0人
杨殿生
找出图中最快路径(加权图)
1,找出最便宜的结点
2,检查是否有前往它们的更短路径,如果有,更新该结点邻居的开销
3,重复这个过程
4,计算最终路径
狄克斯特拉算法只适用于有向无环图。如果有负权边,就不能使用狄克斯特拉算法(负权边的图使用——贝尔曼-富德算法)
实现
1,需要三个列表,graph,costs,parents
找出图中最快路径(加权图)
1,找出最便宜的结点
2,检查是否有前往它们的更短路径,如果有,更新该结点邻居的开销
3,重复这个过程
4,计算最终路径
1,需要三个列表,graph,costs,parents