최단 경로

최단 경로 (Shortest Path Problem) - 플로이드 워셜 알고리즘

플로이드 워셜 최단 거리 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다 각 단계마다 특정한 노드 𝑘를 거쳐 가는 경우를 확인한다 𝑎에서 𝑏로 가는 최단 거리보다 𝑎에서 𝑘를 거쳐 𝑏로 가는 거리가 더 짧은지 검사한다 시간 복잡도는 O($N^3$) → N번의 단계 마다 O($N^2$)의 연산을 통해 현재 거쳐가는 모든 경로 고려 점화..

최단 경로 (Shortest Path Problem) : 다익스트라 알고리즘

최단 경로 알고리즘 이란? 가장 짧은 경로를 찾는 알고리즘 길 찾기 문제라고도 부른다. ✔ 다양한 문제 상황에 사용 한 지점에서 다른 한 지점까지의 최단 경로 (single-pair) 한 지점에서 다른 모든 지점까지의 최단 경로 (single-source) 한 지점으로 가는 모든 최단 경로 (single-destination) 모든 지점에서 다른 모든 지점까지의 최단 경로 (all-pair) 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 등이 있다. 다익스트라 최단 경로 알고리즘 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든노드까지의 최단 거리를 구하는 알고리즘 그리디 알고..