动态规划输出所有路径c++

动态规划求解最短路径通常使用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]中的所有路径，将它们输出。

完整代码如下：

#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;
}