Python을 사용하여 Floyd-Warshall 알고리즘을 구현하는 방법은 무엇입니까?-파이썬 튜토리얼-php.cn

Python을 사용하여 Floyd-Warshall 알고리즘을 구현하는 방법은 무엇입니까?

WBOY

풀어 주다： 2023-09-21 10:29:02

원래의

1177명이 탐색했습니다.

Python을 사용하여 Floyd-Warshall 알고리즘을 구현하는 방법은 무엇입니까?

Floyd-Warshall 알고리즘은 모든 소스 지점에서 모든 목적지 지점까지의 최단 경로 문제를 해결하는 데 사용되는 고전적인 알고리즘입니다. 유향 그래프나 음의 가중치 에지 문제를 처리하는 데 사용할 수 있는 동적 계획법 알고리즘입니다. 이 기사에서는 Python을 사용하여 Floyd-Warshall 알고리즘을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.

Floyd-Warshall 알고리즘의 핵심 아이디어는 각 노드를 중간 노드로 사용하여 그래프의 모든 노드를 순회하여 노드 간 최단 경로를 점진적으로 업데이트하는 것입니다. 2차원 행렬을 사용하여 그래프의 노드 사이의 거리를 저장할 수 있습니다.

먼저 Floyd-Warshall 알고리즘을 구현하기 위한 함수를 정의해야 합니다. 다음은 간단한 알고리즘 프레임워크입니다.

def floydWarshall(graph):
    dist = graph
    num_vertices = len(graph)
    
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

로그인 후 복사

이 코드는 세 개의 중첩 루프를 사용하여 그래프의 각 노드를 처리합니다. 각 반복에서 거리 행렬을 업데이트하여 더 짧은 경로를 찾습니다. 구체적으로, 노드 i에서 노드 j까지의 경로가 노드 k를 통해 더 짧은 거리를 달성할 수 있는지 확인할 것입니다. 그렇다면 거리 행렬의 값을 업데이트합니다.

이 기능을 사용하기 전에 그래프를 정의해야 합니다. 다음은 예제 그래프의 정의입니다.

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

로그인 후 복사

이 예제 그래프는 유향 그래프의 인접 행렬 표현입니다. 그 중 float('inf')는 거리가 무한대라는 뜻으로, 두 노드 사이에 직접적인 연결이 없다는 뜻이다. float('inf')表示距离为无穷大，这意味着两个节点之间没有直接连接。

下面，我们调用floydWarshall函数，传入图作为参数，并打印最终的结果：

result = floydWarshall(graph)
for row in result:
    print(row)

로그인 후 복사

完整的代码如下：

def floydWarshall(graph):
    dist = graph
    num_vertices = len(graph)
    
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

result = floydWarshall(graph)
for row in result:
    print(row)

로그인 후 복사

运行上述代码，你会得到以下输出：

[0, -1, -2, 0]
[4, 0, 2, 4]
[5, 1, 0, 2]
[3, -1, 1, 0]

로그인 후 복사

输出的结果是一个二维矩阵，表示图中任意两个节点之间的最短路径。例如，result[0][2]

아래에서는 floydWarshall 함수를 호출하고 그래프를 매개변수로 전달한 후 최종 결과를 인쇄합니다.

rrreee

전체 코드는 다음과 같습니다. 🎜rrreee🎜위 코드를 실행하면 다음과 같은 출력을 얻습니다. 🎜 rrreee🎜의 출력 결과는 그래프의 두 노드 사이의 최단 경로를 나타내는 2차원 행렬입니다. 예를 들어 result[0][2]의 값은 -2입니다. 이는 노드 0에서 노드 2까지의 최단 경로 거리가 -2임을 의미합니다. 두 노드에 도달할 수 없는 경우 거리는 무한대로 표시됩니다. 🎜🎜이 예를 통해 Floyd-Warshall 알고리즘의 구현과 사용을 명확하게 이해할 수 있습니다. 이 글이 이 알고리즘을 이해하고 적용하는 데 도움이 되기를 바랍니다! 🎜

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