Finding shortest path in a (un)directed network.

파이썬의 networkx 라이브러리는 directional이나 undirectional에 대해 shortest path를 찾기 매우 용이하다.

 

알고리즘은 dijkstra이 default이다.

 

directional의 경우 nx.DiGraph()로 만들어줘야한다.

 

'''
tutorial
B->A->D #1
A->C->D->E->B #2
'''
#------------------------------------
# un-directional network
#------------------------------------
import networkx as nx
undirection_net=nx.Graph()
undirection_net.add_edge('b','a') #1
undirection_net.add_edge('a','d') #1
undirection_net.add_edge('a','c') #2
undirection_net.add_edge('c','d') #2
undirection_net.add_edge('d','e') #2
undirection_net.add_edge('e','b') #2

nx.draw(undirection_net,with_labels=True) # 네트워크 그림 그리기용
undShort=nx.all_shortest_paths(undirection_net, 'a', 'b',method='dijkstra')
print([i for i in undShort])
# [['a','b']]
# 방향성 없는 네트워크라서 a-b로 나온다.

 

un-directional network

 

'''
tutorial
B->A->D #1
A->C->D->E->B #2
'''
#------------------------------------
# Directional network
#------------------------------------
import networkx as nx
direction_net=nx.DiGraph()
direction_net.add_edge('b','a') #1
direction_net.add_edge('a','d') #1
direction_net.add_edge('a','c') #2
direction_net.add_edge('c','d') #2
direction_net.add_edge('d','e') #2
direction_net.add_edge('e','b') #2

nx.draw(direction_net,with_labels=True) # 네트워크 그림 그리기
dShort=nx.all_shortest_paths(direction_net, 'a', 'b',method='dijkstra')
print([i for i in dShort])
# [['a','d','e','b']]
# 방향이 반영되어 나온다.