dijkstra.cpp

C++的电子教程

//程序实例8_6
//Dijkstra算法求最短路径
#include<stdio.h>
#define Max 100
#define I 32767

void print_path(int dist[],int path[],int s[],int n,int v0)
{
	int i,k;
	for(i=1;i<=n;i++)
		if(s[i]==1)
		{
			k=i;
			printf("%d到%d的最短路径为：",v0,i);
			while (k!=v0)
			{
				printf("%d<-",k);
				k=path[k];
			}
			printf("%d",k);
			printf("\n路径长度为:  %d\n",dist[i]);
			printf("\n");
		}
		else
			printf("%d<-%d  路径不存在!",i,v0);
}

void shortest(int cost[][7],int dist[],int path[],int n,int v0)	
//cost[][]为带权邻接矩阵
//dist[i]为从源点v到终点vi的最短路径长度
//path[i]为从源点v到终点vi的最短路径中的前一个顶点的编号
{
	int s[Max],i,j,k,min;
	for(i=1;i<=n;i++)    //初始化
	{	dist[i]=cost[v0-1][i-1];
		s[i]=0;          //0表示顶点不在S集合中，1则相反
		if(cost[v0-1][i-1]<I)	path[i]=v0;
		else		path[i]=0;
	}
	s[v0]=1;path[v0]=0;     //源点v0放入S中
	for(i=1;i<=n;i++)       //对所有的n个顶点
	{	min=I;	k=0;
		for(j=1;j<=n;j++)   //选取不在S中且具有最小距离的顶点k
			if(s[j]==0)
				if(dist[j]!=0 && dist[j]<min)
				{	min=dist[j];	k=j;	}
		s[k]=1;               //把顶点k加入S中
		for(j=1;j<=n;j++)     //修改不在S中的顶点的距离
			if(s[j]==0)
		    if(cost[k-1][j-1]<I && dist[k]+cost[k-1][j-1]<dist[j])
				{	dist[j]=dist[k]+cost[k-1][j-1];
					path[j]=k;
				}
	}
	print_path(dist,path,s,n,v0);
}

void main()
{	int cost[][7]={{0,15,I,4,I,I,I},	{I,0,I,I,2,I,8},
					{9,I,0,I,I,I,I},	{I,5,I,0,I,6,I},
					{I,I,I,I,0,I,3},	{I,I,12,I,I,0,16},
					{I,I,I,11,I,I,0}};
	int dist[Max], path[Max],n,v0;
	n=7; 	v0=1;
	shortest(cost,dist,path,n,v0);
}