플로이드 워샬 알고리즘

생성일: 2022년 2월 27일 오후 4:25

구현 코드 ⭐

# 플로이드 워샬 알고리즘
import sys
sys.stdin = open("input.txt", "rt")

if __name__ == "__main__":
    n, m = map(int, input().split())
    dis = [[5000 for _ in range(n+1)] for _ in range(n+1)]
    
    # 출발지와 목적지가 같은 경우는 0으로 초기화
    for i in range(1, n+1):
        dis[i][i] = 0

    for i in range(m):
        a, b, c = map(int, input().split())
        dis[a][b] = c
    
    # 플로이드 워샬 알고리즘
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])

    for i in range(1, n+1):
        for j in range(1, n+1):
            if dis[i][j] == 5000:
                print('M', end=' ')
            else:
                print(dis[i][j], end=' ')
        print()

• 플로이드 워샬 알고리즘은 3중 for문을 통해 해결한다.

    # 플로이드 워샬 알고리즘
      for k in range(1, n+1):
          for i in range(1, n+1):
              for j in range(1, n+1):
                  dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])

  여기서 i는 출발위치, j는 도착 위치이다. k는 거쳐가는 위치이다. 따라서 dis[i][k]+dis[k][j] 는 i⇒k⇒j 에 해당되는 경로에서의 비용 합이다.