dijkstra.cpp

数据结构常用算法之一-Dijkstra算法,实现最短路径选择.

#include"iostream.h"
#include"fstream.h"
#include"stdlib.h"
#define N 9
#define M 1000
void dg(int i,int path[])
	{

		if(i<N)
		{   
			cout<< path[i]<<"->"<<i<<"  "<<endl;
			i++;
		
			dg(i,path);
		}
}
void main()
{
	int a[N][N],mark[N],path[N],dist[N];
	int i,j;
	int b=0;
	int l=1,k;
	int w;
	int min;
	int c;
	ifstream fin;
	char file[32];
	cout<<"输入要打开的文件：\n"<<endl;
    cin>>file;
	fin.open(file,ios::in|ios::nocreate);
	if(!fin)
	{cerr<<"can't open";
	 exit(1);
	}
	for(i=0;i<N;i++)
	{	for(j=0;j<N;j++)
		{	fin>>a[i][j];cout<<a[i][j]<<" ";}
	cout<<endl;
	}
	fin.close();
		for(i=0;i<N;i++)
			mark[i]=0;
		for(i=1;i<N;i++)
			dist[i]=a[1][i];
		mark[0]=1;
		mark[1]=1;
		path[1]=0;
for(k=2;k<N;k++)
{   
	j=l;
	for(i=1;i<N;i++)
	{   
		if(dist[i]>b+a[j][i]&&mark[i]==0)
	    	dist[i]=b+a[j][i];
		if(dist[i]<b+a[j][i]&&mark[i]==0)
			dist[i]=dist[i];
		if(mark[i]==1)
			dist[i]=M;
          
	}
	if(j==2)
	for(i=1;i<N;i++)
	cout<<"**"<<dist[i];
	cout<<endl;
	min=dist[1];
	for(i=2;i<N;i++)
		if(dist[i]<min)
			min=dist[i];
		b=min;
	for(i=1;i<N;i++)
	{	if(dist[i]==min)
	break;}
		mark[i]=1;
		path[i]=l;
		l=i;
}
   /*得path数组*/
	for(j=0;j<N;j++)
		cout<<"##"<<j<<","<<path[j]<<" ";//
	i=0;
	dg(i,path);

}