Pythonで都市間のショートカット最短距離を求めるプログラムの実装方法

n個の都市があり、それぞれの都市は「高速道路」と「近道（ショートカット）」という2種類の道路で結ばれているとします。手元の地図には高速道路だけが記載されていて、近道は一切載っていません。都市の運輸部門では、高速道路と近道を活用して各都市を結ぶ交通手段を新設しようと考えています。ここで重要なルールは、「2つの都市の間に高速道路が存在しない場合、その間には必ず近道が存在する」ということです。今回の課題は、出発都市から他のすべての都市までの、近道の利用回数で表した最小距離を求めることです。

たとえば、入力が次のようなケースを考えてみましょう。

開始頂点 s を 1 とした場合、出力は「3 1 2」になります。これは、出発都市（都市1）を除く各都市（都市2、都市3、都市4）への距離を順番に並べたものです。

近道だけを辿ると、都市1と都市2の間の経路は 1→3→4→2 となり、コストは3です。同様に、

• 都市1と都市3：1→3、コスト1
• 都市1と都市4：1→3→4、コスト2

解法のステップ

この問題は、高速道路ネットワークの「補グラフ」（＝近道だけで構成されるグラフ）上で幅優先探索（BFS）を行うことで解けます。ただし、補グラフを実際に構築すると最大 O(n²) のメモリが必要になるため、ここでは補グラフを明示的に作らずにBFSを実現するテクニックを使います。具体的な手順は以下の通りです。

• graph := n個の空集合からなる新しいリストを作成する
• edges 内の各ペア (x, y) について、以下を実行する
  • x := x − 1
  • y := y − 1
  • y を graph[x] に追加する
  • x を graph[y] に追加する
• temp_arr := サイズ n・初期値 −1 の新しい配列を作成する
• b_set := {s − 1} からなる新しい集合を作成する
• f := 0 以上 n 未満の整数全体から b_set を引いた差集合を作成する
• index := 0 とする
• b_set のサイズが 0 より大きい間、以下を繰り返す
  • b_set 内の各要素 a に対して、temp_arr[a] := index を代入する
  • nxt := 「b_set が graph[f] の部分集合ではない」ような頂点 f の集合（つまり、現在の層の少なくとも1つの頂点と高速道路でつながっていない＝近道で到達できる頂点）
  • f := f と nxt の差集合を計算する
  • b_set := nxt とする
  • index := index + 1
• temp_arr のうち 0 より大きい値を返す

ポイントは条件式「b_set が graph[f] の部分集合でない」の部分です。ある頂点 f が現在の探索層 b_set のすべての頂点と高速道路で結ばれているなら、f へは近道では直接届きません。逆に、1つでも高速道路のない頂点が b_set に含まれていれば、その頂点との間に近道が存在するため、f は次の層に進むことができます。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def solve(n, edges, s):
    graph = [set() for i in range(n)]
    for (x, y) in edges:
        x -= 1
        y -= 1
        graph[x].add(y)
        graph[y].add(x)
    temp_arr = [-1] * n
    b_set = {s - 1}
    f = set(range(n)).difference(b_set)
    index = 0
    while len(b_set) > 0:
        for a in b_set:
            temp_arr[a] = index
        nxt = {f for f in f if not b_set.issubset(graph[f])}
        f = f.difference(nxt)
        b_set = nxt
        index += 1
    return (' '.join(str(t) for t in temp_arr if t > 0))

print(solve(4, [(1, 2), (2, 3), (1, 4)], 1))

入力

4, [(1, 2), (2, 3), (1, 4)], 1

出力

3 1 2

このように、補グラフを明示的に作成することなく、高速道路の情報だけから各都市へのショートカット最短距離を効率よく求めることができます。