
최단 경로 구하기 (다익스트라, 벨만-포드)
·
알고리즘(코딩테스트)
1. 다익스트라 알고리즘가중치가 있는 그래프의 최단경로를 구할 때 사용하는 알고리즘 다익스트라 알고리즘의 동작 방식은모든 노드의 최소 비용을 INF로 초기화한다.시작한 노드의 최소비용은 0, 직전 노드는 자기 자신으로 두고 시작이후 최소 비용이 가장 낮으면서 방문하지 않은 노드를 선택하여 최소 비용을 업데이트 한다.아래의 그림을 통해 어떤 방식으로 동작하는지 알 수 있다.최소 비용이 가장 낮은 A로 시작하여 모든 연결된 노드의 최소비용을 갱신 (A 방문)이후 최소비용이 가장 낮은 E노드를 시작으로 더 작은 최소비용이 되는 경로가 있다면 갱신 A->E->C가 기존의 A->C 보다 최소비용이 작으므로 갱신! (E 방문)이 방식을 모든 노드 방문할 때 까지 반복하기결과우리가 C까지의 경로를 알고 싶다면, C의..