무 방향성 그래프에서 두 정점 사이의 모든 최단 경로를 찾는 방법은 무엇입니까?

Question

그래프 G는 방향이없는 그래프이며 모든 에지의 가중치는 동일합니다. u, v는 주어진 2 개의 꼭지점이고, 그래프 G에서 u와 v 사이의 최단 경로 수를 찾는 방법은 O (| V |)입니까?

| V | G의 정점 수를 나타냅니다.

Answer 1

BFS의 계수 변동을 사용할 수 있습니다.

아이디어는 dict:(v,depth)->#paths을 매핑하는 사전 (항목은 정점 및 현재 깊이이며 값은 소스에서 원하는 깊이의이 정점까지의 경로 수임)을 보유하는 것입니다.

BFS를 반복 할 때마다 경로의 현재 깊이를 추적하고 발견 된 경로 수를 다음 단계에 추가합니다.

당신이 x로 이어지는 3 개 경로와 깊이 3 y 모두로 이어지는 4 개 경로가 있고, 모두 가장자리 (x,u),(y,u)이있는 경우 있다는 생각 - 3 선도 + x에 대한 실행 (x - 다음 u에 이르는 7 개 경로가 , u)이고, 4는 y + (y, u)가됩니다.

그렇게 보일 것이다 :

findNumPaths(s,t): 
    dict = {} //empty dictionary 
    dict[(s,0)] = 1 //empty path 
    queue <- new Queue() 
    queue.add((s,0)) 
    lastDepth = -1 
    while (!queue.isEmpty()) 
     (v,depth) = queue.pop() 
     if depth > lastDepth && (t,lastDepth) is in dict: //found all shortest paths 
      break 
     for each edge (v,u): 
      if (u,depth+1) is not entry in dict: 
       dict[(u,depth+1)] = 0 
       queue.push((u,depth+1)) //add u with depth+1 only once, no need for more! 
      dict[(u,depth+1)] = dict[(u,depth+1)] + dict[v,depth] 

     lastDepth = depth 
    return dic[t] 

실행 시간은 사전에 대한 해시 테이블을 사용하는 경우 O (V + E)이다.

---

다른 용액 (프로그램 용이하지만 덜 효율적이)이다 작동

1. Build the adjacency matrix of the graph, let it be `A`. 
2. Set `Curr = I` (identity matrix) 
3. while Curr[s][t] != 0: 
    3.1. Calculate Curr = Curr * A //matrix multiplication 
4. Return Curr[s][t] 

이유 (A^n)[x][y]가 A가 x에서 y에 나타내는 그래프의 크기 n의 경로의 수이다. 우리는 0보다 높은 첫 번째 숫자를 찾고 경로 수를 반환합니다.