[파이썬] scipy 최단 경로 찾기

06 Sep 2023

scipy

SciPy는 파이썬의 과학 계산용 라이브러리로, 다양한 과학, 수학 및 엔지니어링 애플리케이션에 사용됩니다. 이번 블로그 포스트에서는 SciPy를 활용하여 최단 경로를 찾는 방법에 대해 알아보겠습니다.

그래프 생성

최단 경로를 찾기 위해서는 먼저 그래프를 생성해야 합니다. 이는 노드와 간선의 집합으로 구성됩니다. 여기서는 간단한 그래프를 생성해보겠습니다.

import numpy as np
import networkx as nx

# 그래프 생성
G = nx.Graph()

# 노드 추가
G.add_node('A')
G.add_node('B')
G.add_node('C')
G.add_node('D')
G.add_node('E')

# 간선 추가
G.add_edge('A', 'B', weight=3)
G.add_edge('B', 'C', weight=4)
G.add_edge('C', 'D', weight=2)
G.add_edge('D', 'E', weight=5)
G.add_edge('E', 'A', weight=1)
G.add_edge('A', 'C', weight=2)

# 그래프 시각화
nx.draw(G, with_labels=True)

위의 코드는 networkx 라이브러리를 사용하여 그래프를 생성하고, 노드와 간선을 추가하는 예시입니다.

최단 경로 찾기

이제 그래프가 준비되었으므로 최단 경로를 찾을 수 있습니다. 최단 경로 알고리즘 중 대표적인 알고리즘은 다이크스트라(Dijkstra) 알고리즘입니다. SciPy의 shortest_path 함수를 사용하여 최단 경로를 찾을 수 있습니다.

from scipy.sparse.csgraph import shortest_path

# 최단 경로 찾기
dist_matrix, predecessors = shortest_path(G, return_predecessors=True)

# 출발점과 도착점 설정
start_node = 'A'
end_node = 'E'

# 최단 경로 출력
path = []
node = end_node
while node != start_node:
    path.append(node)
    node = predecessors[start_node][np.where(G.nodes == node)]
path.append(start_node)
path.reverse()

print(f'최단 경로: {" -> ".join(path)}')

위의 코드는 주어진 그래프에서 ‘A’ 노드에서 ‘E’ 노드로의 최단 경로를 찾는 예시입니다. shortest_path 함수를 사용하여 최단 경로를 찾고, return_predecessors=True로 설정하여 최단 경로의 이전 노드 정보를 반환받습니다. 마지막으로 최단 경로를 출력합니다.

결론

이번 포스트에서는 SciPy를 사용하여 최단 경로를 찾는 방법에 대해 알아보았습니다. SciPy는 다양한 최적화 및 알고리즘 기능을 제공하므로 과학 및 엔지니어링 분야에서 유용하게 활용될 수 있습니다. 최단 경로 문제는 이를 활용하여 다양한 애플리케이션에 적용할 수 있으니, 관심 있는 분야에서 활용해보시기 바랍니다.