是否有已知的算法來找出每對之間距離相同的節點之間的最短距離？

Question

換句話說，我不知道是否有尋找的節點間移動的次數最少從一個到另一個得到一個已知的算法。例如，我可能有這樣

A - B - C - D 
\ /\ 
    E - F - G 

一棵樹，我想從A到G的最短路徑。那將是A->B->C->G或A->E->F->F。

爲了把這個更具體而言，我有一個

var nodes = new List<Node> 

其中

class Node 
{ 
    // ... properties 

    List<Node> Neighbors; 
} 

，並給出了nodes我想找到start到end最短路徑一些Node start, end;。

我知道我可以使用Djikstra的算法，每個節點之間的距離1，但我想有一個更好的方式對於這種情況？

Answer 1

的BFS遍歷是解決這個問題，因爲它會在線性時間O（M + N）解決問題的最快方式。

的BFS爲級順序遍歷這意味着它通過遍歷級節點級別:(首先在1個邊緣的距離的所有節點被遍歷並以2個邊緣的距離被遍歷等。 ）。

Answer 2

迪傑斯特拉與距離1或BFS - 兩者都可以被應用。這類問題很有名，可以通過這兩種方法解決。我認爲還有其他更好的辦法。