정확히 k 개의 에지가 있는 소스에서 목적지까지 도보 가능

방향 그래프가 제공됩니다. 또 다른 두 꼭짓점 u와 v도 제공되며 u는 시작 꼭짓점이고 v는 끝 꼭짓점입니다. 우리의 임무는 꼭짓점 u에서 v까지 정확히 k개의 모서리를 가진 여러 도보를 찾는 것입니다. k 값도 알고리즘에 제공됩니다.

동적 프로그래밍을 사용하여 행이 u 값을 가리키고 열이 v 값을 가리키고 깊이가 처음부터 끝까지 가장자리 수를 추적하는 데 사용되는 3D 테이블을 만들어야 합니다.

입력 및 출력

입력:그래프의 인접 행렬:대상 정점은 3입니다. K =20 1 1 10 0 10 0 0 10 0 0 0출력:2개의 가장자리가 있는 0에서 3까지 2개의 가능한 걷기가 있습니다. 
알고리즘
 
numberOdWalks(u, v, k)
 

 입력: 시작 정점 u, 끝 정점 v, 모서리 수 k.
 

 출력: k 개의 가장자리가 있는 가능한 걷기 수입니다.
 
3D 배열 순서 정의 시작(nxnx k+1) //n은 범위 0에서 k의 가장자리에 대한 꼭짓점의 수, 범위 0에서 n-1의 i에 대해 수행, 범위 0에서 n까지의 j에 대해 수행 -1, do count[i, j, edge] :=edge =0이고 i =j이면 0이고, edge =1이고 (i, j)가 연결된 경우 count[i, j, edge] :=1, 다음 count[i, j, edge] :=1 if edge> 1, 범위 0에서 n까지이고 i와 인접하여 count[i, j, edge] :=count[i, j, edge] + count [a, j, edge - 1] done done done done return count[u, v, k]End
 
예시
 
#include #define NODE 7 using namespace std;int graph[NODE][NODE] ={ {0, 1, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}}; int numberOfWalks(int u, int v, int k) { int count[NODE][NODE][k+1]; for (int edge =0; edge <=k; edge++) { //k edge (0..k) for (int i =0; i 1) { //둘 이상의 에지 for (int a =0; a  
출력
 
2개의 가장자리가 있는 0에서 3까지 2개의 가능한 걷기가 있습니다.