美文网首页
第七章:狄克斯特拉算法

第七章:狄克斯特拉算法

作者: 杨殿生 | 来源:发表于2018-10-15 09:56 被阅读0次

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

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

    实现

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

    相关文章

      网友评论

          本文标题:第七章:狄克斯特拉算法

          本文链接:https://www.haomeiwen.com/subject/jlixzftx.html