迪杰斯特拉算法

① 迪杰斯特拉算法怎么算

Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。.

② dijkstra算法有哪些

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

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

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

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

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

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

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

③ 解释一下dijkstra算法这个计算过程的意思 怎么算的

最近也看到这个算法，不过主要是通过C语言介绍的，不太一样，但基本思想差不多。下面只是我个人的看法不一定准确。
Dijkstra算法主要解决指定某点(源点)到其他顶点的最短路径问题。
基本思想：每次找到离源点最近的顶点，然后以该顶点为中心(过渡顶点)，最终找到源点到其余顶点的最短路。

t=1：令源点(v_0)的标号为永久标号(0,λ)(右上角加点), 其他为临时(+无穷,λ). 就是说v_0到v_0的距离是0，其他顶点到v_0的距离为+无穷。t=1时，例5.3上面的步骤(2)(3)并不能体现

t=2：第1步v_0(k=0)获得永久标号，记L_j为顶点标号当前的最短距离(比如v_0标号(0,λ)中L_0=0), 边(v_k,v_j)的权w_kj. 步骤(2)最关键，若v_0与v_j之间存在边，则比较L_k+w_kj与L_j, 而L_k+w_kj=L_0+w_0j<L_j=+无穷。
这里只有v_1,v_2与v_0存在边，所以当j=1,2时修改标号, 标号分别为(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不变。步骤(3)比较所有临时标号中L_j最小的顶点, 这里L_1=1最小，v_1获得永久标号(右上角加点)。

t=3: 第2步中v_1获得永久标号(k=1), 同第2步一样，通过例5.3上面的步骤(2)(3)，得到永久标号。 步骤(2),若v_1与v_j(j=2,3,4,5(除去获得永久标号的顶点))之间存在边，则比较L_1+w_1j与L_j。这里v_1与v_2，v_3，v_,4存在边，
对于v_2, L_1+w_12=1+2=3<L_2=4, 把v_2标号修改为(L_1+w_12, v_1)=(3, v_1);
对于v_3, L_1+w_13=1+7=8<L_3=+无穷, 把v_3标号修改为(L_1+w_13, v_1)=(8, v_1);
对于v_4, L_1+w_14=1+5=6<L_4=+无穷, 把v_4标号修改为(L_1+w_14, v_1)=(6, v_1);
v_5与v_1不存在边，标号不变。步骤(3), 找这些标号L_j最小的顶点，这里v_2标号最小

t=4: k=2, 与v_2存在边的未获得永久标号的顶点只有v_4, 比较L_2+w_24=3+1=4<L_4=6, 把v_4标号修改为(L_2+w_24, v_2)=(4, v_2); 其他不变。步骤(3), L_4=4最小。

t=5: k=4, 同理先找v_4邻接顶点，比较，修改标号，找L_j最小
t=6: 同理

啰嗦的这么多，其实步骤(2)是关键，就是通过比较更新最短路径，右上角标点的就是距离源点最近的顶点，之后每一步就添加一个新的”源点”，再找其他顶点与它的最短距离。

迪杰斯特拉算法(Dijkstra)(网络)：
http://ke..com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_josbPNcGKtLYJ5GJsJT6U28koc_#4
里面有个动图，更形象地说明了该算法的过程。(其中每次标注的一个红色顶点out就和你的这本书中获得永久标号是相似的)

④ 迪杰斯特拉算法的原理

1.首先，引入一个辅助向量D，它的每个分量 D 表示当前所找到的从起始点 （即源点 ）到其它每个顶点 的长度。
例如，D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。
2.D的初始状态为：若从 到 有弧（即从 到 存在连接边），则D 为弧上的权值（即为从 到 的边的权值）；否则置D 为∞。
显然，长度为 D = Min{ D | ∈V } 的路径就是从 出发到顶点 的长度最短的一条路径，此路径为( )。
3.那么，下一条长度次短的是哪一条呢？也就是找到从源点 到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点 到顶点 的最短路径长度。
假设该次短路径的终点是 ，则可想而知，这条路径要么是( )，或者是( )。它的长度或者是从 到 的弧上的权值，或者是D 加上从 到 的弧上的权值。
4.一般情况下，假设S为已求得的从源点 出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为 ）要么是弧( )，或者是从源点 出发的中间只经过S中的顶点而最后到达顶点 的路径。
因此，下一条长度次短的的最短路径长度必是D = Min{ D | ∈V-S }，其中D 要么是弧( )上的权值，或者是D ( ∈S)和弧( , )上的权值之和。
算法描述如下：
1）令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从 出发的的终点的集合，初始状态为空集。那么，从 出发到图上其余各顶点 可能达到的长度的初值为D=arcs[Locate Vex(G, )]， ∈V；
2）选择 ，使得D =Min{ D | ∈V-S } ；
3）修改从 出发的到集合V-S中任一顶点 的最短路径长度。

⑤ dijkstra算法

楼上正解，你找个图自己用此算法实践一下就知道了，从A点出发，发现离A最近的点是B点，那么我们就已经认为A到B的最短距离就是AB了，如果有负数，就指不定冒出个C点,AC+CB<AB;或者冒出个DE为很大的负值，AC+CD+DE+EF+FB<AB;等等诸如此类的情况。
简单说来，你驾车从家出发到某地沿某条路只需经过一个收费站，但是远在外省某地有个站不但不收你的费，你去了还会给你个千八百万的欢迎光临费，你能说你直接沿着这条路去某地是最省费用的？不计时间成本，绕到外省那个给你钱的地方，再绕回到你的目的地，还能赚钱呢。
而且一般权值为负的图研究也比较少。有些带负权的图，某些点间还没有最小距离呢。中间出个带某条负权很大的边的环圈，绕此一圈所经过的距离反而减少了，那就一直在此圈上绕啊绕啊绕到负的足够大溢出为止。
当然考虑各种自己随便假设出来的变种问题也是很有趣的。比如说边带有多个权值对应多次经过改变的消费，上面的问题有可能变成有解的。话说那个站会后悔，第二次经过它会收回100万，第三次经过收回250万，这样的话你只需要经过一次就够了，问题也是有解的。再比如说对于多权重图，从A点出发经过B点到达C点的最短路线，就不是简单的AB最短路线+BC最短路线了，说不定两者有重合边，第二次经过来个天价就傻眼了。其实这种图貌似应该可以转化成单权重图的，我直觉估计啊，刚随便想出这个问题，还没去思考这个问题的解^_^

⑥ 迪杰斯特拉算法 应用

#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("输入代号错误，请重新输入:
");						//代号错误
}

