1. 序章

このチュートリアルでは、ダイクストラのアルゴリズムでエッジを緩和するメカニズムについて説明します。 エッジを緩和することは、グラフ理論の分野におけるさまざまな最短経路アルゴリズムにとって重要な手法です。

2. 最短経路を見つける

最短経路を見つける最もよく知られているアプリケーションはナビゲーションです。ここでは、地図上の2つの位置の間の最短経路を見つけることが重要です。

この図では、非常に単純な最短経路問題が見られます。「東京、北京、ニューヨーク」が東京とニューヨークの間の最短経路です。

最短経路を見つけるのは非常にコストがかかる可能性があります。 ナビゲーションシステムで2つの都市間の最短経路を見つけ、出発地と目的地の間にさまざまな都市や通りがあると想像してみてください。 ダイクストラのアルゴリズムは、必要なリソースが非常に少ないため、最短経路を見つけるための非常に有名な方法です。 負のエッジ評価を持たないすべての有向グラフで機能します。

3. エッジをリラックスしてパスを改善する

ダイクストラ法とベルマンフォード法アルゴリズムは、エッジ緩和と呼ばれる手法を使用します。 これは、グラフをトラバースして最短パスを見つける際に、到達するためのより短いパスが見つかるとすぐに、既知のノードのパスを更新することを意味します。 これは写真で最もよく示されています：

この図では、から開始し、ターゲットはです。 ダイクストラのアルゴリズムに従うので、最初にからに進みます。 から、に移動するためのコストは合計で16になることがわかります。 しかし、ダイクストラは常にまだ通過していない最短のエッジをたどるので、最初にからへのパスを取ります。 から、へのパスのコストは11であることがわかります。これにより、パス、、は、、、よりも安価になります。 これにより、へのパスを更新し、より低いコスト11で割り当てることができます。 グラフ内のパスを更新するこのプロセスは、エッジの緩和と呼ばれます。

4. 複雑

グラフ内のすべての可能なパスを試すことは、超多項式の問題です。 これが、最短経路を見つけるための効率的なアルゴリズムが私たちに多くの時間を節約できる理由です。 ダイクストラのアルゴリズムは、エッジを緩和する方法も使用するベルマンフォードのアルゴリズムと比較して、リストを使用して実装する場合の時間計算量があります。 最短経路を見つける別の代替方法は、グラフ内のすべてのペアのすべての最短経路を見つけることです。

緩和エッジを使用しないアルゴリズムの例は、フロイドアルゴリズムです。 これは、利用可能な頂点のすべてのペア間の最短経路を計算することによって機能し、複雑であり、負のエッジを持つグラフの最短経路を計算するという利点もあります。 フロイドのアルゴリズムは、エッジ緩和を使用しない最速の最短経路アルゴリズムの1つであるため、この手法によってパフォーマンスが大幅に向上すると結論付けることができます。

5. リラクゼーションの順序

最後の段落で、ダイクストラの複雑さはベルマンフォードの複雑さとは異なることがわかりました。 グラフをトラバースしている間、両方ともエッジを緩和するため、これは少し驚くかもしれません。 したがって、エッジを緩和するだけでなく、それを実行する順序も重要です。 これをよりよく理解するために、次の例を見てみましょう。

まず、パスをたどり、、、、、途中ですべてのエッジをリラックスします。

次に、右上のエッジを緩和して、次のパスへの短いパスを取得できることに気付きます。

右上のエッジを緩和した後、左上のエッジを緩和して、次のパスへの短いパスを取得することもできます。

最後に、グラフの最短経路を取得するために、右上のエッジを再度緩和する必要があります。

ご覧のとおり、最初に左上端を緩和し、次に右上端を緩和すると、1回の緩和のコストが節約されるため、緩和の順序は非常に重要です。 これは一見あまり見えませんが、実際にはそのようなタイプのエッジのコストがかかります。

7. 結論

この記事では、緩和エッジの概念と、さまざまな最短経路アルゴリズムにおけるそれらの重要性について説明しました。 さらに、最短経路を計算するときに、緩和の順序が異なるとコスト差が生じる可能性があることを分析しました。