Pythonで解く「赤と青の辺が交互になる最短経路」問題 ― BFSによる実装方法

問題の概要

ノードに 0 から n-1 までのラベルが付いた有向グラフを考えます。このグラフでは、各辺は赤または青のいずれかで塗られており、自己ループや平行辺（同じ向きの複数の辺）が存在することもあります。red_edges 内の各 [i, j] はノード i からノード j への赤い有向辺を、blue_edges 内の各 [i, j] は青い有向辺を表します。

求めたいのは長さ n の配列 answer です。各 answer[X] には、ノード 0 からノード X までの最短経路のうち、通る辺の色が交互に入れ替わるものの長さを格納します。そのような経路が存在しない場合は -1 を返します。

たとえば、入力が n = 3、red_edges = [[0,1],[1,2]]、blue_edges = [] の場合、出力は [0, 1, -1] となります。ノード 0 からノード 1 へは赤い辺で 1 ステップで到達できますが、ノード 2 までは色が交互になる経路が存在しないためです。

解法のアプローチ：BFS（幅優先探索）

この問題は幅優先探索（BFS）で効率よく解けます。重要なポイントは、訪問済みの管理を「ノード」と「次に使う辺の色」のペアで行うことです。同じノードでも、到達したときの直前の辺の色が異なれば別々の状態として扱う必要があるためです。

bfs() メソッドの手順

• bfs() メソッドを定義します。引数は re（赤い辺の隣接リスト）、be（青い辺の隣接リスト）、f（開始時の色）、n です。
• 訪問済みを記録する集合 visited を定義し、キューに三つ組 [0, f, 0]（ノード、色、ステップ数）を挿入します。
• キューが空でない間、以下を繰り返します。
  • キューの先頭から current、color、step を取り出します。
  • color を反転させます（True ⇔ False）。これにより「次に使うべき辺の色」が決まります。
  • res[current] を現在の値と step の最小値で更新します。
  • color が真（赤）の場合：re[current] の各ノード i について、ペア (i, color) が未訪問なら visited に追加し、[i, color, step + 1] をキューに挿入します。
  • color が偽（青）の場合：be[current] に対して同様の処理を行います。

メイン処理の手順

• res := サイズ n の無限大（inf）で初期化された配列を用意します。
• re と be := n 個の空リストを持つ配列を作成します。
• r の各要素 i について、re[i[0]] に i[1] を追加します。
• b の各要素 i について、be[i[0]] に i[1] を追加します。
• bfs(re, be, False, n) と bfs(re, be, True, n) を呼び出します。最初の辺が赤の場合と青の場合の両方を試すことで、すべての交互パターンを網羅できます。
• 最後に、res[i] が無限大のまま残っている場合は -1 に置き換えて返します。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

class Solution(object):
    def shortestAlternatingPaths(self, n, r, b):
        self.res = [float("inf")] * n
        re = [[] for i in range(n)]
        be = [[] for i in range(n)]
        for i in r:
            re[i[0]].append(i[1])
        for i in b:
            be[i[0]].append(i[1])
        self.bfs(re, be, False, n)
        self.bfs(re, be, True, n)
        for i in range(len(self.res)):
            if self.res[i] == float('inf'):
                self.res[i] = -1
        return self.res

    def bfs(self, re, be, f, n):
        visited = set()
        queue = [[0, f, 0]]
        while queue:
            current, color, step = queue[0]
            queue.pop(0)
            color = not color
            self.res[current] = min(self.res[current], step)
            if color:
                for i in re[current]:
                    if (i, color) not in visited:
                        visited.add((i, color))
                        queue.append([i, color, step + 1])
            elif not color:
                for i in be[current]:
                    if (i, color) not in visited:
                        visited.add((i, color))
                        queue.append([i, color, step + 1])

ob = Solution()
print(ob.shortestAlternatingPaths(3, [[0,1], [1,2]], []))

入力

3
[[0,1],[1,2]]
[]

出力

[0,1,-1]

まとめ

この問題の鍵となるのは、通常の BFS とは異なり、(ノード, 辺の色) のペアを状態として管理する点です。さらに、最初の辺の色が赤のケースと青のケースの両方について BFS を実行することで、あらゆる交互パターンの経路を漏れなく探索できます。計算量は O(n + E)（E は辺の総数）程度に抑えられ、効率的に最短距離を求められます。