Dijkstra算法

Dijkstra算法

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其它全部节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但因为它遍历计算的节点非常多,所以效率低。

  Dijkstra算法是非常有代表性的最短路算法,在非常多专业课程中都作为基本内容有具体的介绍,如数据结构,图论,运筹学等等。

其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间仅仅经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每一个顶点所相应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u加入�到S中,同一时候对数组dist作必要的改动。一旦S包括了全部V中顶点,dist就记录了从源到全部其他顶点之间的最短路径长度。

比如,对下图中的有向图,应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下表中。

Dijkstra算法
Dijkstra算法的迭代过程:

Dijkstra算法

eg:

在每年的校赛里,全部进入决赛的同学都会获得一件非常美丽的t-shirt。可是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以如今他们想要寻找最短的从商店到赛场的路线,你能够帮助他们吗?
 
Input
输入包含多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包含3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员须要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。
 
Output
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
 
Sample Input
2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0

 
Sample Output
3 2

#include<iostream>
#include<stdio.h>
#include<iomanip>
using namespace std;
#define N 10000
#define MAX 100000099
int a[N][N];
int dist[N];

void input(int n,int m)
{
	int p,q,len,i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			a[i][j]=MAX;
		dist[i]=MAX;
	}
	for(i=0;i<m;i++)
	{
		cin>>p>>q>>len;
		if(len<a[p][q])
		{
			a[p][q]=len;
			a[q][p]=len;
		}
	}
}

void dijkstra(int n)
{
	int s[N],newdist,i;
	for(i=1;i<=n;i++)
	{
		dist[i]=a[1][i];
		s[i]=0;
	}
	dist[1]=0;
	s[1]=1;
	for(i=2;i<=n;i++)
	{
		int j,tem=MAX;
		int u=1;
		for(j=2;j<=n;j++)
			if(!s[j]&&dist[j]<tem)
			{
				u=j;
				tem=dist[j];
			}
		s[u]=1;
		for(j=2;j<=n;j++)
		{
			if(!s[j]&&a[u][j]<MAX)
			{
				newdist=dist[u]+a[u][j];
				if(newdist<dist[j])
					dist[j]=newdist;
			}
		}
	}
}

int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m),m||n)
	{
		input(n,m);
		dijkstra(n);
		cout<<dist[n]<<endl;
	}
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118482.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • html content属性_HTTP函数

    html content属性_HTTP函数关于HttpEntity的用法HttpEntity表示http的request和resposne实体,它由消息头和消息体组成。从HttpEntity中可以获取http请求头和回应头,也可以获取http请求体和回应体信息。HttpEntity的使用,与@RequestBody、@ResponseBody类似。HttpEntity的典型应用是配合RestTemplate,在微服务项目中的应用(参见API示例)用户登录示例:步骤一:在login.jsp发送ajax请求,发送之前添加请求头信息

    2022年10月23日
  • 计算机专业的男生喜欢你,【男生这十个反应说明他喜欢你】_男人的10个表现说明他喜欢上了你…

    计算机专业的男生喜欢你,【男生这十个反应说明他喜欢你】_男人的10个表现说明他喜欢上了你…[onlylady乐活健康情感]男人是一种奇怪动物.和他看不上的女人说话时,他表现得十分自然大方,仿佛兄弟.和他看上的女人说话时,则表现得有点扭捏.1、和女人说话时,不太敢正面女人,而是常常温柔地瞟女人.男人是一种奇怪动物.和他看不上的女人说话时,他表现得十分自然大方,仿佛兄弟.和他看上的女人说话时,则表现得有点扭捏.并非缺乏正面女人的勇气,而是心底不由自主的害羞在作祟.对了,还有一种伴发症…

  • VirtualBox安装Mac OS 10.11——虚拟机安装黑苹果

    VirtualBox安装MacOS10.11,安装日期:2016/5/14用虚拟机装黑苹果本人也装了不下3次了,这次为了做这个教程还特意把virtualbox和旧版的MacOS删了,重新再装一遍。所以保证能运行,不像网上其他教程都是导出复制,还不要脸的贴个原创。VirtualBox是官网下的最新版:5.0.20forWindowshostsx

  • 二叉树的非递归遍历

    二叉树的非递归遍历

  • otn与stn网络_mstp和stn的区别

    otn与stn网络_mstp和stn的区别SDH、MSTP、OTN和PTN的区别和联系看了很多人写的关于SDH、PTN和O…SDH、MSTP、OTN和PTN的区别和联系_信息与通信_工程科技_专业资料。首…SDH与MSTP_信息与通信_工程科技_专业资料。一、判断题(共5道小题,共50.0分)1.以字节交错间插方式构成高阶STM-N(N>1)段开销时,第一个STM-1……MSTP、SDH+ATM、OT…

    2022年10月18日
  • 软件定义网络(SDN)基础概念学习笔记(下)

    软件定义网络(SDN)基础概念学习笔记(下)第四章1.南向接口协议设计目标/主要任务承上启下,分离控制平面与数据平面实现网络配置与管理实现路径计算,包括网络开销、链路状态等已实现的南向接口协议Openflow:Openflow交换机与控制器的信息交互OF-Config:Openflow交换机的配置和管理NETCONF:网络设备的配置与管理OVSDB:OpenvSwitch的配置与管理XMPP:用于即时通讯(O…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号