动态规划求最短路径c++

下面是一份使用动态规划求解最短路径的 C++ 代码：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 定义矩阵类型
typedef vector<vector<int>> Matrix;

// 使用动态规划求解最短路径
int shortestPath(Matrix& graph, int source, int dest) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    dist[source] = 0;

    for (int k = 1; k < n; k++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0) {
                    if (dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                        dist[v] = dist[u] + graph[u][v];
                    }
                }
            }
        }
    }

    return dist[dest];
}

int main() {
    // 定义一个4*4的矩阵
    Matrix graph = {
        {0, 10, 3, 2},
        {INT_MAX, 0, INT_MAX, 7},
        {INT_MAX, INT_MAX, 0, 6},
        {INT_MAX, INT_MAX, INT_MAX, 0}
    };

    int source = 0;
    int dest = 3;

    int shortest = shortestPath(graph, source, dest);

    cout << "Shortest path from " << source << " to " << dest << " is " << shortest << endl;

    return 0;
}

这份代码使用了一个二维矩阵来表示有向图，其中每个元素 graph[i][j] 表示从节点 i 到节点 j 的距离。在求解过程中，我们使用了一个一维数组 dist 来记录源节点到各个节点的最短距离。我们首先将源节点的距离设置为 0，然后循环执行 n-1 次，每次都尝试更新 dist 数组中的元素。在更新 dist[u] 时，我们遍历所有与节点 u 相连的节点 v，并检查是否有更短的路径可以到达节点 v。如果有，我们就更新 dist[v]。最终，dist[dest] 就表示了源节点到目标节点的最短距离。