key102b.cpp

该包是数据结构的实验软件,来源于合肥工业大学人工智能与数据挖掘实验室,用来实现数据结构.

//{ test10_2 }
#include"graph2.h"
#include"grary1.h"
const int MMax=999;
set u;



   void   Init_dist_path(datagraph& g,bb1& dist,bb1& path,int v0)
    {int i;

	 for (i=1;i<=nodes(g);i++)
	    if (have_edge(g,v0,i) )
		 {
		  dist[i]=edge_weight(g,v0,i);//_______________________{Blank 1};
		  path[i]=v0;
		  }
	    else
		  { dist[i]=MMax;
		    path[i]=0;
		    }
	 dist[v0]=0;
      }

  int  Nearest_Vertex(datagraph& g,GrpArr& gdist)
    {
    int  MMin=0,j=0,k=0;
	 MMin=MMax;
	    for (j=1;j<=nodes(g);j++)
	       if (!u.contain(j)&&( elmn(gdist,j)<MMin) ) //_________________________{Blank 2}
		  {
		   k=j;
		   MMin=elmn(gdist,j);
		   }
       int	    Nearest_Vertex=k;
       return  Nearest_Vertex;
     }

  void   change_dist_path_with(datagraph& g,bb1& dist,bb1& path,GrpArr& gdist,GrpArr& gpath,int k)
    {int j;

	  for (j=1;j<=nodes(g);j++)
	     if(!u.contain(j)&&have_edge(g,k,j)&&(dist[j]>dist[k]+edge_weight(g,k,j) ) )
		 //_________________________________{Blank 3}
	     {
			  dist[j]=dist[k]+edge_weight(g,k,j);
			  path[j]=k;
			  display_GrpArr_elmn(gdist,j);
			  display_GrpArr_elmn(gpath,j);
	      }
    }


     void  one_path_to(bb1& path,int v)
	{ if ( path[v]!=0 )
	       one_path_to(path,path[v]);
	   cout<<v;
	}

     void  all_path_from(datagraph& g,bb1& path,int k)
      {int i;

	window(1,1,80,nodes(g));
	for (i=1;i<=nodes(g);i++)
	      {
		one_path_to(path,i);
		cout<<endl;
		Wait();
	     }
     }

  void   dijkstra(datagraph& g,datagraph& gtree,int  v0)
  {//   var u:set of 1..50;
      u.insert(v0);


     int     i,j,k,x1,y1,x2,y2;
     bb1   dist,path;

     GrpArr gdist,gpath;
     display_graph("graph",g);
     Clear_range(0,0,getmaxx(),getmaxy() );
     move_graph_to("graph",g,10,50);
    copy_all_vertex(g,gtree,getmaxx()/2,0);
     num=nodes(g);
     create_grp_Arrbb(gdist,horizon,1,true,dist,"dist",1,num);
     create_grp_Arrbb(gpath,horizon,1,true,path,"path",1,nodes(g));
     initial_GrpArr(gdist);
     initial_GrpArr(gpath);
    graph_range(g,x1,y1,x2,y2);
    move_GrpArr_mid(gdist,getmaxx()/2,y2+50);
    move_GrpArr_mid(gpath,getmaxx()/2,y2+120);
    disp_graph("graph",g);
    disp_graph("gtree",gtree);
    dispint_atgnode_angle(0,gtree,v0,90);
    Init_dist_path(g,dist,path,v0);
    display_GrpArr(gdist);
    display_GrpArr(gpath);
    for (i=1;i<=nodes(g)-1;i++)
       { Wait();
	 k=Nearest_Vertex(g,gdist);
	 u.insert(k);
	  dispint_atgnode_angle(dist[k],gtree,k,90);
	  cur_elmn_onoff(gdist,k);
	  cur_elmn_onoff(gpath,k);
	  copy_edge(g, path[k],k,gtree);
	  display_edge(gtree, path[k],k);
	  change_dist_path_with(g,dist,path,gdist,gpath,k);
	}
    all_path_from(g,path,v0);
   }

  void main()
   { datagraph g,gtree;
     load_graph_file(g,"graphs\\dijkstra.grp");
     dijkstra(g,gtree,1);
     getch();
    }