일반적인 최단 경로 알고리즘이 단 하나의 최단 경로만을 반환하는 것과 달리, 옌(Yen)의 k-최단 경로 알고리즘은 k개의 최단 경로를 한꺼번에 구해 줍니다. 덕분에 최단 경로뿐 아니라 두 번째 최단 경로, 세 번째 최단 경로 등도 차례대로 얻을 수 있습니다.
A 지점에서 B 지점으로 이동해야 하는 상황을 가정해 봅시다. 두 지점 사이에는 여러 갈래의 경로가 존재하지만, 우리는 실행 시간 측면에서 비효율적인 경로들은 제외하고 목적지에 도달하는 최단 경로를 찾아야 합니다.
구체적인 예시를 통해 살펴보겠습니다.
위 예제를 꼭대기에 정점 B가 있는 아치형 다리라고 생각해 봅시다. 누군가 A 지점에서 C 지점으로 다리를 건너고자 할 때, 굳이 꼭대기(B)까지 올라갔다가 내려오는 사람은 없을 것입니다. 결국 B를 경유하는 경로는 A에서 C로 바로 가는 경로보다 더 길어집니다.
최단 경로를 구하는 방법은 여러 가지가 있지만, k-최단 경로 문제에서는 첫 번째부터 (k-1)번째 최단 경로까지 모두 찾아내야 합니다.
옌의 k-최단 경로 알고리즘의 동작 원리
옌의 알고리즘은 1971년 Jin Y. Yen이 제안한 방법으로, 데이크스트라(Dijkstra) 알고리즘을 반복적으로 활용하여 루프가 없는(loopless) k개의 최단 경로를 찾습니다. 핵심 동작 과정은 다음과 같습니다.
- 스퍼 노드(Spur Node) 지정: 이전에 찾은 경로 위의 각 노드를 차례로 스퍼 노드로 설정합니다.
- 간선 제거: 새로운 경로가 기존 최단 경로와 중복되지 않도록, 스퍼 노드 이후 구간의 간선을 임시로 제거합니다.
- 후보 경로 생성: 스퍼 노드에서 목적지까지의 최단 경로를 다시 계산하여 후보 목록에 추가합니다.
- 반복 선택: 후보 경로 중 가장 짧은 것을 결과 집합에 넣고, k개의 경로가 모일 때까지 이 과정을 반복합니다.
이 알고리즘의 시간 복잡도는 O(kn(m + n log n))으로 알려져 있으며, 여기서 n은 노드 수, m은 간선 수를 의미합니다.
k-최단 경로 알고리즘 구현 예제
다음은 Neo4j 그래프 데이터베이스의 Cypher 쿼리와 Python 드라이버를 사용하여 출발지에서 목적지까지 k-최단 경로를 조회하는 예제 코드입니다.
query = """
MATCH (start:Place {id: $source}), (end:Place {id: $destination})
CALL algo.kshortestPaths.stream(start, end, 10, "distance")
YIELD nodeIds, costs, index
RETURN index,
[nodeId IN nodeIds | algo.getNodeById(nodeId).id] AS nodeNames,
reduce(acc = 0.0, cost IN costs | acc + cost) AS totalCost
"""
params = {"source": "Alex", "destination": "US"}
with driver.session() as session:
rows = session.run(query, params)
df = pd.DataFrame([dict(record) for record in rows])
pd.set_option('max_colwidth', 100)
display(df)
이 코드는 출발지(Alex)에서 목적지(US)까지 거리(distance)를 기준으로 최대 10개의 최단 경로를 스트림 형태로 조회한 뒤, 각 경로의 노드 목록과 총 비용을 데이터프레임으로 정리하여 화면에 출력합니다. 이처럼 k-최단 경로 알고리즘은 내비게이션 대안 경로 추천, 네트워크 이중화 설계 등 실무에서 다양하게 활용됩니다.