Time and Space Complexity

時間計算量:

• ここに記載されている通り O(V² + V*E) です（V回の各ラウンドで、最小値を見つけるために頂点をスキャンし、緩和のためにエッジをスキャンします）。バイナリヒープと隣接リストを使用すると、O((V + E) log V) に改善されます。

空間計算量:

• 距離配列および訪問済み配列のための O(V)（および入力エッジ）。

まとめ:

• ダイクストラ法は、最も近い頂点を貪欲に確定させ、そのエッジを緩和することで、非負の重みに対する単一始点最短距離を求めます。
• 負のエッジには対応していません。その場合はベルマン・フォード法（Bellman-Ford）を使用してください。