[Networkx] 최단 경로 그리기

파이썬의 Networkx 패키지를 사용하여 다양한 그래프를 그릴수 있다.

 

자세한 내용은 Networkx 공식 문서를 보면 설명이 나와있다.

https://networkx.github.io/documentation/stable/

 

Networkx로 그래프를 형성하고 matplotlib를 사용해 직접 화면으로 출력해본다. 코드는 아래와 같다.

 

 
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
import math
 
G2 = nx.Graph()
# explicitly set positions
 
with open('./graph.txt') as f:
    n,l = [int(x) for x in next(f).split()]
    pos = [[int(x) for x in line.split()] for line in f]
 
# 파일 읽기를 위한 코드, n,l 변수에 파일 첫 라인을 정수값으로 저장
# pos에 나머지 각 라인들을 저장 : 노드들의 x,y값 맨 마지막 값은 시작 정정과 도착정점을 저장
 
for x in range(n):
    nx.draw_networkx_nodes(G2,pos,node_size = 100,nodelist=[x],node_color = 'g')
    print(x)
#x는 0~9까지 pos 리스트의 위치에 따라 노드를 그림, pos자료는 0~10까지 인덱스를 가짐 10번 인덱스는 시작정점과 도착정점
 
for x in range(n):
    for y in range(n):
        if x == y : continue
        if y < x : continue
        num = abs(pos[x][0]-pos[y][0])
        num2 = abs(pos[x][1] - pos[y][1])
        num3 = abs(num**2 + num2**2)
        #print(num,num2,math.sqrt(num3))
        if math.sqrt(num3) <= l:
            print(x,y)
            G2.add_edge(x,y)
#0~9까지의 각 노드사이의 거리가 l이하이면 edge를 연결
 
nx.draw_networkx_edges(G2,pos,alpha = 0.3)
#edge를 그림
 
 
path = nx.shortest_path(G2,source = pos[n][0],target = pos[n][1])
 
path_edges = zip(path,path[1:])
path_edges = set(path_edges)
#print(path_edges)
#시작정점에서 도착정점까지의 shrtest_path를 가지는 노드와 에지를 저장
#path 에는 노드가 path_edges에는 연결된 노드 쌍들이 저장됨
 
nx.draw_networkx_nodes(G2,pos,node_size = 100,nodelist = path,node_color = 'r')
nx.draw_networkx_edges(G2,pos,edgelist=path_edges,edge_color='r',width=1)
#shortest_path를 가지는 노드와 에지를 그림
 
plt.savefig("shortest_path.png") #출력결과 저장
plt.axis('on') # 좌표계를 표시
plt.show() #그림 출력

 

위와 같이 Networkx 모듈을 사용해 구현할 수 있다. 데이터는 각자 만들어 실험해보길 바란다.

 

결과는 아래와 같다.