Python で Bellman-Ford アルゴリズムを記述するにはどうすればよいですか?

Bellman-Ford アルゴリズムを Python で記述するにはどうすればよいですか?

Bellman-Ford アルゴリズムは、負の重み付けエッジを使用した単一ソース最短経路問題を解決するためのアルゴリズムです。この記事では、Python を使用して Bellman-Ford アルゴリズムを作成する方法を紹介し、具体的なコード例を示します。

Bellman-Ford アルゴリズムの中心的な考え方は、最短パスが見つかるまで段階的に反復してパスを最適化することです。アルゴリズムの手順は次のとおりです。

1. 配列 dist[] を作成して、ソース ポイントから他の頂点までの最短距離を保存します。
2. dist[] 配列のすべての要素を無限大に初期化しますが、ソース ポイントからの距離は 0 です。
3. n-1 回の反復を通じて、各エッジ (u, v) に対して:
   1) dist[v] > dist[u]weight(u, v) の場合、dist[v] を更新します。 dist[u] 重み(u, v)。
4. 負の体重サイクルがあるかどうかを確認してください。各エッジ (u, v) について:
   1) dist[v] > dist[u]weight(u, v) の場合、負の重みサイクルがあり、最短パスは決定できません。
5. 負の重みサイクルがない場合、最短パスが計算されており、dist[] 配列が最短パスになります。

以下は、Python で書かれた Bellman-Ford アルゴリズムのコード例です。

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def bellman_ford(self, src):
        dist = [float("Inf")] * self.V
        dist[src] = 0

        for _ in range(self.V - 1):
            for u, v, w in self.graph:
                if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        for u, v, w in self.graph:
            if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                print("图中存在负权环，无法确定最短路径")
                return

        self.print_solution(dist)

    def print_solution(self, dist):
        print("顶点    最短距离")
        for i in range(self.V):
            print(i, "        ", dist[i])

# 示例用法
g = Graph(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, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)
g.bellman_ford(0)

上の例では、グラフ g が作成され、いくつかのエッジが追加されます。次に、bellman_ford メソッドを呼び出して最短パスを計算し、結果を出力します。この例では、ソース ポイントは 0 であり、最短パスが計算されます。

ベルマン・フォード アルゴリズムの時間計算量は O(V*E) です。ここで、V は頂点の数、E はエッジの数です。実際のアプリケーションでは、グラフに負の重みサイクルがある場合、アルゴリズムは停止せずに無限ループに入ります。したがって、Bellman-Ford アルゴリズムを使用する場合は、まず負の重みサイクルがあるかどうかを確認する必要があります。

以上がPython で Bellman-Ford アルゴリズムを記述するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。