jhrsya

用户名：1564244868

访问量：13193

签　名：

等　　级
排　　名	644
经　　验	4066
参赛次数	2
文章发表	49
年　　龄	0
在职情况	学生
学　　校	南昌大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-数的统计-题解(C++代码)
浏览：125

蓝桥杯算法提高VIP-摆花-题解(C++代码)
浏览：82

链表解答p38
浏览：233

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

数据结构-Floyd(弗洛伊德)最短路径算法-题解(C++代码)

　　作者: jhrsya　　　　发表时间：2020-02-03 20:27:02 浏览：701　|　评论：0　

原题链接：数据结构-Floyd(弗洛伊德)最短路径算法

#floyd算法

用于计算图任意两点间最短距离

实际上可以用动态规划的解决方案，属于DP问题

只使用顶点0~k和i,j的情况下，记i到j的最短路径为d[k+1][i][j]

我们分i到j的最短路正好经过顶点k一次和完全不经过顶点k两种情况来讨论：

1、不经过顶点k的情况下d[k][i][j] = d[k-1][i][j]

2、经过顶点k的情况下，d[k][i][j] = d[k-1][i][k] + d[k-1][k][j]

综上所述：d[k][i][j] = min(d[k-1][i][j], d[k-1][i][j]),这个DP也可以使用同一个数组，不断进行d[i][j] = min(d[i][j], d[i][k] + d[k][j])更新来实现

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    #define INF (1 << 21) 
    
    static const int MAX = 500;
    
    int d[MAX][MAX];	//最小距离
    
    
    int V,s;
     
    void floyd(){
    	for(int k = 0; k < V; k++){
    		for(int i = 0; i < V; i++){
    			for(int j = 0; j < V; j++){
    				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    			}
    		}
    	}
    }
    int main(){
    	cin >> V;
    	int x;
    	for(int i = 0; i < V; i++){
    		for(int j = 0; j < V; j++){		
    			cin >> x;
    			if(x == 0){
    				d[i][j] = INF;
    			}
    			else{
    				d[i][j] = x;
    			}
    		}
    	}
    	
    	floyd();
    	for(int i = 0; i < V; i++){
    		for(int j = 0; j < V; j++){
    			if(i == j) d[i][j] = 0;
    			cout << (d[i][j] == INF ? -1 : d[i][j]) << " ";
    		}
    		cout << endl;
    	}
    	return 0;
    }

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

jhrsya

TA的其他文章

你可能喜欢

关于逻辑非“！”与取反“~”运算符

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

数据结构-Floyd(弗洛伊德)最短路径算法-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

时间转换（Java代码）

【偶数求和】（C语言代码）

WU-格式化数据输出（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

大神老白（C语言代码）

众数问题（C语言代码）

jhrsya

TA的其他文章

你可能喜欢

关于逻辑非“！”与取反“~”运算符

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

数据结构-Floyd(弗洛伊德)最短路径算法-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

时间转换 （Java代码）

【偶数求和】 （C语言代码）

WU-格式化数据输出 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

大神老白 （C语言代码）

众数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

　　评论区

时间转换（Java代码）

【偶数求和】（C语言代码）

WU-格式化数据输出（C语言代码）

大神老白（C语言代码）

众数问题（C语言代码）