test10_1.cpp

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

//  { test10_1 }
#include"graph2.h"
#include"grary2.h"
  const int  mmax=999;
  typedef  BB2   adjmatrix;

  datagraph g1;
  int n;
  adjmatrix  cost,a,path;


    void Graph_to_matrix(datagraph& g, BB2& a)
      {int i,j;

	 for (i=1;i<=nodes(g);i++)
	    for (j=1;j<=nodes(g);j++)
	     if (have_edge(g,i,j) )
	      a[i][j]=edge_weight(g,i,j) ;
	     else
	       a[i][j]=mmax;
	 for (i=1;i<=n;i++)
	    a[i][i]=0;
      }
    void  Init_path(BB2& a,BB2& path)
       {int  i,j;

	  for (i=1;i<=n;i++)
	    for (j=1;j<=n;j++)
	       if (a[i][j]<mmax )
			 path[i][j]=0;
	       else
		path[i][j]=-1;
       }


  void  floyd(datagraph& g,adjmatrix& A,adjmatrix& Path)
   {int i,j,k,x1,y1,x2,y2,len1;
    GrpArr2 ga,gpath;
    unsigned char ss[60];
    unsigned char st[8];
    display_graph("g",g);
    move_graph_to("g",g,10,50);
    Clear_range(0,0,getmaxx(),getmaxy());
    Graph_to_matrix(g,a);
    Init_path(A,path);
     create_grp_arrbb2(ga,A,"dist",1,n,1,n);
     create_grp_arrbb2(gpath,path,"Path",1,n,1,n);
    initial_GrpArr2(ga);
    initial_GrpArr2(gpath);
     display_graph("g",g);
     graph_range(g,x1,y1,x2,y2);
    move_GrpArr2_to(ga,30,y2+20);
    move_GrpArr2_to(gpath,getmaxx()/2,y2+20);
      for( k=1;k<=n;k++)
	for (i=1;i<=n;i++)
	  for (j=1;j<=n;j++)

       {
	 cur_cover2(ga,i,j,1);
	 len1=A[i][k]+A[k][j];
	 strcpy(ss, "the path ");
	 Convs(i,st);
	 strcat(ss,st);
	 strcat(ss,"==>");
	 strcpy(st,"");
	 Convs(j,st);
	 strcat(ss,st);
	 strcat(ss, " pass ");
	 strcpy(st,"");
	  Convs(k,st);
	 strcat(ss,st);

	 Statusline(ss);
	 Wait();
	 if ( (i!=j)&&(a[i][j]>len1) )
	   {
		unsigned char s1[20];
		strcpy(s1," pass ");
		Convs(k,st);
		strcat(s1,st);
		strcat(s1," is shorter");
		Dispstrinwnd(40,10, s1);
		put_elmn2(ga,i,j,len1);
		cur_cover2(ga,i,j,1);
		path[i][j]=k;
		display_GrpArr2_elmn2(gpath,i,j);
		cur_cover2(gpath,i,j,1);
	   }
	    cur_cover2(ga,i,j,1);
       }
       for (i=1;i<=n;i++)
	 for (j=1;j<=n;j++)
	   if (path[i][j]==0);
	    clear_GrpArr2_elmn2(gpath,i,j);
     }

    main()
    {   
	load_graph_file(g,"graphs\\floyd.grp");
	n=g.nodes;
	 floyd(g,a,path);
   }