Dijkstraアルゴリズムのグラフは、DFSまたはBFSに似ていますか？

Question

私はこの質問に答える必要がありますが、私はどちらがより似ているか分かりません。 dijkstraアルゴリズムはBFSといくつかの点で似ていますが、DFSにも似ています。あなたは答えとその理由を教えてもらえますか？ありがとう！

Answer 1

どちらもありません。

ダイクストラは、実際に動的プログラミングdp[v] = min{dp[u] + w(u,v)} where u has already calculated and w(u, v) is the edge valueあります。

貪欲を使用する権利であることを証明することができます。

BFSとDFSはあなたが必要とする何かを得るグラフを検索する方法です。しかし、どんなことが必要ですか？

あなたはすべてのエッジ値が1である特定のノードからの距離を取得したい場合は、[OK] BFSはダイクストラの特殊なケースです。あなたが他のアルゴリズムを実行するか、BFSまたはDFSで他のものを取得したい場合は

、そこにダイクストラを行うに注目し、あるいは彼らと非常に似ていません。