动态规划输出所有路径c++
时间: 2023-12-21 14:56:38 浏览: 155
动态规划求解最短路径通常使用Dijkstra算法,而不是输出所有路径。不过如果您确实需要输出所有路径,可以使用回溯法来实现。
假设我们有一个有向无环图,我们可以使用动态规划来求解从起点到终点的所有路径。
首先,我们需要建立一个存储路径的数据结构,例如一个vector。接着,我们定义一个二维数组dp[i][j],其中dp[i][j]表示从起点到第i个节点的所有路径中,长度为j的路径的数量。
我们可以使用以下递推式来计算dp[i][j]:
dp[i][j] = 0; // 初始化
for (k = 0; k < n; k++) {
if (graph[k][i] != 0) {
for (l = 1; l <= j-1; l++) {
if (dp[k][l] != 0) {
for (m = 0; m < dp[k][l]; m++) {
vector<int> tmp = paths[k][l][m];
tmp.push_back(i);
paths[i][j].push_back(tmp);
}
}
}
}
}
if (graph[start][i] != 0) {
paths[i][1].push_back(vector<int>(1, start));
dp[i][1] = 1;
}
其中,n表示图中节点的数量,graph[i][j]表示从节点i到节点j的边的权重,start表示起点。
最后,我们可以遍历dp[end]中的所有路径,将它们输出。
完整代码如下:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
int graph[MAXN][MAXN];
int dp[MAXN][MAXN];
vector<vector<int>> paths[MAXN][MAXN];
void print_paths(int start, int end) {
for (auto path : paths[end][dp[end]]) {
if (path[0] == start) {
for (int i = 0; i < path.size(); i++) {
cout << path[i];
if (i != path.size() - 1) {
cout << " -> ";
}
}
cout << endl;
}
}
}
int main() {
int n, m, start, end;
cin >> n >> m >> start >> end;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = w;
}
for (int i = 0; i < n; i++) {
dp[i][0] = 1;
}
for (int j = 1; j <= n; j++) {
for (int i = 0; i < n; i++) {
dp[i][j] = 0;
if (j == 1 && i == start) {
paths[i][1].push_back(vector<int>(1, start));
dp[i][1] = 1;
} else {
for (int k = 0; k < n; k++) {
if (graph[k][i] != 0) {
for (int l = 1; l <= j-1; l++) {
if (dp[k][l] != 0) {
for (int m = 0; m < dp[k][l]; m++) {
vector<int> tmp = paths[k][l][m];
tmp.push_back(i);
paths[i][j].push_back(tmp);
}
}
}
}
}
}
}
}
cout << "All paths from " << start << " to " << end << ":" << endl;
print_paths(start, end);
return 0;
}
```
阅读全文