jhrsya

用户名：1564244868

访问量：13193

签　名：

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

　　自我简介：

TA的其他文章

数据结构-Dijskra(迪杰斯特拉)最短路径算法（C++代码）
浏览：727

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

dijkstra算法，最小堆实现
浏览：209

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

数据结构-Dijskra(迪杰斯特拉)最短路径算法（C++代码）

　　作者: jhrsya　　　　发表时间：2020-02-03 13:03:39 浏览：727　|　评论：0　

原题链接：数据结构-Dijskra(迪杰斯特拉)最短路径算法

#dijkstra算法与prim算法极其相似，见https://blog.dotcpp.com/a/64796
	
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    #define INF (1 << 21) 
    
    static const int MAX = 500;
    int cost[MAX][MAX];  //cost[i][j]数组表示点i 与点j 的距离 
    int d[MAX];			//d[i]表示源点s 距离i 点的距离 
    bool used[MAX];		//used[i] 表示点i 是否加入已确定的顶点 
    int V;
    
    void dijkstra(int s){
    
    	for(int i = 0; i < V; i++){		// 初始化d[i],和used[i]数组 
    		d[i] = INF;
    		used[i] = false;
    	}
    	d[s] = 0;		//起点s 距离 s点的距离为0 
    	
    	while(true){
    		int v = -1;
    		for(int u = 0; u < V; u++){		//从尚未使用过的顶点中选取距离最小的顶点 
    			if(!used[u] && (v == -1 || d[u] < d[v] )) v = u;
    		}
    		
    		if(v == -1) break;
    		used[v] = true;
    		for(int u = 0 ; u < V; u++){		//更新d[i]，取之前的的d[i]值与 v点到u 点距离的最小值 
    			d[u] = min(d[u], d[v] + cost[v][u]);
    		}
    	}
    }
    int main()
    {
    	int s;
    	cin >> V >> s;
    	int x;
    	for(int i = 0; i < V; i++){
    		for(int j = 0; j < V; j++){		//输入cost[][],如果输入的是0，则设置为无穷大，即两点间无边 
    			cin >> x;
    			if(x == 0)
    				cost[i][j] = INF;
    			else{
    				cost[i][j] = x;
    			}
    			 
    		}
    	}
    	
    	
    	dijkstra(s);
    	for(int i = 0; i < V; i++){
    		if(i == s) continue;
    		cout << (d[i] == INF ? -1 : d[i]) << " ";
    	}
    	return 0;
    }

0.0分

5 人评分

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

jhrsya

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

The 3n + 1 problem （C语言代码）

Tom数（C语言代码）

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

数据结构-Dijskra(迪杰斯特拉)最短路径算法（C++代码）

评论区

精彩推荐

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

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

字符串输入输出函数（Java代码）

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

c primer plus 第十二章 12.1小节

简单的a+b （C语言代码）

DNA （C语言描述，蓝桥杯）

1157题解

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

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

jhrsya

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

The 3n + 1 problem （C语言代码）

Tom数 （C语言代码）

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

数据结构-Dijskra(迪杰斯特拉)最短路径算法 （C++代码）

评论区

精彩推荐

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

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

字符串输入输出函数 （Java代码）

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

c primer plus 第十二章 12.1小节

简单的a+b （C语言代码）

DNA （C语言描述，蓝桥杯）

1157题解

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

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

Tom数（C语言代码）

数据结构-Dijskra(迪杰斯特拉)最短路径算法（C++代码）

　　评论区

字符串输入输出函数（Java代码）