弗洛伊德最短路徑算法？

Question

我覺得我有一些問題，在這裏 下面是我給

矩陣我應該找到的經過頂點K = 0， 1，2，3路徑的成本。 對於頂點K = 0，有

0，10，30，INF

15，0，INF，INF

INF，5,0，2

30,40,33,0

這是正確的嗎？有人能幫助我嗎？

Answer 1

讓我們試着解釋你的（中間？）結果。第一行顯示如下：

0, 10, 30, inf 

這意味着，有一個從頂點0到0的路徑與0成本，平凡，從頂點0到1的路徑以最小的成本10，和從頂點0〜2以路徑最低成本30.這不可能，因爲從頂點0到2有更便宜的路徑，而成本3是由初始成本矩陣給出的。因此你的實現有一個錯誤。如果你可以分享它，我們也可以指出它。

PS。即使這是一箇中間結果，矩陣中的費用也不會因Floyd-Warshall而增加，而只會減少。 （例如：證明）

Answer 2

據我瞭解，k=1的中間結果如下。其中，從集合{1}注意中間是允許的，即更好的路徑從要麼會從i到j或

000 010 003 inf 
015 000 018 inf 
inf 005 000 002 
030 004 033 000 

對於intutitive理解，與指數i和j的條目將是從i到j的最短路徑路徑i-0-j。