Networkx

Question

가장 짧은 경로를 선택하는 모호성은 I 그래프를 가지고

이유 최단 경로의 기능을 사용한 후 :

nx.shortest_path(g, 0, 6) 

[0, 3, 6] 출력 경로 왜

? 왜 [0, 2, 6]? 위의 경우 알고리즘 shortest_path()에 대한 경로 [0, 3, 6]의 선택이 항상 명확합니까?

Answer 1

@ jon-clements는 질문에 대한 답에 정답을 가지고 있습니다. 둘 이상의 최단 경로가있는 경우 networkx.shortest_path() 함수는 그 중 하나를 반환합니다. 특정 경로는 데이터가 networkx 그래프 데이터 구조 (파이썬 사전 기반)에 저장되는 방식에 따라 결정적 일 수 있습니다. 원하는 경우 최단 경로를 모두 가져올 수 있으며 정렬하여 정렬하여 안정적인 주문을 제공 할 수도 있습니다.

In [1]: import networkx as nx 

In [2]: G = nx.Graph({0: [3, 2], 2: [6, 4], 3: [5, 6]}) 

In [3]: nx.shortest_path(G, 0, 6) 
Out[3]: [0, 2, 6] 

In [4]: list(nx.all_shortest_paths(G, 0,6)) 
Out[4]: [[0, 3, 6], [0, 2, 6]] 

In [5]: sorted(nx.all_shortest_paths(G, 0,6)) 
Out[5]: [[0, 2, 6], [0, 3, 6]]