G - Longest Path の解説（その1）

何の話かと言うと

この問題をネタにして、最短／最長経路に関する考え方を説明してみます。

経路問題の基本的な考え方

実際にはいくつかの考え方があって、問題にあわせてうまく選ばないといけないのですが、まずは、汎用性の高い考え方をおさえましょう。

通常、経路問題では、隣り合ったノード間のリンクの情報だけが与えられます。つまり、他のノードを経由せずに、ダイレクトに移動できる経路についての情報だけが与えられているのです。

ただ、これは逆に言うと、次の様な条件付きの問題は簡単に解けるということです。

[例題1]
N ノード、M リンクの有向グラフ G があり、G は有向閉路を含みません。各リンク i には重み $w_i$ が与えられています。
他のノードを経由せずに、1ホップでの移動だけが許可されているとして、ノード x とノード z のすべてのペアに対して、x から z への移動に伴う重みの最大値を求めよ。（ノード間を移動する経路がない場合は、0 を答える）

はい。何も計算する必要はありません。最初に与えられたリンクの重みを2次元リスト dp[x][y] に書き込めば終わりです。dp[x][y] は x から y に至る経路の重みの最大値を表します。

  # N ノード数、M リンク数
  dp = [[0]*(N+1) for _ in range(N+1)]
  for _ in range(M):
    x, y, w = # 始点 x、終点 y、重み w を読み込み
    dp[x][y] = w

これではあまりにもつまらないので、条件をちょびっとだけ緩めてみます。

[例題2]
[例題1] において、ノード1を経由する経路を許可した場合の結果を求めよ。

これは、[例題1]の結果に修正を加えればOKです。影響を受けるのは、次の様にノード1で接続されたノードyとノードzに対する dp[y][z] です。

y --------> z
 \         ^
  \       /
   \    /
    v /
     1

既存の dp[y][z] と w(y->1) + w(1->z) を比べて、後者の方が大きければ、dp[y][z] の値をこれに修正します。この処理を実装するには、ノード1からリンクされたノード（この例では z）とノード1にリンクしたノード（この例では y）を検索する必要がありますが、これは、既存の dp[ ][ ] を見ればOKです。

・dp[y][1] が 0 でない y
・dp[1][z] が 0 でない z

をそれぞれ検索すればよいのです。

  # N ノード数、M リンク数
  dp = [[0]*(N+1) for _ in range(N+1)]
  for _ in range(M):
    x, y, w = # 始点 x、終点 y、重み w を読み込み
    dp[x][y] = w

  for y in range(1, N+1):
    if dp[y][1] == 0:
      continue
    for z in range(1, N+1):
      if dp[1][z] == 0:
        continue
      if y == z:
        continue
      dp[y][z] = max(dp[y][z], dp[y][1] + dp[1][z])

簡単ですね。（dp[ ][ ] の検索で無駄なループが回るのが気になるかも知れませんが、このあたりは（本当に必要であれば）後から最適化すればOKです。ここでは、気にしないでください。）

ここからさらに、ノード2も経由してよいことにすればどうなるでしょうか？同じことをノード2についても続けてやればOKです。

  for y in range(1, N+1):
    if dp[y][2] == 0:
      continue
    for z in range(1, N+1):
      if dp[2][z] == 0:
        continue
      if y == z:
        continue
      dp[y][z] = max(dp[y][z], dp[y][2] + dp[2][z])

んんんん？？？？　本当にOKでしょうか。次のようなパターンが気になる方もいるやも知れません。。。。

y -------------> z
 \              ^
  \            /
   \         /
    v      /
     1 --> 2

y と z は、y->1->2->z と、1と2の両方を経由して繋がりますが、上記のコードでは、1だけを経由するパターン、2だけを経由するパターンしか処理していないような気もします。

でも大丈夫！

1 の修正を加えた後の dp[ ][ ] の中身を考えてください。1 の修正を加えると dp[y][2] に 0 でない値が入っていますので、この時点で、y と 2 は該当する重みを持った直接のリンクがあることになっているのです。2 の修正を加える際は、dp[y][2] が 0 でない y を検索していますので、結果的にうまくいくのです。

というわけで、この後は、さらに3の経由を許可して、4の経由を許可して・・・と繰り返すと、結局は、すべてのノードを経由を許可した場合の結果が dp[ ][ ] に記録されることになります。一般的な DP の枠組みとはちょっとずれている感がありますが、とりあえずは冒頭の問題の答えが得られます。すべてのリンクの重みを1にして上記の手法を適用したのちに、dp[ ][ ] に残った値の最大値を答えればよいわけです。

  dp = [[0]*(N+1) for _ in range(N+1)]

  for _ in range(M):
    x, y = # 始点 x、終点 y を読み込み
    dp[x][y] = 1

  for x in range(1, N+1):
    for y in range(1, N+1):
      if dp[y][x] == 0:
        continue
      for z in range(1, N+1):
        if dp[x][z] == 0:
          continue
        if y == z:
          continue
        dp[y][z] = max(dp[y][z], dp[y][x] + dp[x][z])

  print(max(list(map(lambda x: max(x), dp))))

なお、x とつながるリンクを検索する時間を短縮したければ、次の様に、リンク情報を別のデータ構造に収めておく方法もあります。

  dp = [[0]*(N+1) for _ in range(N+1)]
  L_from = [[] for _ in range(N+1)] # L_from[x] : x からのリンクをまとめたリスト
  L_to = [[] for _ in range(N+1)] # L_to[x] : x へのリンクをまとめたリスト

  for _ in range(M):
    x, y = # 始点 x、終点 y を読み込み
    L_from[x].append(y)
    L_to[y].append(x)
    dp[x][y] = 1

  for x in range(1, N+1):
    for y in L_to[x]:
      for z in L_from[x]:
        if y == z:
          continue
        dp[y][z] = max(dp[y][z], dp[y][x] + dp[x][z])
        if y not in L_to[z]:
          L_to[z].append(y) # リンク情報の更新に注意
          L_from[y].append(z) # リンク情報の更新に注意

  print(max(list(map(lambda x: max(x), dp))))