迪杰斯特拉Dijkstra算法 图论最短路径问题

//在Dijkstra算法里,为了求源点v0到其他各个顶点vi的最短路径及其长度,需要设置三个数组

//dist[n]: dist[i]表示当前找到的从源点v0到终点vi 的最短路径长度,初始化时,dist[i]=Edge[v0][i],即邻接矩阵的第v0行

//S[n]: S[i]为0表示顶点vi 还未加入到集合S中,S[i]为1表示vi已经加入到集合S中,初始化时,S[v0]为1,其余为0,表示最初集合S中只有顶点v0

//path[n]: path[i]表示v0到vi的最短路径上顶点vi的前一个顶点序号,采用”倒向追踪”的方法,可以确定v0到顶点vi的最短路径上的每个顶点

//在Dijkstra算法里,重复做以下步骤:

//(1)在数组dist[n]里查找S[i]!=1,并且dist[i]最小的顶点u

//(2)将S[u]改为1,表示顶点u已经加入进来了.

//修改集合中每个顶点vk的dist以及path数组元素值: 当S[k]!=1,顶点u到顶点k有边(Edge[u][k]QQ截图20141128103334
程序运行结果:
QQ截图20141128103636
源代码如下:

#include<iostream>
using namespace std;

#define INF 10000
#define MAXN 20
int n;//顶点个数
int Edge[MAXN][MAXN];
int S[MAXN];
int dist[MAXN];
int path[MAXN];
void Dijkstra(int v0)
{
	int i,j,k;
	for(i=0;i<n;i++)
	{
		dist[i]=Edge[v0][i];
		S[i]=0;
		if(i!=v0&&dist[i]<INF)
			path[i]=v0;
		else
			path[i]=-1;
	}
	S[v0]=1;dist[v0]=0;
	for(i=0;i<n-1;i++)
	{
		int min=INF,u=v0;
		for(j=0;j<n;j++)
		{
			if(!S[j]&&dist[j]<min)
			{
				u=j;min=dist[j];
			}
		}
		S[u]=1;
		for(k=0;k<n;k++)
		{
			if(!S[k]&&Edge[u][k]<INF&&dist[u]+Edge[u][k]<dist[k])
			{
				dist[k]=dist[u]+Edge[u][k];path[k]=u;
			}
		}
	}
}


int main()
{
	int i,j;
	int u,v,w;
	printf("输入顶点个数:\n");
	scanf("%d",&n);//n个顶点
	printf("输入每条边的信息,当输入-1 -1 -1结束:\n");
	while(1)
	{
		scanf("%d%d%d",&u,&v,&w);
		if(u==-1&&v==-1&&w==-1)
			break;
		Edge[u][v]=w;
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(i==j)
				Edge[i][j]=0;
			else if(Edge[i][j]==0)
				Edge[i][j]=INF;
		}
	}
	Dijkstra(0);
	int shortest[MAXN];
	for(i=1;i<n;i++)
	{
		printf("%d\t",dist[i]);
		memset(shortest,0,sizeof(shortest));
		int k=0;
		shortest[k]=i;
		while(path[shortest[k]]!=0)
		{
			k++;
			shortest[k]=path[shortest[k-1]];
		}
		k++;
		shortest[k]=0;
		for(j=k;j>0;j--)
			printf("%d->",shortest[j]);
		printf("%d\n",shortest[0]);
	}
	return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注