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一定要放在最外层
全部评论
相关推荐
10-23 10:30
杭州电子科技大学 Java 
YIYI啊：不要去制造业，特别是这种流程给特别快的厂，说明流动率高，加班严重。你可是杭电的学生，把这个工作机会留给普通双非吧 点赞 评论 收藏
分享