파이썬 알고리즘 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의 최초 초기화는 인접 행렬을 초기화 해놓는 것 - 직행하는데 (중간 노드 안 거치고) 드는 비용
- 그리고 직행해서 가는 게 아니고 어떤 노드를 거쳐서 가는 경우도 존재할 것이다
Author And Source
이 문제에 관하여(파이썬 알고리즘 080 | 플로이드 워샬 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@myway00/파이썬-알고리즘-080-플로이드-워샬-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)