鏈路狀態路由協議 - Dijkstras算法

Question

N-網絡 R-路由器

在上面的圖片中，可以看到一個關於鏈路狀態路由協議的問題。爲此，我知道你首先加入N3和N4，然後看成本，2小於4，所以N4變成永久的，但是當N4變成永久的時候，它會加上R4和R7或者你只是選擇其中一個？

Answer 1

這個例子有點混亂，因爲有箭頭，但我想我們可以假設這是一個無向圖，頂點集爲N union R。

從wikipedia，這些都是Dijkstra的步驟：

1. 分配到每一個節點的暫行距離值：它設爲零，我們最初的節點和無窮大的所有其他節點。
2. 標記未訪問的所有節點。將初始節點設置爲當前。創建一組未經訪問的節點，稱爲未訪問集合，由除初始節點之外的所有節點組成。
3. 對於當前節點，考慮所有未訪問的鄰居並計算它們的暫定距離。
4. 當我們完成考慮當前節點的所有鄰居時，將當前節點標記爲已訪問並將其從未訪問集中移除。被訪問的節點將不會再次被檢查。
5. 如果目標節點已被標記訪問（規劃兩個特定節點之間的路由時），或者未訪問集中節點間的最小暫定距離爲無窮大（計劃完整遍歷時），則停止。該算法已完成。
6. 選擇標有最小的暫行距離未訪問節點，並將其設置爲新的「當前節點」，然後回到步驟3.

讓我們來看看這些步驟你的情況。

• Ad1。 R3是初始節點，所以它得到距離0。
• Ad2。 R3是最新的。
• Ad3。請訪問N3和N4，並分別將它們的試驗距離設置爲4和2。
• Ad4。完成後，標記R3。
• Ad5。 -
• Ad6。選擇N4作爲當前節點並返回步驟3.
• Ad3。請訪問R4和R7，並分別將它們的臨時距離設置爲6和3。
• Ad4。完成後，標記爲N4。
• Ad5。 -
• Ad6。選擇R7作爲當前節點並返回步驟3。

依此類推。

Answer 2

Dijkstra算法的關鍵在於，在處理它之前，您從不放棄節點。

Step 1 : R3 
N4 - 2 
N3 - 4 

Step 2 : N4 
R7 - 3 
N3 - 4 
R4 - 6 

Step 3 : R7 
N3 - 4 
R4 - 6 
N6 - 9 

在這個步驟中，您有N3作爲最接近與R3被留下，所以你做N3

Step 4 : N3 
R4 - 6 
R8 - 6 
R2 - 6 
N6 - 9 

注意，每一步之後有一個排序。所以最低優先級隊列應該有所幫助。