알고리즘 - 플로이드 워셜
가중치가 있는 그래프에서 모든 노드에서 모든 노드로 이동할때의 최소비용은 어떻게 구할까?
다익스트라 알고리즘으로 가중치가있는 그래프에서 출발지로부터 다른 목적지까지 최소비용으로 탐색하는 법을 알 수 있었다.
그러나 출발지가 한 곳이 아니라 모든노드에서 출발하여 모든 노드로 도착할때 최소비용은 어떻게 구할까?
플로이드 워셜 알고리즘은
다이나믹 프로그래밍 알고리즘을 이용한다.
2차원 배열에 최소비용이 발견될때마다 값을 갱신한다.
다른 노드를 거쳐가는 경우를 확인한다.
import sys
import math
input = sys.stdin.readline
N = int(input())
M = int(input())
graph = [[math.inf]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
graph[i][i] = 0
for _ in range(M):
a,b,c = map(int, input().split())
graph[a][b] = min(graph[a][b], c)
for k in range(1, N+1):
for a in range(1, N+1):
for b in range(1, N+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
for a in range(1, N+1):
for b in range(1, N+1):
if graph[a][b] == math.inf:
print(0, end = ' ')
else:
print(graph[a][b], end=' ')
print()
플로이드 워셜 알고리즘의 시간복잡도는 O()이다.
노드의 갯수가 500정도만 되도, 1억2천5백만번을 연산 해야하므로
시간초과의 위험이 있다.
따라서 노드의 갯수가 적을때 사용해볼 수 있을 것이다.
Author And Source
이 문제에 관하여(알고리즘 - 플로이드 워셜), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mauserne/알고리즘-플로이드-워셜저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)