[NetworkX] 경로의 개념, 가장 짧은 경로 찾기

그래프를 그리고 나서 가장 유용하게 활용하는 방법 중 하나는 노드 간 거리를 활용하는 방법입니다.

어떤 노드가 가장 멀리 있는 노드인지,

이쪽 노드에서 저쪽 노드까지 얼마나 먼지를 계산할 수 있습니다.

 

그러러면 먼저 몇 가지 개념을 익혀야 하겠습니다.

 

경로 Path

• 단순히 선(엣지)에 의해 연결된 노드들의 순서를 의미함
• X노드에서 Y노드로 가는 경로의 수는 다양함

예시) A에서 H로 가는 경로

• A-B-C-E-H
• A-B-C-F-E-H
• A-K-B-C-F-E-H
• ....

 

경로의 길이 Path length

• 몇번 건너가면 도착하는가
• 즉, 몇개의 엣지로 이루어져 있는가

• A-B-C-E-H (길이: 4)
• A-B-C-F-E-H (길이: 5)

 

노드 간의 길이 Distance between two nodes

• 노드 간 길이 = 가장 짧은 경로의 길이

• A ~ H 간 길이 = 4 (A-B-C-E-H)

 

가장 짧은 경로 찾기, 가장 짧은 경로의 길이

# 가장 짧은 경로 찾기
nx.shortest_path(G, 'A', 'H')  # ['A','B','C','E','H']

# 가장 짧은 경로의 길이
nx.shortest_path(G, 'A', 'H')  # 4