dijkstra.cpp

用c语言编写的Dijkstra算法的源代码。代码短小精炼有注释

#include<stdio.h>
#include<iostream.h>
#define MAXINT 999
void main()
{
	int a,n;
	int c[100][100];//c[i][j]表示边(i,j)的权 （1=< i <=n）
	int dist[100]; //dist[i]表示当前从源点到顶点i的最短路径长度
	int s[100];//顶点集合
	int prev[100];//prev[i]表示当前从源点到顶点i的最短路径上i的前一个节点
	int v=1;//源点为v1
	FILE* fp=fopen("test.txt","r");
    ///////读取权矩阵
	for(int i=1,j=0;fscanf(fp,"%d",&a)>0;j++){//i表示行，j表示列
		if(j==0)
			n=a;//第一个数为顶点的个数
		
		if(j!=0)
			c[i][j]=a; 
		if(j==n){
			i++;//下一行
			j=0;
		}
	}
	for(i=1;i<=n;i++){ //打印矩阵
		for(j=1;j<=n;j++){
			if(c[i][j]==MAXINT)
				printf("*\t");
			else printf("%d\t",c[i][j]);
		}
		printf("\n");
	}
	/////////////////////////////////////////////////////////////////
	//////////////Dijkstra 算法//////////////////////////
	//初始化
	for(i=1;i<=n;i++){
		dist[i]=c[v][i];
		s[i]=false;
		if(dist[i]==MAXINT) 
			prev[i]=0;
		else
			prev[i]=v;//从源点到i顶点有路径，则i节点的前一个节点为v（源点）
			
	}
	dist[v]=0;
	s[v]=true;//把v放入顶点集
	
	for(i=1;i<=n;i++){
		int temp=MAXINT;
		int u=v;
		for(j=1;j<=n;j++)
			if((!s[j]) && (dist[j]<temp)){
				u=j;
				temp = dist[j]; //temp记录最小的路径长度
			}//if
		s[u] = true;//把u放入顶点集
		for(j=1;j<=n;j++)
			if((!s[j]) && (c[u][j]<MAXINT)){//截枝
				int newdist = dist[u] + c[u][j];

				if(newdist < dist[j]){ //更新路径长度
					dist[j] = newdist;
					prev[j] = u;
				}//if
			}//if
	}//for
	printf("\n");
    /////打印路径////
	for(i=1;i<=n;i++){
		printf("v%d: ",i);
		if(prev[i]!=0){
			int u=i;
			while(u!=v){//往回找到源点的路径
				printf("%d<-",u);
				u=prev[u];
				if(u==0)
					break;
			}
			printf("%d",u);
			if(dist[i]==MAXINT)
				printf("\t\tshortest distance= * ");
			else
				printf("\t\tshortest distance=%d\n",dist[i]); //从源点可到达的点的最短路径
		}//if
		else if(i==v)
			printf("%d\t\t shortest distance=%d\n",v,dist[i]); //源点
		else printf("Unaccessible\t\t shortest distance=*\n"); //从源点不可到达的点

	}

	/////////////////////////////////////////////////////////////////////////////

}//main