迪杰斯特拉算法為什么不能有負(fù)權(quán)邊？因?yàn)镈ijkstra是貪婪的，他總是找到一個(gè)離源點(diǎn)最近的點(diǎn)（Dmin），然后將距離確定為從該點(diǎn)到源點(diǎn)（d[i]<--Dmin）的最短路徑；但是如果存在負(fù)權(quán)重邊，則

迪杰斯特拉算法為什么不能有負(fù)權(quán)邊？

因?yàn)镈ijkstra是貪婪的，他總是找到一個(gè)離源點(diǎn)最近的點(diǎn)（Dmin），然后將距離確定為從該點(diǎn)到源點(diǎn)（d[i]<--Dmin）的最短路徑；但是如果存在負(fù)權(quán)重邊，則可以首先傳遞一個(gè)不離源點(diǎn)最近的子優(yōu)勢(shì)（Dmin “），然后通過負(fù)權(quán)邊L（L<0）使路徑之和變小（Dmin”），這樣Dijkstra就會(huì)丟失。

例如，n=3，鄰接矩陣：

0，3，4

3，0，-2

4，-2，0

使用Dijkstra得到d[1，2]=3，實(shí)際上，d[1，2]=2，這使得路徑通過1-3-2遞減。