플로이드 -와샬 알고리즘

1. 다익스트라 알고리즘
   -한 노드에서 다른 특정 노드까지의 최단 경로를 구할 때 사용
   -우선 순위 큐 활용해서 구현
   -그리디 알고리즘

2. 플로이드-와샬 알고리즘
   -모든 노드-다른 모든 노드까지의 최단 경로 구할때 사용
   -다이나믹 프로그래밍

플로이드-와샬 알고리즘 과정

1. 2차원 인접 행렬 구성
   -모든 노드간의 최단 거리를 구해야 하므로
2. 라운드 마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고
3. 더 짧은 길이를 선택하여 줄이는 과정을 반복

플로이드-와샬 알고리즘 개념

-결과는 항상 2차원 배열 (모든 노드-모든 노드로 가는 최단 경로가 모두 포함된 테이블 형성)

-초기 이차원 배열을 선언할 때, 직접적으로 연결이 되어 있지 않으면 무한대로 선언하고,
자기 자신은 0으로 초기화
(자기 자신을 0으로 같이 초기화 하는 방법도 있다)

-a->b->C에서 끼어 있는 노드를 기준으로 최단 거리를 구하는것

0번 노드 부터 순차적으로 탐색
자신을 제와한 노드를 탐색하는 경우 :
1,2/ 1,3 /2,1/ 2,3/ 3,1/ 3,2
총 6가지의 경우의 수

6가지의 경우의 수에대해 1>2 경로와 1>0>2 중 더 작은것이 어느 경로인지 판단
-1>2 : 무한
-1>0>2 : 5+4 =9
작은값으로 테이블 업데이트

import sys

def floyd_warshall(n, data):
    dist = [[sys.maxsize] * n for _ in range(n)]

    for i, j, edge in data:
        dist[i - 1][j - 1] = edge

    for k in range(n):
        dist[k][k] = 0
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

n = 4
data = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]

result = floyd_warshall(n, data)
# [[0, -1, -2, 0], [4, 0, 2, 4], [5, 1, 0, 2], [3, -1, 1, 0]]

• 참고 자료 : https://brownbears.tistory.com/560