최단 경로(Shortest Path): 가장 짧은 경로를 찾는 알고리즘으로, ‘길 찾기’ 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다.
예를 들어 ‘한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우’, ‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우’ 등의 다양한 사례가 존재한다.
최단 경로를 구하는 경우에 대한 알고리즘은 일반적으로 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3가지가 있으며 다익스트라와 플로이드 워셜 알고리즘을 다루려 한다.
이 유형만 파악해도 코딩 테스트 수준에서의 최단 경로 문제를 해결할 수 있다.
더불어 앞서 공부한 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징이 있다.
가중치 그래프에서 사용한다.
다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
‘음의 간선’이 없을 때 정상적으로 동작한다. 음의 간선이란, 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.
다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘을 분류된다. 매번 ‘가장 비용이 적은 노드’를 선택해서 임의의 과정을 반복하기 때문이다. 알고리즘의 원리를 간략히 설명하면 다음과 같다.
다익스트라는 최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다.
다익스트라 알고리즘을 구현하는 방법은 2가지이다.
방법 1. 구현하기 쉽지만 느리게 동작하는 코드
방법 2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드