⑦ 迪杰斯特拉算法

按路径长度递增次序产生最短路径算法：
把V分成两组： （1）S：已求出最短路径的顶点的集合
（2）V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，
保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 （反证法可证） 求最短路径步骤 … 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值 ƒ 若存在<V0,Vi>，为<V0,Vi>弧上的权值 ƒ 若不存在<V0,Vi>，为∝ … 从T中选取一个其距离值为最小的顶点W，加入S … 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的 距离值比不加W的路径要短，则修改此距离值 … 重复上述步骤，直到S中包含所有顶点，即S=V为止

⑧ 迪杰斯特拉算法的算法实现

· 算法思想
设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。
设下一条最短路径终点为Vj ，则Vj只有：
◆ 源点到终点有直接的弧<Vs，Vj>；
◆ 从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。
若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：
dist[i]=Min{ dist[k]| Vk∈V-S }
利用上述公式就可以依次找出下一条最短路径。
· 示例程序
· 算法思想
var a:array[1..100,1..100]of integer;//邻接矩阵
flag:array[1..100] of boolean;//已经找到最短路径的节点标志
path:array[1..100]of integer;
w,x,n,i,j,min,minn,k:integer;
begin
readln(n,k);for i:=1 to n do//读取邻接矩阵,无路径写-1
begin
for j:=1 to n do
begin
read(a[i,j]);
If a[i,j]=-1 then a[I,j]:=maxint;
end;
readln;
end;
fillchar(flag,sizeof(flag),false);//标明所有节点都未找到最短路径
flag[k]:=true; //源节点除外
fillword(path,sizeof(path) div 2,k);
path[k]:=0;
minn:=k;//标记最小的点for x:=2 to n do
begin
min:=32767;//标记要找下一个最短路径点的距离
for i:=1 to n do//找下一点点
if (a[k,i]<min) and (flag[i]=false) then
begin
min:=a[k,i];
minn:=i;
end;
flag[minn]:=true;//标记下一个点的找到
for j:=1 to n do //更新最短路径
if (j<>minn) and (a[k,minn]+a[minn,j]<a[k,j]) and (flag[j]=false) then
begin
a[k,j]:=a[k,minn]+a[minn,j];
path[j]:=minn;
end;
end;
for i:=1 to n do write(a[k,i],' ');//输出源点到各个点的距离
writeln;
for i:=1 to n do write(path[i],' ');//输出源点到各个点的距离
end.
求采纳（空格被网络吃了……）

⑨ 迪杰斯特拉算法的定义

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

⑩ dijkstra算法是什么

迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。

算法把一个图（G）中的点划分成了若干部分：

1）：原点（v）；

2）：所有周边点（C）；

另外有一个辅助集合S，从v到S中的点的最短路径已经求得。S的最初状态是空集。

这样就可以进一步划分图（G）：

1）：原点（v）；

2）：已求出v至其最短路径的周边点（S）；

3）：尚未求出v至其最短路径的周边点（Other=C-S）；

算法的主体思想：

A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）；

B、找到v——S——Other所有路径中的的最短路径vi=v——i（Other的一个元素）；

C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。

重复以上步骤直至Other为空集。

我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v——