Bellman-Fordアルゴリズムの理解と実装

Bellman-Fordアルゴリズムは、重み付きグラフにおいて単一始点から他の全ての頂点への最短経路を求めるためのアルゴリズムです。特に、負の重みを持つ辺が存在する場合でも正しく動作します。Dijkstraアルゴリズムと異なり、負の重みの辺を扱うことができるのが大きな特徴です。

Bellman-Fordアルゴリズムの基本概念

Bellman-Fordアルゴリズムは、以下のステップで動作します。

1. 初期化: 始点の距離を0、その他の頂点の距離を無限大に設定します。
2. 頂点数 - 1 回の反復: グラフの全ての辺を検査し、各辺に対して最短距離を更新します。
3. 負の重みの検出: 追加の反復を行い、距離が更新される場合は負のサイクルが存在することを示します。

Bellman-Fordアルゴリズムの実装

では、PythonでBellman-Fordアルゴリズムを実装してみましょう。

class Edge:
    def __init__(self, u, v, weight):
        self.u = u  # 始点
        self.v = v  # 終点
        self.weight = weight  # 辺の重み

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 頂点数
        self.edges = []  # 辺のリスト

    def add_edge(self, u, v, weight):
        self.edges.append(Edge(u, v, weight))

    def bellman_ford(self, start):
        # 初期化
        distance = [float("inf")] * self.V
        distance[start] = 0

        # 頂点数 - 1 回の反復
        for _ in range(self.V - 1):
            for edge in self.edges:
                if distance[edge.u] != float("inf") and distance[edge.u] + edge.weight < distance[edge.v]:
                    distance[edge.v] = distance[edge.u] + edge.weight

        # 負の重みの検出
        for edge in self.edges:
            if distance[edge.u] != float("inf") and distance[edge.u] + edge.weight < distance[edge.v]:
                print("負のサイクルが存在します。")
                return None

        return distance

# グラフの作成とテスト
if __name__ == "__main__":
    g = Graph(5)  # 頂点数は5
    g.add_edge(0, 1, -1)
    g.add_edge(0, 2, 4)
    g.add_edge(1, 2, 3)
    g.add_edge(1, 3, 2)
    g.add_edge(1, 4, 2)
    g.add_edge(3, 1, 1)
    g.add_edge(3, 4, -3)
    g.add_edge(4, 0, 5)

    start_vertex = 0
    distances = g.bellman_ford(start_vertex)
    if distances:
        print("頂点からの最短距離:")
        for i in range(len(distances)):
            print(f"頂点 {i}: {distances[i]}")

コードの解説

1. Edgeクラス: 辺を表現するクラスで、始点u、終点v、重みweightを持ちます。
2. Graphクラス: グラフを表現し、頂点数と辺のリストを保持します。add_edgeメソッドで辺を追加します。
3. bellman_fordメソッド: Bellman-Fordアルゴリズムを実行します。
4. 初期化: 始点の距離を0、他の頂点の距離を無限大に設定します。
5. 反復処理: 各辺を通じて最短距離を更新します。
6. 負のサイクルの検出: 追加の反復を行い、距離が更新される場合には負のサイクルが存在することを示します。
7. メインセクション: グラフを作成し、辺を追加してBellman-Fordアルゴリズムを実行します。最短距離を出力します。

このアルゴリズムは、特に負の重みを持つ場合に強力なツールです。実際のアプリケーションでは、ネットワークの最適化や経路問題に利用されることが多いです。