• 所有问题

    • 为什么Dijkstra算法不能处理有负权值的图？

    如题所述

    举报该问题
    推荐答案   2013-08-08
    很简单
    Dijkstra不断维护最小，每次走使当前权值最小的能边，那么一旦有负的权值
    每次从这里通过总的权值和就会越来越小，那么这条边会一直是最小边，
    Dijkstra算法会使你陷入死循环，不断在这条负权值的边两端的点来回
    可以理解么？
    温馨提示：答案为网友推荐，仅供参考
    其他回答
    第1个回答  2011-11-19
    不能处理环这个要说么追问

    环也不能处理？这个真要说一下！

    相似回答
    Dijkstra算法为什么权值不能是负值答：归入S集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与S 内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值 结果小于a原先确定的最短路径长度，而此时a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果...
    大家正在搜
    迪杰斯特拉算法权值不能为负的原因prim算法如果有相同的权值prim算法权值可以为负吗普里姆算法最小生成树的权值权值为负数的最短路径最小生成树kruskal算法例题最小生成树kruskal算法最小生成树的权值计算Kruskal算法
    相关问题
    Dijkstra算法权值为什么不能为负？权值为负是怎样一种情...
    dijkstra算法边上带有负权值时不能适用，但是我自己按照...
    Dijkstra算法为什么权值不能是负值
    最短路径 Dijkstra 算法为什么边上的权值非负阿？