최단 경로

최단 경로

최단 경로란, 가장 짧은 경로를 찾는 알고리즘을 얘기하고, 가장 대표적인 알고리즘은 다음과 같다.

1. 다익스트라 최단 경로
2. 플로이드 워셜 알고리즘

다익스트라 최단 경로 알고리즘

매번 가장 비용이 적은 노드를 선택해 다음의 과정을 반복한다.

1. 출발 노드를 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 3,4를 반복

다익스트라 알고리즘은 일종의 그리디 알고리즘이라고 한다. 구현 방법은 2가지가 있는데, 구현하기가 조금 까다롭지만 빠르게 동작하는 코드에 대해 무조건적으로 외우는 것이 좋다고 한다. 힙큐를 이용한 우선순위 큐를 구성하는 방법에 대해 외우자.

플로이드 워셜 알고리즘

다익스트라는 “한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우”에 사용하고, 이것은 “모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우”에 사용된다.