셀프 루프가있는 가중치가있는 가중치 그래프가 주어지면 주어진 노드 x에서 정확히 k 번째 떨어진 노드 목록을 찾으십니까?

Question

그래프의 각 에지는 1의 가중치를가집니다. 그래프는 사이클을 가질 수 있습니다. 노드가 자체 루프를 가지면 노드에 따라 0에서 무한대까지의 거리가 될 수 있습니다. 시간의 우리는 자기 반복을 가져 간다.

필자는 bfs를 사용하여 문제를 해결했지만 거리 제약 조건은 10 ​​^ 9 정도이므로 bfs가 느립니다.

주어진 그래프에서 (거리, 소스) 형태의 여러 쿼리를 요청할 것이고 o/p는 소스 정점에서 시작하여 주어진 거리에 정확히있는 노드 목록입니다.

제약

1<=Nodes<=500 
1<queries<=500 
1<=distance<=10^9 

나는 느낌이는 더 많은 반복 계산이있을 것입니다. 노드의 작은,하지만 어떻게 작은 문제에서 문제를 줄일 수 알아낼 수 없습니다.

효율적인 방법은 무엇입니까?

편집 : 매트릭스 지수를 사용하려고했지만 주어진 제한 조건에 대해서는 너무 느립니다. 문제의 제한 시간은 1 초입니다.

Answer 1

하자가 그래프, 그리고 다음 A를 인접 행렬을 정의 G = (V,E)이 매트릭스는

A[i][j] = 1  (V[i],V[j]) is in E 
      0  otherwise 

각 k 들면 :

는

(A^k)[i][j] > 0 if and only if there is a path from v[i] to v[j] of length exactly k. 

이것은이 행렬을 생성하고 계산 수단에 의해 지수, 쉽게 답을 얻을 수 있습니다.

빠른 지수 계산을 위해 을 산출 할 수 있습니다. 여기서 M(n)은 nXn 행렬에 대해 cost for matrix multiplication입니다.

동일한 그래프에서 다른 쿼리를 찾을 때 계산량을 절약 할 수 있습니다.

부록 - 주장의 증거 :

자료 : A^1 = A, 실제로의 정의에 의해 A, A[i][j]=1(V[i],V[j])이 E

가설에있는 경우에만 경우 : 주장을지지 모든 l<k

에 대한 올바른

A^k = A^(k-1)*A. 유도 가설에서, k-1 길이가 V[i]에서 V[j]까지 인 A^(k-1)[i][j] > 0 iff 경로가 있습니다.

인덱스가 i 및 j 인 두 개의 정점 v1,v2을 살펴 보겠습니다.
길이가 k 인 경우이를 v1->...->u->v2으로합시다. u의 색인을 m으로합시다.
i.h에서.A^(k-1)[i][m] > 0 경로가 있기 때문입니다. 또한 A[m][j] = 1이므로 (u,v2) = (V[m],V[j])은 가장자리입니다.

A^k[i][j] = A^(k-1)*A[i][j] = A^(k-1)[i][1]A[1][j] + ... + A^(k-1)[i][m]A[m][j] + ... + A^(k-1)[i][n]A[n][j] 

그리고 A[m][j] > 0 및 A^(k-1)[i][m] > 0, A^(k-1)*A[i][j] > 0

그러한 경로가없는 경우부터, 각 정점 u 이러한 (U, v2)는 에지는, 길이 k-1 어떠한 경로로부터는 없다고 v ~ u (기타 v1->..->u->v2은 길이가 k입니다).

유도 가설을 사용하면 A^(k-1)[i][m] > 0이면 A[m][j] = 0이면 모두 m입니다. 우리는 합계에 A^k[i][j]를 정의하는 것으로 지정하면
, 우리는 얻을 A^k[i][j] = 0

QED

작은 참고 : 기술적으로, A^k[i][j]이 i 길이 정확히 k의 j 사이의 경로의 수입니다. 위와 비슷하지만 세부 사항에 대해서는 조금 더주의를 기울여야합니다.
숫자가 너무 빠르게 증가하는 것을 피하려면 (그 값을 저장하기 위해 큰 정수가 필요할 수도 있으므로 M(n)이 증가 할 것입니다.) 그리고 0/1 이외의 값을 신경 쓰지 않으므로 - 행렬을 불리언으로 처리 할 수 ​​있습니다 - 0/1 값만 사용하고 다른 것은 다듬을 수 있습니다.

Answer 2

그래프에주기가있는 경우 인접한 각 노드 사이에 링크가 있다고 생각하면 cycle * N + 1이라고 생각하면됩니다. 원하는만큼 반복 할 수 있기 때문입니다.

그 아이디어에 나를 데려 오면, 우리는 우리의 장점을주기를 사용할 수 있습니다! 주기를 감지하면서 BFS를 사용
, 우리는 offset + cycle*N 계산하고 우리는 우리의 목표 (K)

에 가까운 얻을 꽤 쉽게 K를 검색합니다.

A → B → C → D → B K = 1000; S = A;

A - 0
B - 1
C - 2
D - 3
B - 여기서 1 (+ 4N)
는() k - (1+4N) = 0>1000 - 1 - 4N = 0>999 = 4N>N=249 => 바닥을 확인할 수 여기에서 round(k - offset, cycle)

가 더 많은 단지 몇 단계를 계산 할 수 있습니다 최고의 B는 997
간단한 방법은 계산하는 것 = 입니다.
(예 : REGEX) : A(BCD){249}BCD