dijkstra.cpp

根据大连理工的《数据结构》课本自己写的Dijkstra算法,从文件读取顶点之间的路径数据,然后输出结果

#include <stdio.h>
#include <iostream.h>
#include <ctype.h>
int C[5][5],D[5],T[5],F[5];
int *current_T,temp,i,w,v,n,k,j,line,file,a=0;
FILE *fp;
/*
根据大连理工的《数据结构》课本自己写的Dijkstra算法		
我设置的是0，1，2，3，4这5个顶点
从文件读取顶点之间的路径数据
每一次筛选过后都会把最短路的输出结果显示一次
当时的目的是和书上的对比，因为测试的数据就是再书中找的题	
它列出了每次筛选后的数据，这样方便我调试。
最后的结果和书上的一模一样
*/


void main()
{
	if((fp=fopen("1.txt","r+"))!=NULL)
	{
		while(!feof(fp))
		{
			if(a==0)
			{
				fscanf(fp,"%d",&n);
				printf("%d\t",n);
				a=1;
				for(i=0;i<n;i++)
				{
					T[i]=20000;
					F[i]=20000;
				}
			}
			else
			{
				for(line=0;line<n;line++)
					for(file=0;file<n;file++)
					{
						fscanf(fp,"%d",&C[line][file]);
					}	
			}
		}
	}
	if(fp!=NULL)
		fclose(fp);

	current_T=T;
	T[0]=0;
	F[0]=1;
	F[1]=2;
	F[2]=3;
	F[3]=4;
	isalnum(T[0]);
	for(i=1;i<n;i++)
	{
		D[i]=C[0][i];
	}
	for(int r=0;r<n-1;r++)
	{
		temp=20000; 
	
		for(i=0;T[i]!=20000;i++)
		{
			for(j=0;F[j]!=20000;j++)
			{
				if(temp>C[T[i]][F[j]])
				{
					temp=C[T[i]][F[j]]; 
					w=F[j]; 
				}
			}
		}
		cout<<endl<<"w:"<<w<<endl;
		for(int e=1;e<n;e++)
		{
			cout<<"D["<<e<<"]:"<<D[e]<<" ";
		}
		current_T++;
		(*current_T)=w;
		while(F[k]!=20000) 
		{ 
			F[k]=F[k+1];
			k++;
		}

		for(j=0;F[j]!=20000;j++)
		{
			v=F[j];
			D[v]=D[v]<(D[w]+C[w][v])?D[v]:(D[w]+C[w][v]);
		}
		cout<<endl<<"－－－－－－－－－－－－－－－－－－－－－－"<<endl;
	}
	for(j=1;j<n;j++)
	{
		cout<<"源点0到点"<<j<<"的最短距离为:";
		cout<<"D["<<j<<"]="<<D[j]<<endl;
	}
	getchar();


}