心算口訣表完整版 迪杰斯特拉算法為什么不能有負權(quán)邊？
迪杰斯特拉算法為什么不能有負權(quán)邊？因為Dijkstra是貪婪的，他總是找到一個離源點最近的點（Dmin），然后將距離確定為從該點到源點（d[i]<--Dmin）的最短路徑；但是如果存在負權(quán)重邊，則
迪杰斯特拉算法為什么不能有負權(quán)邊？
因為Dijkstra是貪婪的，他總是找到一個離源點最近的點（Dmin），然后將距離確定為從該點到源點（d[i]<--Dmin）的最短路徑；但是如果存在負權(quán)重邊，則可以首先傳遞一個不離源點最近的子優(yōu)勢（Dmin “），然后通過負權(quán)邊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遞減。