狄克斯屈标号法步骤 迪杰斯特拉算法为什么不能有负权边？

迪杰斯特拉算法为什么不能有负权边？

因为Dijkstra是贪婪的，他总是找到一个离源点最近的点（Dmin），然后将距离确定为从该点到源点（d[i]<--Dmin）的最短路径；但是如果存在负权重边，则可以首先传递一个不离源点最近的子优势（Dmin “），然后通过负权边L（L<0）使路径之和变小（Dmin”），这样Dijkstra就会丢失。

例如，n=3，邻接矩阵：

0，3，4

3，0，-2

4，-2，0

使用Dijkstra得到d[1，2]=3，实际上，d[1，2]=2，这使得路径通过1-3-2递减。

狄克斯屈标号法步骤 狄克斯特拉算法 狄克斯特拉算法基本思想

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。