傻子也能看懂的迪杰斯特拉算法

① 迪杰斯特拉（dijkstra）详细介绍

Dijkstra 迪杰斯特拉算法

//求单源点最短路径
#include "stdafx.h"
#include <iostream.h>const int n=5; //图中定点个数
const int e=9; //图中边的个数#define max 32767class Graph
{
public:
int arcs[n+1][n+1]; //图的邻接矩阵
int dist[n+1]; //存放源点到个顶点的最短路径
int path[n+1]; //存放在最短路径上该顶点的前一顶点号
int s[n+1]; //已求得的在最短路径上的顶点的顶点号
void shortest_path(Graph &t, const int V1);
};void Graph::shortest_path(Graph &t, const int V1)
{
for(int i=1; i<=n; i++)
{t.dist[i]=t.arcs[V1][i];
t.s[i]=0;
if((i!=V1)&&(t.dist[i]<max))t.path[i]=V1;
else t.path[i]=0;
}
t.s[V1]=1; t.dist[V1]=0;
for(i=1; i<n; i++)
{
int min=max; int u=V1;
for(int j=1; j<=n; j++)
if(!t.s[j]&&t.dist[j]<min){u=j,min=t.dist[j];}
t.s[u]=1;
for(int w=1; w<=n;w++)
if(!t.s[w]&&t.arcs[u][w]<max&&t.dist[u]+t.arcs[u][w]<t.dist[w]){t.dist[w]=t.dist[u]+t.arcs[u][w]; t.path[w]=u;}
}

for(i=1; i<=n; i++)
{
if(i!=V1)
{
cout<<t.dist[i]<<":";
cout<<i;
int pre=t.path[i];
while(pre!=0)
{ cout<<"←"<<pre;
pre=t.path[pre];
}
cout<<endl;
}
}
}int main(int argc, char* argv[])
{
Graph t;
int i,j,w;
for( i=1; i<=n;i++)
for(j=1; j<=n; j++)
if(i==j)t.arcs[i][j]=0;
else t.arcs[i][j]=max;
for(int k=1; k<=e; k++)
{
cin>>i>>j>>w;
t.arcs[i][j]=w;
}
t.shortest_path(t,1);
return 0;

② 迪杰斯特拉算法

按路径长度递增次序产生最短路径算法： 把V分成两组： （8）S：已求出最短路径的顶点的集合 （8）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中， 保证

③ 用dijkstra算法计算源点到个结点的最短路径....谢谢亲爱的朋友~ 详细答案

(这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值)
1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边) 2． 在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3
3． 对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i), d(j)+Wj->i}，转2

④ 用堆来实现计算单源最短路的迪杰斯特拉(Djisktra)算法

//最近刚写了这个程序，希望对你有帮助

#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>

#define MAXNODE 30 //定义最大节点数
#define MAXCOST 1000 //如果两点间无路劲，则设MAXCOST
int dist[MAXNODE],cost[MAXNODE][MAXNODE],n=6; //为实际节点数

//dijkstra算法求单源最短路径，这个函数就没加注释了，需要自己理解。

void dijkstra(int v0) //v0为起始节点
{
int s[MAXNODE];
int mindis,dis,i,j,u;
for(i=1;i<=n;i++)
{
dist[i]=cost[v0][i];
s[i]=0;
}
s[v0]=1;
for(i=1;i<=n;i++)
{
mindis=MAXCOST;
for(j=1;j<=n;j++)
{
if(s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
s[u]=1;
for(j=1;j<=n;j++)
if(s[j]==0)
{
dis=dist[u]+cost[u][j];
dist[j]=(dist[j]<dis)?dist[j]:dis;
}
}

}

//自定义display_path函数，输出各顶点最短路径
void display_path(int v0)
{
int i;
printf("\n顶点 %d 到各顶点的最短路径长度如下:\n",v0);
for(i=1;i<=n;i++)
{
printf(" (v%d->v%d):",v0,i);
if(dist[i]==MAXCOST)
printf("无路径");
else
printf("%d\n",dist[i]);
}
}
//主函数中各个定点的cost值可以根据实际路劲修改
void main()
{
int i,j,v0=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=((i==j)?0:MAXCOST);
cost[1][2]=10;
cost[1][4]=30;
cost[1][5]=100;
cost[1][6]=20;
cost[2][3]=50;
cost[3][5]=10;
cost[4][3]=20;
cost[4][5]=60;
cost[5][6]=30;
dijkstra(v0);
display_path(v0);

}

⑤ 迪杰斯特拉算法的算法思想

按路径长度递增次序产生算法：
把顶点集合V分成两组：
（1）S：已求出的顶点的集合（初始时只含有源点V0）
（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的路径权值之和
（反证法可证）
求最短路径步骤
算法步骤如下：
G={V,E}
1. 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值
若不存在<V0,Vi>，d(V0,Vi)为∞
2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

⑥ 迪杰斯特拉算法的原理

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算法这个计算过程的意思 怎么算的

最近也看到这个算法，不过主要是通过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就和你的这本书中获得永久标号是相似的)

⑧ 迪杰斯特拉算法 应用

#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 在哪里用

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径,该算法按照最短路径长度递增的顺序产生所以最短路径.
对于图G=（V,E）,将图中的顶点分成两组：
第一组S：已求出的最短路径的终点集合（开始为{v0}）.
第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）.
算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中,直到所有顶点都被加入到第一组顶点集S为止.
【算法思想】
g为用邻接矩阵表示的带权图.
（1）S

⑩ 迪杰斯特拉算法

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