迪杰斯特拉算法应用

① 迪杰斯特拉算法适用大规模吗

适用。迪杰斯特拉算铅首法纤激肢(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算毁世法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。

② dijkstra算法有哪些

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径。

对于图G=（V，E），将图中的顶点分成两组：

第一组S：已求出的最短路径的终点集合（开始为{v0}）。

第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）。

算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中，直到所有顶点都被加入到第一组顶点集S为止。

(2)迪杰斯特拉算法应用扩展阅读：

从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点，需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

③ dijkstra算法是什么

dijkstra算法最短路径算法。

Dijkstra是典型最短路径算法，用于计算一个节点到其他节点的最短路径。该算法使用的是贪心策略：每次都找出剩余顶点中与源点距离最近的一个顶点。

给定一带权图，图中每条边的权值是非负的，代表着两顶点之间的距离。指定图中的一顶点为源点，找出源点到其它顶点的最短路径和其长度的问题，即是单源最短路径问题。

Dijkstra的原理

（1）初始化时，S只含有源节点。

（2）从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源节点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值是顶点k的距离加上k到u的距离。

④ dijkstra算法是什么

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径。

对于图G=（V，E），将图中的顶点分成两组：第一组S：已求出的最短路径的终点集合（开始为｛v0}）。第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）。

堆优化

思考

该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。

实现

1、将源点加入堆，并调整堆。

2、选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。

3、处理与u相邻的，未被访问过的，满足三角不等式的顶点

1):若该点在堆里，更新距离，并调整该元素在堆中的位置。

2):若该点不在堆里，加入堆，更新堆。

4、若取到的u为终点，结束算法；否则重复步骤2、3。

⑤ 关于matlab中的一个Dijkstra算法应用

这个算法算起始点到其他点的最短路径。
function [d,index1,index2]=Dijkf(a)
%两点间最短距离的Dijkstra算法
% a表示图的权值矩阵
% d表示所求最短路的权和
% index1 表示标号顶点的顺序
% index2 表示标号顶点索引
% 起始点为第一个点
%参数初始化
M=max(max(a));
pb(1:length(a))=0;
pb(1)=1;
index1=1;
index2=ones(1:length(a));
d(1:length(a))=M;
d(1)=0;
temp=1;
%更新l（v），同时记录顶点顺序和顶点索引
while sum(pb)<length(a)
tb=find(pb==0); %第i次循环处理第i+1个顶点
d(tb)=min(d(tb),d(temp)+a(temp,tb)); %更新l（v）
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(1));
pb(temp)=1;
index1=[index1,temp]; %记录标号顺序
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index; %记录标号索引
end

下面这个用来求任意两点间的最短距离，还能算出路线。
function [P,u]=n2shorf(W,k1,k2)
%求任意两点最短路径算法
% P 为两点k1,k2间的最短路，顶点以经过次序进行排序
% u 为最短路的长度
% 初始化
n=length(W);
U=W;
m=1;
% 利用求最短路的Floyd算法，求最短路矩阵
while m<=n
for i=1:n
for j=1:n
if U(i,j)>U(i,m)+U(m,j)
U(i,j)=U(i,m)+U(m,j);
end
end
end
m=m+1;
end
u=U(k1,k2);%最短距离
% 求任意给定两个顶点见的最短路包含的顶点
P1=zeros(1,n);
k=1;
P1(k)=k2;
V=ones(1,n)*inf;
kk=k2;
while kk~=k1
for i=1:n
V(1,i)=U(k1,kk)-W(i,kk);
if V(1,i)==U(k1,i)
P1(k+1)=i;
kk=i;
k=k+1;
end
end
end
k=1;
wrow=find(P1~=0);
for j=length(wrow):(-1):1
P(k)=P1(wrow(j));
k=k+1;
end
end

⑥ 迪杰斯特拉算法 应用

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#defineTrue1
#defineFalse0
#definemax99


typedefstructjingdian{												//景点结构体
	charname[16];
	charnum;
}jingdian;

voidjdfz(structjingdianz[])											//景点赋值
{
	intn;

	strcpy(z[0].name,"图书馆");														//名字赋值
	strcpy(z[1].name,"行政楼");
	strcpy(z[2].name,"理学楼");
	strcpy(z[3].name,"电子信息实验楼");
	strcpy(z[4].name,"理科实验楼");
	strcpy(z[5].name,"计算机实验楼");
	strcpy(z[6].name,"工程实验楼");
	strcpy(z[7].name,"生化实验楼");
	strcpy(z[8].name,"体育场");
	strcpy(z[9].name,"宿舍区");
	strcpy(z[10].name,"文俊楼");
	strcpy(z[11].name,"文清楼");
	strcpy(z[12].name,"文新楼");
	strcpy(z[13].name,"文逸楼");
	strcpy(z[14].name,"演艺中心");

	for(n=0;n<15;n++){																//代号赋值
		z[n].num=n+1;
	}
}


