최단 경로, 플로이드 워셜 알고리즘
📌플로이드 워셜 알고리즘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용(다익스트라 알고리즘: 한 지점에서 다른 특정 지점까지의 최단 경로 구하는 경우 사용) 시간복잡도: O(N³) 다이나믹 프로그래밍노드의 개수 N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신 📌플로이드 워셜 알고리즘 소스 코드INF = int(1e9) # 무한, 10억# 노드의 개수와 간선의 개수 입력받기n = int(input())m = int(input())# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화graph = [[INF] * (n + 1) for _ in rang..
코딩테스트
2024. 11. 5. 19:05