[최단경로] 플로이드워셜 python

https://youtu.be/9574GHxCbKc

 

 

✅ 플로이드 워셜

 

모든 정점에서 모든정점으로 가는 최단경로를 구하고 싶을 때 사용하는 알고리즘

 

0. 거리를 저장하기 위한 2차원 배열을 만든다. dist[i][k]는 노드i에서 k를 가기위한 비용이다. 

1. 어떤 노드에서 다른 노드로 갈수있는 edge(간선)가 존재하면, 최소비용을 할당, 갈수 없다면 INF를 할당한다.

2. 3중 for문을 사용, 중간 정점을 거쳐서 비용이 줄어드는 경우가 있다면, 최소비용을 업데이트한다. 

 

 

⏺ 핵심 코드

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

 

 

---

 

💻 CODE

import sys

INF = sys.maxsize

def floydWarshall():
    # dist : n*n 리스트를 만든다. INF로 채워준다. (최단경로 배열)
    dist = [[INF]*n for _ in range(n)]

    # 연결 선에 대한 정보를 dist이차원리스트에 할당한다.
    for i in range(n):
        for j in range(n):
            dist[i][j] = info[i][j]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j] 

    return dist



n = 4
info = [
    [0,2,INF,4], #1
    [2,0,INF,5], #2
    [3,INF,0,INF], #3
    [INF,2,1,0]  #4
]

result = floydWarshall()

for i in range(n):
    for j in range(n):
        print(result[i][j], end=' ')
    print()