各ペア間で同じ距離のノード間の最短距離を求めるアルゴリズムはありますか？

Question

つまり、ノード間で移動する回数を最小限にする既知のアルゴリズムがあるかどうかは疑問です。例えば、私は

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

のようにツリーを持っているかもしれないと私はGからAからの最短経路を求めています。これはA->B->C->GまたはA->E->F->Fのいずれかになります。

は、より具体的にこれを置くために、私が持っている

var nodes = new List<Node> 

どこ

class Node 
{ 
    // ... properties 

    List<Node> Neighbors; 
} 

と私はstartからendへの最短経路を見つけたいnodesでいくつかのNode start, end;を与えられました。

すべてのノード間に距離1のDjikstraのアルゴリズムを使用することができますが、この場合にはより良い方法があると思いますか？

Answer 1

BFSトラバーサルは、線形時間O（M + N）問題を解決する原因この問題を解決するための最速の方法です。

BFSは、第1のエッジの距離ですべてのノードがトラバースされ、2辺の距離で、それはレベルによってノードレベルを横切る意味レベル順トラバーサル :(となるようにトラバースとされている。 ）。

Answer 2

距離1またはBFSのダイクストラ - 両方を適用できます。この種の問題は、これらの2つのアプローチによって解決されることが知られています。他に良い方法はないと思います。