백준 1956

플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 '모든 정점간에 최단거리를 구하는 알고리즘' 입니다. 시간 복잡도는 O(n^3)이다. 두개의 정점과 정점을 거치는 중간점 총 3개를 모두 탐색해야 합니다. 핵심은 거쳐가는 정점을 기준으로 최단거리를 알아내는 것입니다 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단거리를 구하는 문제 입니다. 다익스트라 알고리즘 플로이드 워셜 알고리즘 한 정점에서 다른 모든 정점으로의 최단 거리 구하는 알고리즘 모든 정점에서 모든 정점으로의 최단거리 구하는 문제 코드 먼저 살펴보겠습니다 v, e = map(int, input().split()) INF = 10000000 dist = [INF * (v+1) for _ in range(v+1)] # 입력받은 간선들에 대한 정보로 거리정보 ..