即使在具有負邊權重的圖中，我們是否可以使用Dijkstra's來找到最短路徑？

Question

假設我有一個最小邊權重爲-100的圖。我可以將100作爲偏移量添加到所有邊緣並使用Dijkstra算法嗎？

請幫我理解爲什麼這樣的方法給出了錯誤的解決方案。

Answer 1

將100添加到每個邊權重會給出錯誤的解決方案，因爲它會懲罰比具有更少邊的路徑更多的邊的路徑。

例如，假設我們有一個圖，從點A到點B的最短路徑有3條邊和總距離爲5.假設從點A到點B的其他路徑有2條邊，但總距離爲10.

如果我們爲每個邊權重添加100，那麼第一條路徑的成本爲305，而第二條路徑的成本爲210.所以第二條路徑變得比第一條路徑短。

因此，我們可以得出結論，將偏移或偏置到每個邊緣權重不一定保持最短路徑。