//最短路徑(弗洛伊德算法)FloydP.h
//所有頂點之間的最短路徑
void Floyd(AdjMatrix &G,int dist[6][6],int path[6][6])
//求圖G中每對頂點之間的最短距離dist和最短路徑的頂點序號path
{int i,j,k;
 int n=G.NumV();
 for(i=0;i<n;i++)//初始化
  for(j=0;j<n;j++)
  {dist[i][j]=G.GetWeight(i,j);
   if(i!=j&&dist[i][j]!=MaxValue) path[i][j]=i;
   else
    if(i==j) path[i][j]=0;
    else path[i][j]=-1;
  }
  for(k=0;k<n;k++)
   for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    {if(dist[i][j]>(dist[i][k]+dist[k][j]))
      {dist[i][j]=dist[i][k]+dist[k][j];
       path[i][j]=path[k][j];
}}}
//最短路徑FloydP.cpp
#include<iostream.h>
#include<iomanip.h>
#include "graph0.cpp"
#include "FloydP.h"
//弗洛伊德算法測試
void main()
{cout<<"FloydP.cpp運行結果:\n";
 int i,j,e=9,n=6,k2=1;
 RCW rcw[9]={{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.CreateMatrix(n,1,k2,rcw);
 g.Creatgraph(n,e,rcw);
 int dist[6][6];
 int path[6][6];
 Floyd(g,dist,path);
 for(i=0;i<n;i++)
 {cout<<"從頂點"<<g.GetValue(i)
      <<"到其他各頂點的最短距離為:\n";
  for(j=0;j<n;j++)
   cout<<"到頂點"<<g.GetValue(j)
       <<"的最短距離為:"<<dist[i][j]<<endl;
   cout<<"從頂點"<<g.GetValue(i)
       <<"到其他各頂點的最短路徑的前一頂點為:\n";
   for(j=0;j<n;j++)
    if(path[i][j]!=-1)
     cout<<"到頂點"<<g.GetValue(j)<<"的前一頂點為:"
         <<g.GetValue(path[i][j])<<endl;
 }
 cin.get();cin.get();}
FloydP.cpp運行結果:
輸入圖的總邊數:9
輸入9條有向有權邊的起點和終點序號及權值!
創建后的鄰接矩陣:
   0  99   5  30  99  99
   2   0  99  99   8  99
  99  15   0  99  99   7
  99  99  99   0  99  99
  99  99  99   4   0  99
  99  99  99  10  18   0
從頂點A到其他各頂點的最短距離為:
到頂點A的最短距離為:0
到頂點B的最短距離為:20
到頂點C的最短距離為:5
到頂點D的最短距離為:22
到頂點E的最短距離為:28
到頂點F的最短距離為:12
從頂點A到其他各頂點的最短路徑的前一頂點為:
到頂點A的前一頂點為: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
到頂點B的前一頂點為:A
到頂點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
到頂點C的前一頂點為:A
到頂點D的前一頂點為:F
到頂點E的前一頂點為:B
到頂點F的前一頂點為:C
從頂點D到其他各頂點的最短距離為:
到頂點A的最短距離為:99
到頂點B的最短距離為:99
到頂點C的最短距離為:99
到頂點D的最短距離為:0
到頂點E的最短距離為:99
到頂點F的最短距離為:99
從頂點D到其他各頂點的最短路徑的前一頂點為:
到頂點D的前一頂點為:A
從頂點E到其他各頂點的最短距離為:
到頂點A的最短距離為:99
到頂點B的最短距離為:99
到頂點C的最短距離為:99
到頂點D的最短距離為:4
到頂點E的最短距離為:0
到頂點F的最短距離為:99
從頂點E到其他各頂點的最短路徑的前一頂點為:
到頂點D的前一頂點為:E
到頂點E的前一頂點為:A
從頂點F到其他各頂點的最短距離為:
到頂點A的最短距離為:99
到頂點B的最短距離為:99
到頂點C的最短距離為:99
到頂點D的最短距離為:10
到頂點E的最短距離為:18
到頂點F的最短距離為:0
從頂點F到其他各頂點的最短路徑的前一頂點為:
到頂點D的前一頂點為:F
到頂點E的前一頂點為:F
到頂點F的前一頂點為:A