从源到目的地的可能步行,恰好有 k 条边
给出了一个有向图。还给出了另外两个顶点u和v,u是起始顶点,v是结束顶点。我们的任务是找到从顶点u到顶点v且恰好有k条边的多次步行。算法中还提供了k的值。
通过使用动态规划,我们需要创建一个3D表,其中行将指向u的值,列将指向值v,深度将用于跟踪从头到尾的边数。
输入和输出
Input: The adjacency matrix of the graph: The destination vertex is 3. K = 2 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 Output: 有 2 Possible Walks, from 0 to 3 with 2 edges.
算法
numberOdWalks(u, v, k)
输入: 起始顶点u,结束顶点v,边数k。
输出:具有k条边的可能步行数。
Begin define 3D array count of order (n x n x k+1) //n是顶点数 for edge in range 0 to k, do for i in range 0 to n-1, do for j in range 0 to n-1, do count[i, j, edge] := 0 if edge = 0 and i = j, then count[i, j, edge] := 1 if edge = 1 and (i, j) is connected, then count[i, j, edge] := 1 if edge > 1, then for a in range 0 to n, and adjacent with i do 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条边(0..k) for (int i = 0; i < NODE; i++) { for (int j = 0; j < NODE; j++) { count[i][j][edge] = 0; //最初所有值都是0 if (edge == 0 && i == j) //当e为0且第i个和第j个节点相同时,只有一条路径 count[i][j][edge] = 1; if (edge == 1 && graph[i][j]) //当e为0并且从(i到j)的直接路径时,一条路径 count[i][j][edge] = 1; if (edge >1) { //对于多个边缘 for (int a = 0; a < NODE; a++) //与源i相邻 if (graph[i][a]) count[i][j][edge] += count[a][j][edge-1]; } } } } return count[u][v][k]; } int main() { int u = 0, v = 3, k = 2; cout << "有 "<< numberOfWalks(u, v, k)<<" Possible Walks, from "; cout <输出结果 有 2 Possible Walks, from 0 to 3 with 2 edges.