貝爾曼 - 福特算法步驟

假設有一個向圖，100-Vertexes如V_1---> V_2 ---> ... ---> V_100貝爾曼 - 福特算法步驟

邊緣的所有重量爲1。我們要使用Bellman-Ford算法來找到其他頂點1 (V_1)之間的最短路徑的數量和頂點。這個算法在每個步驟中以任意順序檢查所有邊。如果在一個步驟中V_1到所有其他頂點not changed之間的最短路徑（來自以前的值），算法將停止！ the number of steps in this algorithmsdepends on the order of inspecting edges。

這個算法中最大和最小步數是多少？爲什麼（2）選擇了這個問題的答案選項

a) 100, 10000 

b) 2, 100 

c) 100, 100 

d) 2, 99

任何人都可以形容我？

來源

2015-03-03 Ali Movagher

似乎學校正在讓你...... :-)我認爲你必須自己解決這個問題，你還能學到什麼？ – 2015-03-03 13:48:19

「V_1 ---> V_2 ---> ... ---> V_100」是什麼意思？這是一個鏈表。這是一個鏈表或一般圖嗎？ – IVlad 2015-03-03 13:58:41

不，它是一個有向圖v_1與v_2有邊，並且有一個邊到v_3等等。 @IVlad – 2015-03-03 14:03:01

Bellman-Ford算法在Wikipedia處給出。

如果選擇V_1和V_2這是兩個步驟。假設V_1到V_1不是允許的輸入，這可能不會變得更好，這可以通過單個步驟完成。

最壞的情況是，如果V_1和V_100作爲輸入給出：這需要100個步驟才能到達V_100。

的問題是：給出可能的輸入，什麼是最好的，什麼是可以在您的示例圖中邊之間發生的距離最壞的情況？

例：輸入是Bellman-Ford(Vertices, Edges, Soucre)
會發生什麼？
在這個特定的例子中，頂點是V_1到V_100，邊緣是E_1（從V_1到V_2等），並且源是V_1。步驟1：從頭開始，即我們知道從V_1到V_1的最短路徑。
第2步：遵循其中一條邊。只有一條邊，我們稱之爲E_1。此邊緣從V_1到V_2。該算法將遵循這個邊緣。現在我們現在從V_1到V_2的最短路徑沿着這條邊走1步。 V_1和V_2的步數爲2.這是最簡單的非平凡路徑。

現在確定V_1和V_100之間距離的結果。 V_1和V_100之間有99個邊緣，因爲E_99從V_99變爲V_100。這需要多少步？這個特定的圖表可以有更長的路徑嗎？

來源

2015-03-03 13:48:26 Beginner

你能否加一點細節？我沒有得到它！ – 2015-03-03 13:52:15

我們該怎麼做BL（v_1，v_2）？我認爲我們總是應該計算從v_1到所有其他人的最短路徑？ – 2015-03-03 14:26:16

貝爾曼 - 福特算法步驟

回答

相關問題