galaxy

用户名：yppp

访问量：9180

签　名：

你只需要做的便是厚积薄发

等　　级
排　　名	1609
经　　验	2653
参赛次数	7
文章发表	18
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

酸菜鱼与黄焖鸡

TA的其他文章

排序-题解（C++代码）
浏览：272

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

数据结构-最小生成树-题解（C++代码）
浏览：290

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

　　作者: galaxy　　　　发表时间：2020-06-01 09:44:38 浏览：241　|　评论：0　

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

本题是利用迪杰斯特拉算法求解最短路径算法
我在代码中加了注释，话不多说，直接亮代码```cpp
    #include<iostream>
    using namespace std;
    const int N=100;
    int Graph[N][N];//读入一个有向图的带权邻接矩阵（即数组表示）
    int n;//表示图中共有n个顶点;
    int s;//且源点为s。
    bool visit[N];//该点是否被遍历过
    int d[N];//每一个点距离源点的最小距离
    const int INF = 100000000;//距离无穷大，表示不可达到
    
    //建立有向图
    void   Init()
    {//输入的第一行包含2个正整数n和s，且源点为s。其中n不超过50，s小于n。
    	cin >> n >> s;
    	 注意，这里的下标从 0 开始**
		//以后的n行中每行有n个用空格隔开的整数。
    	//邻接矩阵的初始化
    	for (int i = 0; i < n; i++)
    	{
    		for (int j = 0; j < n; j++)
    		{
    			cin >> Graph[i][j];		
    			if (Graph[i][j] == 0)
    			{
    				Graph[i][j] = INF;//输入数据为0 即为不可达到
    			}
    		}
    	}
    	for (int i = 0; i < n; i++)
    	{
    		visit[i] = false;
    		d[i] = INF;
    	}
    	d[s] = 0;//源点
    }
    void Dijskra()
    {
    	for (int i = 0; i < n; i++)
    	{
    		int min = INF;
    		int   k = -1;
    		for (int j = 0; j < n; j++)
    		{    //在未被遍历过的点中 找到到源点距离最小的点
    			if (d[j] < min&& visit[j] == false)
    			{
    				min = d[j];
    				k = j;
    			}
    		}
    		if(k==-1)
    		{
    			return;
    		}
    		visit[k] = true;
    		//以k为中间节点，更新未被遍历过的点与源点之间的最小距离
    		for (int j = 0;j<n;  j++)
    		{
    			if (visit[j] == false && Graph[k][j]!=INF&&Graph[k][j] + d[k] < d[j])
    			{
    				d[j] = Graph[k][j] + d[k];
    		    }
    		}
    	}
    }
    int main()
    {
    	Init();
    	Dijskra();
		输出函数
    	for (int l = 0; l < n; l++)
    	{
    		if (l != s)
    		{
    			if (d[l] != INF)
    			{
    				cout << d[l] << " ";
    			}
    			else
    			{
    				cout << -1 << " ";
    			}
    		}
    	}
    	return 0;
    }

0.0分

0 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

galaxy

TA的其他文章

你可能喜欢

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

小九九（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

人见人爱A+B （C++代码）

printf基础练习2 （C语言代码）

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

评论区

精彩推荐

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

【回文数(二)】（C++代码）

汽水瓶（C语言代码）

C语言训练-素数问题（C语言代码）

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

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

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

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

Cylinder （C语言描述+详细分析）

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

galaxy

TA的其他文章

你可能喜欢

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

小九九 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

人见人爱A+B （C++代码）

printf基础练习2 （C语言代码）

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

评论区

精彩推荐

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

【回文数(二)】 （C++代码）

汽水瓶 （C语言代码）

C语言训练-素数问题 （C语言代码）

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

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

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

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

Cylinder （C语言描述+详细分析）

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

小九九（C语言代码）

　　评论区

【回文数(二)】（C++代码）

汽水瓶（C语言代码）

C语言训练-素数问题（C语言代码）