voidljcx(charlinjie[15][15],jingdianz[])				//景点查询函数
{
	inta,b;																	//输入代号用
	intv;
	intl;																		//节点数
	intn,m;																	//循环用
	ints[20];																	//记录已被确定的最短路径长度
	intpath[20];																//记录出发到目的i当前最短路径上i的前驱节点
	intd[20];																	//记录当前的最短路径长度
	intmin;
	inttemp[20]={0};
	intt=0;
	intpre,i;

	printf("输入出发地,目的地代号,以空格隔开:");
	scanf("%d%d",&a,&b);
	//	printf("%d%d",a,b);														//测试是否获得ab
	if(a<1||a>15||b<1||b>15)printf("输入错误!");								//判断输入是否正确
	elseif(a==b)printf("你已在此处!");


	else{
		l=15;
		for(n=1;n<=l;n++){															//求最短路径
			s[n]=False;
			d[n]=linjie[a-1][n-1];
			if(d[n]<max)path[n]=a;
			elsepath[n]=-1;
		}		s[a]=1;																	//出发点路径定义
		d[a]=0;
		path[a]=-1;

		for(n=1;n<l;++n){
			v=-1;
			min=max;
			for(m=1;m<=l;m++){
				if(!s[m]&&d[m]<min){
					v=m;
					min=d[m];
				}
			}
			if(v==-1)break;
			s[v]=True;

			for(m=1;m<=l;m++){
				if(!s[m]&&(d[v]+linjie[v-1][m-1]<d[m])){								//有最短路径时更新前驱和长度
					d[m]=d[v]+linjie[v-1][m-1];
					path[m]=v;
				}

			}
		}


		printf("
最短路径：
");
		pre=path[b];

		for(n=1;n<=15;n++)
			printf("%d",path[n]);
		printf("
");

		while(pre!=-1){//路径倒序存入临时数组

			temp[t++]=pre;
			pre=path[pre];
		}

		//		printf("11");

		for(i=t-1;i>=0;i--){
			printf("%s—>",z[temp[i]-1].name);//倒序输出临时数组
		}
		printf("%s",z[b-1].name);
		printf("

");
	}//else尾
}


voidmain()										//主函数
{
	intn,m;														//循环用n，m
	chara;
	jingdianz[15];

	charlinjie[15][15];

	for(n=0;n<15;n++)													//邻接表
		for(m=0;m<15;m++){
			linjie[n][m]=max;
			if(n==m+1)linjie[n][m]=linjie[m][n]=1;
		}
	linjie[9][0]=linjie[0][9]=1;
	linjie[11][1]=linjie[1][11]=1;

	for(n=11;n<15;n++){
		linjie[n][10]=linjie[10][n]=1;
	}

	jdfz(z);															//名字代号赋值

	//	for(n=0;n<15;n++){															//名字代号赋值测试
	//		puts(z[n].name);
	//		printf("%d",z[n].num);
	//		printf("
");
	//	}
	//	for(n=0;n<15;n++){															//邻接表测试
	//		for(m=0;m<15;m++){
	//			printf("%d",linjie[n][m]);
	//		}
	//		printf("
");
	//	}


	printf("校园景点列表及其编号：

");
	printf("1图书馆2行政楼3理学楼4电子信息实验楼5理科实验楼
6计算机实验楼7工程实验楼8生化实验楼9体育场10宿舍区
11文俊楼12文清楼	13文新楼	14文逸楼	15演艺中心
");
	printf("===========================================================================");
	printf("
选择功能：
1.景点介绍2.路线查询3.退出系统

选择编号：");
	a=getchar();

	//		putchar(a);																//测试是否获得字符


	if(a=='1'){														//景点介绍

	}

	elseif(a=='2'){												//路径查询
		ljcx(linjie,z);
	}

	elseif(a=='3'){												//退出
		exit(0);
		//			printf("这个没显示就是结束了");										//是否结束了
	}

	elseprintf("输入代号错误，请重新输入:
");						//代号错误
}

⑦ Dijkstra算法

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。注意该算法要求图中不存在负权边。

设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度含侍仿。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

（1）初始时，S只包含起点D；U包含除D外的其他顶点，且U中顶点的距离为“起点D到该顶点的距离”（例如，U中顶点A的距离为[D,A]的长度，然后D和A不相邻，则谈枣A的距离为∞）
（2）从U中选出“距离最短的顶点K”，并将顶点K加入到S中；同时，从U中移除顶点K
（3）更新U中各个顶点到起点D的距离。之所以更新U中顶点的距离，是由于上一步谈纤中确定了K是求出最短路径的顶点，从而可以利用K来更新其他顶点到起点D的距离（例如，[D,A]的距离可能大于[D,K]+[K,A]的距离）
（4）重复步骤（2）和（3），直到遍历完所有顶点

https://blog.csdn.net/yalishadaa/article/details/55827681

⑧ 最短路径算法（Dijkstra）

Dijkstra（ 迪科斯特拉 ）算法是用来解决核激唯单源最短路径的算法，要求路径权值非负数。该算法利用了深度优先搜索和贪心的算法。

下面是一个有权图，求从A到各个节点的最短路径。

第1步：从A点出发，判断每个点到A点的路径（如果该点不能直连A点则距离值为无穷大，如果该点能和A直连则是当前的权值），计算完之后把A点上色，结果如下图:

第2步：从除A点之外的点查找到距离A点最近的点C，从C点出发查找其邻近的节点（除去已上色的点），并重新计算C点的邻近点距离A点的值，如图中B点，若新值（C点到A点的值+C点到该点的路径）小于原值，则将值更新为5，同理更新D、E点。同时将C标铅陵记为已经处理过，如图所示涂色。

第3步：从上色的节点中查找距离A最近的B点，重复第3步操作。

第4步： 重复第3步，改培2步，直到所有的节点都上色。

最后就算出了从A点到所有点的最短距离。

leetcode 743题