플로이드 워샬 알고리즘 - python

<문제>

N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최솟값을 구하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에는 도시의 수 N(N <=100)과 도로수 M(M <=200)가 주어지고, M 줄에 걸쳐 도로정보 와 비용(20 이하의 자연수)이 주어진다. 만약 1번 도시와 2번 도시가 연결되고 그 비용이 13이 면 “1 2 13”으로 주어진다.

▣ 출력설명
모든 도시에서 모든 도시로 이동하는데 드는 최소 비용을 아래와 같이 출력한다.
자기 자신으로 가는 비용은 0입니다. i번 정점에서 j번 정점으로 갈 수 없을 때는 비용을 “M"으 로 출력합니다.

 

▣ 입력예제 1

5 8

1 2 6

1 3 3

3 2 2

2 4 1

2 5 13

3 4 5

4 2 3

4 5 7

 

▣ 출력예제 1
0 5 3 6 13 //1번 정점에서 2번 정점으로 5, 1에서 3번 정점으로 3, 1에서 4번 정점으로 6......

M 0 M 1 8 //2번 정점에서 1번 정점으로는 갈 수 없으므로 “M",.......
M 2 0 3 10
M 3 M 0 7
M M M M 0

 

<풀이>

개인적으로 되게 어려웠다

일단 DP테이블을 이차원 리스트로 만든다. 10000( 엄청 큰 값)으로  초기화를 해서 만든다. 그 후에 (1,1), (2,2) 등등 i와 j의 값이 같은 값들을 0으로 만들고 입력값들을 입력받은후에 DP테이블에 저장한다. 

그 후 3중 for문을 사용한다 K가 1일 때 DP테이블을 돌면서 i에서 j로 갈 때 k를 들리는 것과 바로 가는 것 중에 비교를 한다. 그렇게 K를 n까지 비교를 한다. 이렇게 하면 빠른 걸로 값들이 바뀌어서 결국 최단시간 내로 갈 수 있는 값들만 저장이 된다.

n , m = map(int,input().split())
DP = [[10000] * (n+1) for _ in range(n+1)]
for i in range(n+1):
    DP[i][i] = 0
for _ in range(m):
    i , j , d = map(int,input().split())
    DP[i][j] = d 
       
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j])

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