알고리즘은 유향 그래프에

Question

가능한 복제를 서로 다른 경로의 수를 확인하는 방법은 다음과 같습니다
Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

나는 유향 그래프를 가지고, 나는 별개의 수를 찾는 데 사용할 수있는 알고리즘 두 개의 특정 꼭지점 사이의 비순환 경로를 계산하고 이러한 경로에서 모든 경로가 사용되는 최대 시간을 계산합니까? 서로 다른 수의 정점을 방문하거나 다른 순서로 정점을 방문하면 두 경로가 구별됩니다.

Answer 1

약간 수정 된 Dijkstra 알고리즘을 따르면 모든 쌍 솔루션을 사용할 수 있습니다.

설명 : w 통과 w

경로 = 경로의 수를 통과하지 않는

1. 경로 u에서 v에을 : v-u에서 경로는 다음의 합이다 u에서 w번w에서
까지의 경로 수

i에서 j (1 인 경우)의 가장자리가있는 경우를 제외하고는 0으로 매트릭스를 초기화하십시오. 그런 다음 다음의 알고리즘 (모든 쌍 경로 카운트) 말할 필요도없이

for i = 1 to n: 
    for j = 1 to n: 
     for k = 1 to n: 
      paths[i][i] += paths[i][k] * paths[k][j] 

당신에게 결과를 줄 것이다 : O(n^3)

한 쌍 솔루션을 읽을 열망. :)