dijkstra.cpp

修改ＤＩＪＫＳＴＲＡ算法

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
const int n=10; 
#define max 32767

class Graph
{
public:
 int adj[n+1][n+1]; 
 int dist[n+1];   
 int father[n+1];   
 int s[n+1];   
 void shortest_path(Graph &t, const int V1);
};

void Graph::shortest_path(Graph &t, const int V1)
{
 for(int i=1; i<=n; i++)           //init the graph          
 {t.dist[i]=t.adj[V1][i];
 t.s[i]=0;                                  
 if((i!=V1)&&(t.dist[i]<max))
	 t.father[i]=V1;                
 else t.father[i]=0;
 }

 t.s[V1]=1; t.dist[V1]=0;                            
  for(i=1; i<n; i++)               //get the nearest node
 {
  int min=max; int u=V1;    
  for(int j=1; j<=n; j++)       
	  if(!t.s[j] && t.dist[j]<min)
	  {u=j,min=t.dist[j];}                     
   t.s[u]=1;          
   
  for(int w=1; w<=n;w++)           //upgrade the distances       
      if(!t.s[w]&&t.adj[u][w]<max && t.dist[u]+t.adj[u][w]<t.dist[w])
	  {t.dist[w]=t.dist[u]+t.adj[u][w]; t.father[w]=u;}
 }
 
 for(i=1; i<=n; i++)               //print 
 {
  if(i!=V1)
  {if(t.dist[i]!=max)
  {cout<<t.dist[i]<<":";
   cout<<i;}
   int pre=t.father[i];
   while(pre!=0)
   { cout<<"←"<<pre;
   pre=t.father[pre];
   }
   if(t.dist[i]!=max)
   cout<<endl;
  }
 }
}
int main(int argc, char* argv[])
{
 Graph t;
 int i,j,v;

 for( i=1; i<=n;i++)
 for(j=1; j<=n; j++)
 if(i==j)t.adj[i][j]=0;
 else t.adj[i][j]=max;
 
 ifstream inPutFile("graph.txt");
        int k=0;i=0; j=0;
		if(inPutFile){
			do{
				inPutFile>>i>>j;
				t.adj[i][j]=1;
				t.adj[j][i]=1;
				if(k<i) k=i;
				if(k<j) k=j;
			}
			while(!inPutFile.eof());
		}
		else{
			cerr<<"Open error\n";
		}
		cout<<"enter the source node:";
		cin>>v;
 t.shortest_path(t,v);
 
 return 0;
}