파이썬 최단경로 구하기 (NetworkX 라이브러리)

※ NetworkX 라이브러리 설치 필요

https://networkx.github.io/

 

 

위 그래프에서 1부터 6까지 가는 최단 경로와 길이를 구한다고 가정

최단 경로는 1 -> 4 -> 3 -> 6, 길이는 16이 나와야 함.

 

(1,3,6=18, 1,2,5,6=19, 1,4,3,5,6=20, 1,2,5,3,6=31... 이기 때문)

import networkx as nx
import matplotlib.pyplot as plt

# Directed Graph
G = nx.DiGraph()

# G 그래프 만들기 (node 간의 edge가 존재하면 add_node 하고 add_edge 안해도 됨
# G.add_edge(node_i, node_k, distance=X)

# 연결 안 된 노드가 있을 경우를 방지
if nx.has_path(G, sourceNode, targetNode):
    length = nx.shortest_path_length(G, source=sourceNode, target=targetNode, weight='distance')
    path = nx.shortest_path(G, source=sourceNode, target=targetNode, weight='distance')

# 그래프로 표현하기
pos=nx.spring_layout(G)
nx.draw(G, pos=pos, with_labels=True)

labels = nx.get_edge_attributes(G,'distance')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)

# graph.png 로 저장
plt.savefig("graph.png")
plt.show()

 

length는 16

path는 ['1', '4', '3', '6']

 

nx.shortest_path_length가 최단 경로 길이 구하는 함수 (실수)

nx.shortest_path가 최단 경로 구하는 함수 (['A', 'B', 'C'] 형식)

 

(위 함수들은 dijkstra 알고리즘 사용, 추천 :

https://www.bogotobogo.com/python/python_Dijkstras_Shortest_Path_Algorithm.php)

# start = 시작 node를 visited에 넣음 (방식은 다양)
# ie) dijkstra(graph, 'A')
def dijkstra(graph, start):
    visited = {start: 0}
    path = {}

    nodes = set(graph.nodes)

    while nodes:
        min_node = None
        for node in nodes:
            if node in visited:
                if min_node is None:
                    min_node = node
                elif visited[node] < visited[min_node]:
                    min_node = node
        if min_node is None:
            break

        nodes.remove(min_node)
        current_weight = visited[min_node]

        for edge in graph.edges[min_node]:
            try:
                weight = current_weight + graph.distances[(min_node, edge)]
            except:
                continue
            if edge not in visited or weight < visited[edge]:
                visited[edge] = weight
                path[edge] = min_node

    return visited, path

 

사용법은 그래프 G, 출발 노드, 도착 노드, weight 지정하면 끝

 

A* 최단경로 알고리즘 : https://choiseokwon.tistory.com/210