Bellman-Ford 알고리즘을 Python으로 작성하는 방법은 무엇입니까?

Python에서 Bellman-Ford 알고리즘을 작성하는 방법은 무엇입니까?

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이고 최단 경로가 계산됩니다.

Bellman-Ford 알고리즘의 시간 복잡도는 O(V*E)입니다. 여기서 V는 정점 수이고 E는 가장자리 수입니다. 실제 적용에서 그래프에 음의 가중치 주기가 있으면 알고리즘은 멈추지 않고 무한 루프에 들어갑니다. 따라서 Bellman-Ford 알고리즘을 사용하는 경우 음의 가중치 주기가 있는지 먼저 확인해야 합니다.

위 내용은 Bellman-Ford 알고리즘을 Python으로 작성하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!