sshortp.txt

数据结构的c++实现,源代码全部在C++builder中运行.第六部分

//最短路径SShortP.cpp
//所有顶点之间的最短路径
#include<iostream.h>
#include<iomanip.h>
#include "graph0.cpp"
#include "PShortP.h"
template<class T>
void Make2DArray(int **&a,int row,int col)
//定义二维动态数组a,其行数为row,列数为col
{a=new T*[row];//a为指针数组,长度为row
 for(int i=0;i<row;i++)
  a[i]=new T[col];//每个指针指向一个一维数组,长度为col
}
void SShortPath(AdjMatrix &G,int **dist,int **path)
{int n=G.NumV();
 for(int i=0;i<n;i++)
  PShortPath(G,i,dist[i],path[i]);
}
//算法测试
void main()
{cout<<"SShortP.cpp运行结果:\n";
 int n=6,e=9,k2=1,i,j;
 RCW rcw[]={{0,2,5},{0,3,30},{1,0,2},{1,4,8},
  {2,1,15},{2,5,7},{4,3,4},{5,3,10},{5,4,18}};
 AdjMatrix g(n,k2);
 g.Creatgraph(n,e,rcw);
 
 int m=g.NumV();
 int **dist,**path;
 Make2DArray<int>(dist,m,m);
 Make2DArray<int>(path,m,m);
 SShortPath(g,dist,path);
 for(i=0;i<m;i++)
 {cout<<"从顶点"<<g.GetValue(i)
      <<"到其他各顶点的最短距离为:\n";
  for(j=0;j<m;j++)
   cout<<"到顶点"<<g.GetValue(j)
       <<"的最短距离为:"<<dist[i][j]<<endl;
   cout<<"从顶点"<<g.GetValue(i)
       <<"到其他各顶点的最短路径的前一顶点为:\n";
   for(j=0;j<m;j++)
    if(path[i][j]!=-1)
     cout<<"到顶点"<<g.GetValue(j)<<"的前一顶点为:"
         <<g.GetValue(path[i][j])<<endl;
 }
 cin.get();}
SShortP.cpp运行结果:
从顶点A到其他各顶点的最短距离为:
到顶点A的最短距离为:0
到顶点B的最短距离为:20
到顶点C的最短距离为:5
到顶点D的最短距离为:22
到顶点E的最短距离为:28
到顶点F的最短距离为:12
从顶点A到其他各顶点的最短路径的前一顶点为:
到顶点B的前一顶点为:C
到顶点C的前一顶点为:A
到顶点D的前一顶点为:F
到顶点E的前一顶点为:B
到顶点F的前一顶点为:C
从顶点B到其他各顶点的最短距离为:
到顶点A的最短距离为:2
到顶点B的最短距离为:0
到顶点C的最短距离为:7
到顶点D的最短距离为:12
到顶点E的最短路距离:8
到顶点F的最短距离为:14
从顶点B到其他各顶点的最短路径的前一顶点为:
到顶点A的前一顶点为:B
到顶点C的前一顶点为:A
到顶点D的前一顶点为:E
到顶点E的前一顶点为:B
到顶点F的前一顶点为:C
从顶点C到其他各顶点的最短距离为:
到顶点A的最短距离为:17
到顶点B的最短距离为:15
到顶点C的最短距离为:0
到顶点D的最短距离为:17
到顶点E的最短距离为:23
到顶点F的最短距离为:7
从顶点C到其他各顶点的最短路径的前一顶点为:
到顶点A的前一顶点为:B
到顶点B的前一顶点为:C
到顶点D的前一顶点为:F
到顶点E的前一顶点为:B
到顶点F的前一顶点为:C
从顶点D到其他各顶点的最短距离为:
到顶点A的最短距离为:99
到顶点B的最短距离为:99
到顶点C的最短距离为:99
到顶点D的最短距离为:0
到顶点E的最短距离为:99
到顶点F的最短距离为:99
从顶点D到其他各顶点的最短路径的前一顶点为:
从顶点E到其他各顶点的最短距离为:
到顶点A的最短距离为:99
到顶点B的最短距离为:99
到顶点C的最短距离为:99
到顶点D的最短距离为:4
到顶点E的最短距离为:0
到顶点F的最短距离为:99
从顶点E到其他各顶点的最短路径的前一顶点为:
到顶点D的前一顶点为:E
从顶点F到其他各顶点的最短距离为:
到顶点A的最短距离为:99
到顶点B的最短距离为:99
到顶点C的最短距离为:99
到顶点D的最短距离为:10
到顶点E的最短距离为:18
到顶点F的最短距离为:0
从顶点F到其他各顶点的最短路径的前一顶点为:
到顶点D的前一顶点为:F
到顶点E的前一顶点为:F