DIjkstra和BellmanFord算法之间的区别
我正在研究关于最短路径算法的论文.我不明白一件事......
我已经对dijkstras算法进行了可视化.1)这是正确的吗？或者我做错了什么？2)如何看待Bellman-Ford算法？正如我寻找差异一样,我发现"Bellman-ford:基本思想与Dijkstra非常相似,但它不是选择最短距离的邻居边缘,而是选择所有邻居边缘." 但是dijkstra还会检查所有顶点和所有边缘,不是吗？
dijkstra假设路径的成本是单调增加的.加上有序搜索(使用优先级队列),当你第一次到达一个节点时,你已经通过最短路径到达了.
负权重不是这样.如果你使用具有负权重的dijkstra,那么你可能会发现后面的路径比之前的路径更好(因为负权重改善了后续步骤的路径).
所以在bellman-ford中,当你到达一个节点时,你会测试新的路径是否更短.相比之下,使用dijkstra,你可以剔除节点
在一些(大多数)案例中,dijkstra不会探索所有完整路径.例如,如果G仅链接回C,那么通过G的任何路径将是更高的成本,任何通过C. bellman-ford仍将考虑通过G到F的所有路径(dijkstra永远不会看那些因为它们的成本更高,通过C).如果它不这样做,它不能保证找到负循环.
这是一个例子:上面从不计算路径AGEF.当你从G到达时,E已被标记为已访问过.