2024-12-30 17:16 门头沟学院 C++ 发布于江西
关注
day61
Floyd多源最短路：
思路：动态规划
1、grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合为中间节点的最短距离为m；
2、递推公式：
节点i 到 节点j 的最短路径经过节点k：grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
节点i 到 节点j 的最短路径不经过节点k：grid[i][j][k] = grid[i][j][k - 1]
所以grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])
3、初始化：
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid[p1][p2][0] = val;
grid[p2][p1][0] = val; // 注意这里是双向图
}
4、遍历顺序：k一定要放在最外层
思路：动态规划
1、grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合为中间节点的最短距离为m；
2、递推公式：
节点i 到 节点j 的最短路径经过节点k：grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
节点i 到 节点j 的最短路径不经过节点k：grid[i][j][k] = grid[i][j][k - 1]
所以grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])
3、初始化：
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid[p1][p2][0] = val;
grid[p2][p1][0] = val; // 注意这里是双向图
}
4、遍历顺序：k一定要放在最外层
全部评论
相关推荐
莉莉丝游戏公司福利 614人发布 
码农索隆：以下是我以我微薄的认知提供的建议：
1.考个教师资格证，去当体育考试。
2.去健身房当健身教练（因为在我印象里面体育生身材都不错
）。 点赞 评论 收藏
分享