[알고리듬] 플로이드-워셜 알고리즘 / python

[알고리듬] 플로이드-워셜 알고리즘 / python

모든 최단 경로를 구하는 알고리즘

노드 간의 최단 경로를 입려겨한 2차원 행렬을 구성한다.

경유지를 설정하고. 각 시행마다 새로운 경유지로 교체해가며, 기존의 출발->도착 경로 와 출발->new경유지->도착의 경로 를 비교하여 더 짧은 경로를 선택한다.

n = 6 fares = [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] # n : 노드의 수 # fares : 출발, 도착, 요금의 정보가 주어진다고 했을 때 INF = 1e10 # 충분히 큰 수 # dist -> x에서 y로 가는 운임 나타내는 2차원 요금지도 dist = [[INF for _ in range(n)] for _ in range(n)] # 나 자신 -> 나 자신으로 가는 경우 0으로 설정 for i in range(n): dist[i][i] = 0 # fares로 받은 운임 적용해주기 for info in fares: # 우린 인덱스를 0부터 쓰니깐 -1해주자 dist[info[0]-1][info[1]-1] = info[2] # 양방향으로 적용 dist[info[1]-1][info[0]-1] = info[2]

여기까지 적용하면 아래와 같은 2차원 요금지도 확인 가능

# 플로이드-워셜 알고리즘 적용 def floyd(dist, n): # i->j로 가는 최단거리를 저장하려고 하는거임 # k라는 경유지를 두고 i에서 j로 갈때 i->k->j가 빠른지 현재의 i->j가 빠른지 비교 for k in range(n): for i in range(n): for j in range(n): dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]) floyd(dist, n)

그럼 아래와 같은 모든 경로의 최단거리 알 수 있는 요금지도 완성

from http://hyunsix.tistory.com/143 by ccl(A) rewrite - 2021-09-23 22:26:18