파이썬 알고리즘 080 | 플로이드 워샬 알고리즘

80. 플로이드 워샬 알고리즘

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

<내 풀이>

최단거리를 구하는 플로이드 워샬 알고리즘을 배움
최단거리를 구할 때 쓰이는 것, 3중 for문 도는 것 중요

<풀이>

if __name__=='__main__' :
    n,m=map(int,input().split())
    dis=[[5000]*(n+1) for _ in range(n+1)]
    for i in range(1,n+1) :
        dis[i][i]=0 #자기 자신에서 자기 자신한테로 가는 애들은 0이라고 표시
    for i in range(m) :
        a,b,c= map(int,input().split())
        dis[a][b]=c #i에서 j로 직행하는 것
    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->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()

<반성점>

<배운 점>

• 모든 정점에서 정점으로 가는 최단거리, 최단비용
  =>다이나믹 테이블은 2차원 리스트
  dis[i][j] => [i]에서 [j]로 가는 최단경로
  dis의 최초 초기화는 인접 행렬을 초기화 해놓는 것
• 직행하는데 (중간 노드 안 거치고) 드는 비용
• 그리고 직행해서 가는 게 아니고 어떤 노드를 거쳐서 가는 경우도 존재할 것이다