1. 概要

このチュートリアルでは、グラフ内の2つのノード間の最短経路の数をカウントする問題について説明します。 まず、問題を定義し、それを説明する例を示します。

次に、この問題に対する2つのアプローチについて説明します。 最初のアプローチは重み付けされていないグラフ用であり、もう1つのアプローチは重み付けされたグラフ用です。

2. 問題の定義

からまでの番号が付けられたノードのグラフがあるとします。 さらに、これらのノードを接続するエッジがあります。 ソースノードのインデックスと宛先ノードをそれぞれ表す2つの番号が与えられています。

私たちのタスクは、送信元ノードから宛先までの最短パスの数を数えることです。

2つのノード間の最短パスであり、との間のすべての可能なパスの中で最小の長さを持つパスであることを思い出してください。

理解を深めるために例を確認してみましょう。 次のグラフがあり、次のように与えられたとします。

ノードからノードに移動するには、次のパスがあります。

  1. 、長さが。に等しい。
  2. 、長さが。に等しい。
  3. 、長さが。に等しい。
  4. 、長さが。に等しい。

ご覧のとおり、最短経路の長さは。です。 また、長さがに等しい2つのパスがあることに気付きます。 したがって、ノードとノードの間に最短パスがあります。

3. 重み付けされていないグラフ

3.1. 本旨

ここでの主なアイデアは、BFS（幅優先探索）を使用して、グラフ内の他のすべてのノードへのソースノードの最短パスを取得することです。 ノードごとに2つの値を保存します。

  • ：は、ソースから現在のパスまでの最短パスの長さを表します。
  • ：これらの最短経路の数を表します。

最初は、ソースノードが（ノードからそれ自体への最短パスの長さは常に）に等しいことを除いて、すべてのノードの値は無限大です。 また、すべてのノードの値は、（ノードはそれ自体への単一の最短パスを持っています）に等しいソースノードを除きます。

次に、BFSアルゴリズムを使用してグラフのトラバースを開始します。 現在のノードの子をキューに追加するたびに、2つの選択肢があります。

  • の場合、これは、ソースノードから子ノードに向かうパスが前のパスよりも短いことを意味します。 したがって、子ノードの距離値を最小化して、現在のノードの距離に1を加えた値に等しくします。 さらに、子ノードの値は、現在のノードの値と等しくなるように更新されます。
  • の場合、 は、ソースノードから現在のノードに向かうすべての最短パスが子ノードの最短パスの数に追加されることを意味します。理由は、に接続するエッジを追加した後の子ノードの最短パスと同じ長さを持ちます。 したがって、子ノードの距離値を同じに保ちます。 ただし、子ノードの値を現在のノードの値だけ増やします。

最後に、ノードの値には、送信元ノードから宛先ノードに到達する最短パスの数が含まれます。 また、ノードの距離値には、からに向かう最短パスの長さが含まれます。

3.2. 実装

実装を見てみましょう：

最初に、2つの配列を宣言します。

  • ：ここで、はソースノードからノードまでの最短パスの長さを表します。
  • ：ここで、はソースノードからノードへの最短パスの数を表します。

また、BFSトラバーサル中にノードを格納するための空のキューを宣言しました。

次に、キューが空でない限り、複数のステップを実行します。 各ステップで、キューの先頭に配置されたノードを取得し、その子を反復処理します。 子ごとに、そのノードに以前にアクセスしたことがないかどうかを確認します。 その場合は、それをキューに追加し、訪問済みノードとしてマークします。 また、セクション3.1で説明したルールに基づいて、ノードのとの値を更新します。

最後に、送信元ノードから宛先に到達する最短パスの数を格納するを返します。

このアプローチの複雑さは、BFSの複雑さと同じです。です。ここで、はノードの数、はエッジの数です。 この複雑さの背後にある理由は、各ノードを1回だけ反復するためです。 したがって、子を1回繰り返します。 合計で、各エッジも1回繰り返します。

4. 加重グラフ

4.1. 本旨

BFSアプローチの同じの概念を適用して、重み付きグラフの同じ問題を解決します。 ただし、加重グラフで最短パスを取得するには、キューの先頭に配置されているノードが、現在キューに残っている他のすべてのノードの中で最小の距離値を持つことを保証する必要があります。 したがって、ダイクストラのアルゴリズムを使用します。

Dijkstraのアルゴリズムでは、値のペアを格納する優先キューを宣言します。

  • ：ソースノードから現在のノードまでのパスの長さを表します。
  • ：現在のノード自体を表します。

キューの優先度を設定して、ソースノードから現在のノードへの最短パスを取得するための最小のパスを提供します。

最後に、残りのワークフローはBFSアプローチと同じです。

4.2. 実装

実装を見てみましょう：

最初に、前のアプローチと同じ2つの配列を宣言します。

  • ：ここで、はソースノードからノードまでの最短パスの長さを表します。
  • ：ここで、はソースノードからノードへの最短パスの数を表します。

また、探索されたノードを格納するための空の優先キューを宣言し、距離の値に従ってアクセス順に並べ替えます。

次に、重み付けされていないグラフの手順と同様の手順を実行します。 優先キューが空でない限り、優先キューの前に配置されたノードをその（ソースノードから現在のノードまでのパスの長さ）でポップします。

その後、現在のノードの子を繰り返し処理します。 子ごとに、現在のノードの距離値に現在の子エッジのコストを加えた値よりも大きい距離値があるかどうかを確認します。 その場合、この子を優先キューに追加します。 また、子ノードの値と値を更新します。

重み付きグラフの場合、次の手順を少し調整します。

  • の場合、子ノードの距離値を最小化して、現在のノードの距離に現在の子のエッジのコストを加えたものに等しくなります。さらに、子ノードの値が更新されて等しくなります。現在のノードの値に。
  • の場合、子ノードの距離値を同じに保ちます。また、子ノードの値を現在のノードの値だけ増やします。

最後に、送信元ノードから宛先ノードに移動する最短パスの数を格納するパスを返します。

ここでの複雑さはダイクストラの複雑さと同じです。です。ここで、はノードの数、はエッジの数です。 その理由は、BFSアプローチに似ています。 各エッジを1回繰り返し、優先キューは各ノードを追加するために複雑さを必要とするため、優先キュー内のすべてのノードを長さの値でソートしたままにする時間計算量になります。

5. 結論

このチュートリアルでは、グラフ内の2つのノード間の最短経路の数を数える問題を示しました。 一般的な考え方を説明し、加重グラフと非加重グラフの2つのアプローチについて説明しました。