ダイクストラ アルゴリズムに関するほとんどの記事は、ノードの「緩和」を実行するためにどのデータ構造を使用する必要があるかにのみ焦点を当てています。
O(m log(n))私は信じている上で実行される最小ヒープを使用するつもりです。
私の本当の質問は、各ノードの隣接ノードを格納するためにどのデータ構造を使用すればよいですか? uですべての隣接ノードを見つけることができるため、隣接リストの使用を考えていO(deg(u))ます。これが最速の方法ですか?
アルゴリズムの実行時間はどのように変化しますか?
For the algorithm itself, I think you should aim for compact representation of the graph. If it has a lot of links per node, a matrix may be best, but usually an adjacency list will take less space, and therefore less cache misses.
It may be worth looking at how you are building the graph, and any other operations you do on it.
ダイクストラのアルゴリズムでは、ノードの近隣のリストを 1 回ループするだけなので、各ノード (隣接リストのように) に隣接するノード (または単にグローバル リスト内のそれらのインデックス) を格納する単純な配列またはリンク リストで十分です。 .
How will that change the running time of the algorithm?――何と比べて？アルゴリズムの複雑さは、隣接リストの実装を想定していると確信しています。実行時間はO(edges + vertices * log(vertices))です。