가장자리가 교차하지 않는 최단 경로 수를 찾으십시오.

Question

가중치가있는 비선형 그래프가 있고, 정점을 시작하고 끝내면 어떤 가장자리에서 이 교차하지 않는 정확히 동일한 (가중치의 합계에서) 최단 경로 수를 찾아야합니다..

여기에서는 Ford-Fulkerson의 알고리즘을 사용하려고 시도했지만 가능한 최대 수만 제공하고 최단 경로는 찾지 않습니다.

Ford-Fulkerson에서 경로를 찾는 Dijkstra의 알고리즘을 사용하면 경로를 최적의 솔루션으로 연결하는 하나 이상의 에지가있는 경로를 찾을 수 있기 때문에 도움이되지 않습니다.

제가 알기로는 비슷한 문제에 대한 답변이 있지만 가중치가 있고 지향적 인 그래프가 있습니다. 몇 가지 순서로 가장자리를 제거 할 수있는 무차별 방식이 필요합니다. 또는이 문제를 해결할 수있는 알려진 방법이있을 수 있습니까? 감사.

편집 1 : 여기 Dijkstra의 잘못된 길을 보여주는 그래프가 있습니다. 빨간색 가장자리 (대부분)가 1 위를 차지하고 최적의 솔루션을 만들 수 없습니다. 나는 우리가 먼저 계산할 수 Vedang 메타가

Answer 1

을 무엇을 제안 알고리즘의 목표는 어떻게 든 모든 빨간색 가장자리를 제거하는 것입니다 참조 DIS [U] : 유 처음부터 최단 경로의 = 길이.

그렇다면 우리는 DIS [] 및 G로부터 직접 그래프 (네트워크 흐름) G '구성 :

체크 모든 에지 (U, V) G에

if dis[u] = dis[v] + weight(u,v) then add a direct edge (u->v) to G'(capacities 1) 

if dis[v] = dis[u] + weight(u,v) then add a direct edge (v->u) to G'(capacities 1) 

않는 에지의 최대 개수 - 가장 짧은 경로를 교차하는 것은 단지

G '의 시작 정점부터 끝 정점까지의 최대 흐름입니다. 정확성

의

분명

증명. 여기

는 구현을

http://lemon.cs.elte.hu/pub/doc/latest-svn/a00238.html