c++动态规划最短路径权重和四行五列
时间: 2023-12-25 22:29:30 浏览: 40
以下是使用动态规划算法求解最短路径权重和的C++代码示例,假设图的大小为四行五列:
```cpp
#include <iostream>
#include <climits>
using namespace std;
// 定义图的大小
#define ROW 4
#define COL 5
// 使用动态规划算法求解最短路径权重和
int shortestPath(int graph[ROW][COL]) {
// 创建一个二维数组来存储最短路径权重和
int dp[ROW][COL];
// 初始化dp数组
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
dp[i][j] = INT_MAX;
}
}
// 设置起点的最短路径权重和为起点的权值
dp[0][0] = graph[0][0];
// 从左上角开始计算最短路径权重和
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
// 更新右边的最短路径权重和
if (j + 1 < COL) {
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + graph[i][j + 1]);
}
// 更新下边的最短路径权重和
if (i + 1 < ROW) {
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + graph[i + 1][j]);
}
}
}
// 返回终点的最短路径权重和
return dp[ROW - 1][COL - 1];
}
int main() {
// 定义图的权值矩阵
int graph[ROW][COL] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}
};
// 调用函数求解最短路径权重和
int shortestWeight = shortestPath(graph);
// 输出最短路径权重和
cout << "The shortest path weight is: " << shortestWeight << endl;
return 0;
}
```