ホームページ バックエンド開発 Python チュートリアル Python で Bellman-Ford アルゴリズムを記述するにはどうすればよいですか?

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

Sep 22, 2023 am 08:01 AM
Pythonプログラミング アルゴリズムの実装 ベルマン・フォードアルゴリズム

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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

AssertionError: Python アサーション エラーを解決するにはどうすればよいですか? AssertionError: Python アサーション エラーを解決するにはどうすればよいですか? Jun 25, 2023 pm 11:07 PM

Python のアサーションは、プログラマがコードをデバッグするための便利なツールです。これは、プログラムの内部状態が期待を満たしていることを確認し、これらの条件が false の場合にアサーション エラー (AssertionError) を発生させるために使用されます。開発プロセスでは、コードのステータスが期待される結果と一致するかどうかを確認するために、テストとデバッグ中にアサーションが使用されます。この記事では、原因、解決策、およびコード内でアサーションを正しく使用する方法について説明します。アサーションエラーの原因 アサーションエラーパス

Python での層化サンプリング手法 Python での層化サンプリング手法 Jun 10, 2023 pm 10:40 PM

Python の層化サンプリング手法 サンプリングは、統計学で一般的に使用されるデータ収集方法であり、データ セットから分析用のサンプルの一部を選択して、データ セット全体の特性を推測することができます。ビッグデータの時代では、データの量が膨大になり、分析に完全なサンプルを使用することは時間がかかり、経済的にも現実的ではありません。したがって、適切なサンプリング方法を選択することで、データ分析の効率を向上させることができます。この記事では主にPythonでの層別サンプリング手法を紹介します。層化サンプリングとは何ですか?サンプリングでは、層別サンプリング

Python で脆弱性スキャナーを開発する方法 Python で脆弱性スキャナーを開発する方法 Jul 01, 2023 am 08:10 AM

Python による脆弱性スキャナーの開発方法の概要 インターネット セキュリティの脅威が増大する今日の環境において、脆弱性スキャナーはネットワーク セキュリティを保護するための重要なツールとなっています。 Python は、簡潔で読みやすく強力な人気のあるプログラミング言語であり、さまざまな実用的なツールの開発に適しています。この記事では、Python を使用してネットワークにリアルタイムの保護を提供する脆弱性スキャナーを開発する方法を紹介します。ステップ 1: スキャン対象を決定する 脆弱性スキャナーを開発する前に、スキャンする対象を決定する必要があります。これは、独自のネットワークでも、テスト権限のあるネットワークでもかまいません

Linux でのスクリプト作成と実行に Python を使用する方法 Linux でのスクリプト作成と実行に Python を使用する方法 Oct 05, 2023 am 11:45 AM

Python を使用して Linux でスクリプトを作成および実行する方法 Linux オペレーティング システムでは、Python を使用してさまざまなスクリプトを作成および実行できます。 Python は、スクリプト作成をより簡単かつ効率的にするための豊富なライブラリとツールを提供する、簡潔で強力なプログラミング言語です。以下では、Linux で Python を使用してスクリプトを作成および実行する基本的な手順を紹介し、Python をよりよく理解して使用するのに役立つ具体的なコード例をいくつか示します。 Pythonをインストールする

C# を使用して幅優先検索アルゴリズムを作成する方法 C# を使用して幅優先検索アルゴリズムを作成する方法 Sep 19, 2023 am 11:45 AM

C# を使用して幅優先検索アルゴリズムを作成する方法 幅優先検索 (BFS) は、幅に従ってグラフまたはツリーを走査するために使用される、一般的に使用されるグラフ検索アルゴリズムです。この記事では、C# を使用して幅優先検索アルゴリズムを作成する方法を検討し、具体的なコード例を示します。アルゴリズムの原理 幅優先検索アルゴリズムの基本原理は、アルゴリズムの開始点から開始して、ターゲットが見つかるかグラフ全体が走査されるまで、検索範囲を層ごとに拡大することです。通常、キューを通じて実装されます。

Python での sqrt() 関数の使用法 Python での sqrt() 関数の使用法 Feb 21, 2024 pm 03:09 PM

Python での sqrt() 関数の使用法とコード例 1. sqrt() 関数の関数と紹介 Python プログラミングにおいて、sqrt() 関数は math モジュール内の関数であり、その機能は次の平方根を計算することです。数。平方根は、数値をそれ自体で乗算すると数値の 2 乗に等しいことを意味します。つまり、x*x=n の場合、x は n の平方根になります。プログラム内で sqrt() 関数を使用すると、平方根を計算できます。 2. Python で sqrt() 関数を使用する方法、sq

Python プログラミングの実践: Baidu Map API を使用して静的地図関数を生成する方法 Python プログラミングの実践: Baidu Map API を使用して静的地図関数を生成する方法 Jul 30, 2023 pm 09:05 PM

Python プログラミング演習: Baidu Map API を使用して静的地図関数を生成する方法 はじめに: 現代社会において、地図は人々の生活に欠かせないものとなっています。マップを操作する場合、多くの場合、Web ページ、モバイル アプリ、またはレポートに表示するために、特定のエリアの静的なマップを取得する必要があります。この記事では、Python プログラミング言語と Baidu Map API を使用して静的地図を生成する方法を紹介し、関連するコード例を示します。 1. 準備作業 Baidu Map API を使用して静的地図を生成する機能を実現するために、

Python プログラミングを使用して、Baidu 画像認識インターフェイスのドッキングを実現し、画像認識機能を実現する方法を説明します。 Python プログラミングを使用して、Baidu 画像認識インターフェイスのドッキングを実現し、画像認識機能を実現する方法を説明します。 Aug 25, 2023 pm 03:10 PM

Python プログラミングを使用して、Baidu の画像認識インターフェイスのドッキングを実装し、画像認識機能を実現する方法を説明します。コンピューター ビジョンの分野において、画像認識技術は非常に重要な技術です。 Baidu は、画像の分類、ラベル付け、顔認識、その他の機能を簡単に実装できる強力な画像認識インターフェイスを提供します。この記事では、Python プログラミング言語を使用して、Baidu 画像認識インターフェイスに接続して画像認識機能を実現する方法を説明します。まず、Baidu Developer Platform でアプリケーションを作成し、

See all articles