경로 길이 제한이있는 원본 대상 사이의 모든 경로 찾기

Question

저는 python 2.7 및 networkx를 사용하고 있습니다.

저는 꽤 큰 네트워크를 가지고 있으며, 출발지와 목적지 사이의 모든 경로 (최단 경로는 물론)를 찾아야합니다. 내 네트워크가 크기 때문에 경로 길이, 비용 등과 같은 몇 가지 제약 조건으로 속도를 높이고 싶습니다.

networkx를 사용하고 있습니다. all_simple_paths를 사용하기 때문에 all_simple_paths를 사용하고 싶지 않습니다. 나중에 경로 길이 (노드 수) 또는 경로 비용 (아크 비용 기준)을 기반으로 모든 경로를 필터링해야합니다. 모든 경로를 필터링하는 것은 대규모 네트워크의 경우 매우 비쌉니다.

난 정말 어떤 도움을 주셔서 감사합니다.

Answer 1

정말 찾는 경로에 따라 다릅니다.

가장 짧은 경로는 길이 제약 조건에서 가장 낮은 경계 인 c_min을 제공합니다. 그런 다음 길이 제한 c>=c_min이 주어지면 각 노드 n에 대해 P_s_n의 최단 경로와 시작부터이 노드까지의 거리 c_n을 알 수 있습니다. c_n <c을 만족하는 노드를 선택하십시오. 그런 다음 P_s_n을 임의의 경로 n에서 목표까지 확장 할 수 있습니다. 이는 길이 제약 조건을 충족시킵니다.