floyd算法.doc

#include <iostream>
#include <iomanip>
using namespace std;
#define  MAXV  100
#define  INF  32767
typedef int InfoType;
typedef int Vertex;
typedef struct
{       int no;               
     InfoType info;             
} VertexType;               //顶点类型
typedef struct                         
{       int edges[MAXV][MAXV];
     int n,e;              
     VertexType vexs[MAXV];
} MGraph;                           //图类型
void Ppath(int path[][MAXV], int i, int j)
{     int k;
      k=path[i][j];
      if (k==-1)  return;               //递归出口
      Ppath(path,i,k);                
      cout<<k<< "  ";            //输出k           
      Ppath(path,k,j);                
}
void Dispath(int A[][MAXV],int path[][MAXV],int n)
{   int i,j;
    for (i=0;i<n;i++)
   for (j=0;j<n;j++)
      if (A[i][j]==INF)
    {   if(i!=j) cout<< "从" <<i<< "到"
                     <<j<< "不存在路径\n";
    }
    else
    {      cout<< "从" <<i<< " 到" <<j
                          << " 的路径为: "<< i <<" ";
            Ppath(path, i, j);   
                  cout<<j;
                               cout<< " \t\t 路径长度为:"<<A[i][j]
                                      <<endl;
    }
}
void Floyd(MGraph g)
{     int A[MAXV][MAXV],path[MAXV][MAXV];
      int i,j,k;
      for (i=0;i<g.n;i++)
  for (j=0;j<g.n;j++)
          { 
   A[i][j]=g.edges[i][j];
   path[i][j]=-1;
  }
      for (k=0;k<g.n;k++)
  for (i=0;i<g.n;i++)
          for (j=0;j<g.n;j++)
    if (A[i][j]>(A[i][k]+A[k][j]))
                   {
     A[i][j]=A[i][k]+A[k][j];
     path[i][j]=k; 
    }
 Dispath(A,path,g.n);                           //输出最短路径
  }
void DispMat(MGraph g)
{
 int i,j;
 for(i=0;i<g.n;i++)
 {
  for(j=0;j<g.n;j++)
   if(g.edges[i][j]==INF)
    cout <<setw(3)<<" ∞";
   else cout<<setw(3)<<g.edges[i][j];
  cout<<endl;
 }
}
void Floyd(MGraph g);
void Ppath(int path[][MAXV], int i, int j) ;
void Dispath(int A[][MAXV],int path[][MAXV],int n);
void DispMat(MGraph g);
void main()
{
 int i,j;
 MGraph g;
 cout<<"输入邻接矩阵g总顶点数g.n和总边数g.e：";
 cin>>g.n>>g.e;
 cout<<"输入邻接矩阵g的元素值：\n";
 for(i=0;i<g.n;i++)
 {
  cout<<"第"<<i<<"行：";
  for(j=0;j<g.n;j++)
   cin>>g.edges[i][j];
 }
 cout<<"输出邻接矩阵g：\n";
 DispMat(g);
 cout<<"输出每对顶点之间的最短路径：\n";
 Floyd(g);
 cout<<endl;
}