【1】为什么需要弗洛伊德算法？

带权图中单个源点到所有顶点的最短路径问题可以用《》求解。

那如果要求图中每一个顶点与其它顶点之间的最短路径呢？类似可以想到的方法为：

每次以一个顶点为源点，重复执行地杰斯特拉算法算法n次。

这样，理论上我们便可以求得每一个顶点与其它顶点的最短路径，总的执行时间为O(n3）。

好吧！为了实现这个中需求，可以采用另外一种求解算法：弗洛伊德算法。

为了更好的理解弗洛伊德算法的精妙，我们先看简单的案例。

如下图是一个最简单的3个顶点连通网图：

【2】弗洛伊德算法

弗洛伊德算法是非常漂亮的算法，简洁直观大气上档次。

不过很可惜由于它的三重循环，因此也是O(n*n*n)的时间复杂度。

如果你面临需要求所有顶点至所有顶点的最短路径问题？

它是很好的选择。算法代码如下图：

关于本算法再不做详细赘述。如若感兴趣，下面的代码案例可以自己琢磨琢磨。

【3】弗洛伊德算法实现

注意：本算法的实现案例与迪杰斯特拉算法相同都是在求同一个图的最短路径问题。

不同的是这个算法可以求得所有顶点到所有顶点的最短路径。

模拟实现代码如下：

1 #include 
      
         2 #include "SeqList.h"  3 #include 
       
          4 using namespace std;  5   6 #define  INFINITY  65535  7   8 typedef    int* pInt;  9 typedef pInt* ppInt; 10  11 template
        
          12 class Graph 13 { 14 private: 15     SeqList
         
           Vertices; 16     DistType **Edges; 17     int nVer, nEdges; 18  19 public: 20     Graph()  21         : Edges(NULL) 22         , nEdges(0) 23         , nVer(0) 24     {} 25     ~Graph() 26     {} 27  28 public: 29     int GetVer() const 30     { 31         return nVer; 32     } 33  34     istream & operator>>(istream &in) 35     { 36         int v, u, value; 37         int i, j; 38         NameType item; 39         cout << "请输入顶点的个数: " << endl; 40         in >> nVer; 41         cout << "请输入顶点的数据信息: " << endl; 42         for (i = 0; i < nVer; ++i) 43         { 44             in >> item; 45             Vertices.push_back(item);    // 保存全部顶点 46         } 47         /////二维数组的创建并初始化 48         Edges = new DistType*[nVer]; // DistType *ar[10]; 49         for (i = 0; i < nVer; ++i) 50         { 51             Edges[i] = new DistType[nVer]; 52             for (j = 0; j < nVer; ++j) 53             { 54                 Edges[i][j] = 0; 55             } 56         } 57         cout << "请输入边的个数: " << endl; 58         in >> nEdges; 59         cout << "请输入边的信息：" << endl; 60         for (i = 0; i < nEdges; ++i) 61         { 62             in >> v >> u >> value; 63             Edges[v][u] = value; 64             Edges[u][v] = value; 65         } 66         return in; 67     } 68     ostream & operator<<(ostream &out) const 69     { 70         int i, j; 71         out << "顶点信息 " << endl; 72         for (i = 1; i <= nVer; ++i) 73         { 74             out << Vertices[i] << setw(5); 75         } 76         out << endl; 77         out << "矩阵信息：" << endl; 78         out << setw(10); 79         for (i = 1; i <= nVer; ++i) 80         { 81             out << Vertices[i] << setw(5); 82         } 83         out << endl; 84         for (i = 0; i < nVer; ++i) 85         { 86             out << Vertices[i+1] << setw(5); 87             for (j = 0; j < nVer; ++j) 88             { 89                 if (0 == Edges[i][j] && i != j) 90                     Edges[i][j] = INFINITY; 91                 cout << Edges[i][j] << setw(5); 92             } 93             out << endl; 94         } 95         out << endl; 96  97         return out; 98     } 99     // 弗洛伊德算法实现100     void ShortestPath_Floyd(int** p, int** D)101     {102         int v = 0, w = 0, k = 0;103         // 初始化数据104         for (v = 0; v < nVer; ++v)105         {106             for (w = 0; w < nVer; ++w)107             {108                 D[v][w] = Edges[v][w];109                 p[v][w] = w;110             }111         }112         for (k = 0; k < nVer; ++k)113         {114             for (v = 0; v < nVer; ++v)115             {116                 for(w = 0; w < nVer; ++w)117                 {118                     if (D[v][w] > D[v][k] + D[k][w])119                     {120                         D[v][w] = D[v][k] + D[k][w];121                         p[v][w] = p[v][k];122                     }123                 }124             }125         }126     }127     // 打印矩阵信息128     void PrintArray(ppInt pp)129     {130         cout << setw(10);131         for (int i = 1; i <= nVer; ++i)132         {133             cout << Vertices[i] << setw(5);134         }135         cout << endl;136         for (int i = 0; i < nVer; ++i)137         {138             cout << Vertices[i+1] << setw(5);139             for (int j = 0; j < nVer; ++j)140             {141                 cout << pp[i][j] << setw(5);142             }143             cout << endl;144         }145         cout << endl;146     }147     // 求解完成后打印所以路径信息148     void PrintPath(ppInt pp, ppInt DD)149     {150         int v, k, w;151         for (v = 0; v < nVer; ++v)152         {153             for (w = v+1; w < nVer; ++w)154             {155                 cout << "V" << v << "-->" << "V" << w << " weight:" << DD[v][w] << endl;156                 k = pp[v][w];157                 cout << "Path:V" << v;158                 while (k != w)159                 {160                     cout << "-->V" << k;161                     k = pp[k][w];162                 }163                 cout << "-->V" << w << endl;164             }165         }166         cout << endl;167     }168 };169 170 template
          
           171 istream & operator>>(istream &in, Graph
           
             &g)172 {173 g >> in;174 return in;175 }176 177 template
            
             178 ostream & operator<<(ostream &out, const Graph
             
               &g)179 {180 g << out;181 return out;182 }183 184 185 void main()186 {187 Graph
              
                myg;188 cin >> myg;189 cout << "打印所有输入信息：" << endl;190 cout << myg << endl;191 cout << "求最短路径....." << endl;192 int numVer = myg.GetVer();193 ppInt pPathmatirx = new pInt[numVer];194 for (int i = 0; i < numVer; ++i)195 {196 pPathmatirx[i] = new int[numVer];197 for (int j = 0; j < numVer; ++j)198 {199 pPathmatirx[i][j] = 0;200 }201 }202 ppInt pShortPath = new pInt[numVer];203 for (int i = 0; i < numVer; ++i)204 {205 pShortPath[i] = new int[numVer];206 for (int j = 0; j < numVer; ++j)207 {208 pShortPath[i][j] = 0;209 }210 }211 myg.ShortestPath_Floyd(pPathmatirx, pShortPath);212 cout << "分别打印矩阵结果：" << endl;213 cout << "各顶点最短路径：" << endl;214 myg.PrintArray(pShortPath);215 cout << "各最短路径前驱顶点下标值：" << endl;216 myg.PrintArray(pPathmatirx);217 cout << "打印全部最短路径："<< endl;218 myg.PrintPath(pPathmatirx, pShortPath);219 // 释放二维数组220 for (int i = 0; i < numVer; ++i) 221 delete []pPathmatirx[i]; 222 delete []pPathmatirx;223 for (int i = 0; i < numVer; ++i) 224 delete []pShortPath[i]; 225 delete []pShortPath;226 pPathmatirx = NULL;227 pShortPath = NULL;228 }229 // 备注：230 // 最短路径弗洛伊德算法实现231 // 整理于2013-12-05232 // 测试输入程序为：233 /*234 请输入顶点的个数:235 9236 请输入顶点的数据信息:237 A B C D E F G H I238 请输入边的个数:239 16240 请输入边的信息：241 0 1 1242 0 2 5243 1 2 3244 1 3 7245 1 4 5246 2 4 1247 2 5 7248 3 4 2249 3 6 3250 4 5 3251 4 6 6252 4 7 9253 5 7 5254 6 7 2255 6 8 7256 7 8 4257 打印所有输入信息：258 顶点信息259 A B C D E F G H I260 矩阵信息：261 A B C D E F G H I262 A 0 1 5655356553565535655356553565535263 B 1 0 3 7 565535655356553565535264 C 5 3 065535 1 7655356553565535265 D65535 765535 0 265535 36553565535266 E65535 5 1 2 0 3 6 965535267 F6553565535 765535 3 065535 565535268 G655356553565535 3 665535 0 2 7269 H65535655356553565535 9 5 2 0 4270 I655356553565535655356553565535 7 4 0271 272 273 求最短路径.....274 分别打印矩阵结果：275 各顶点最短路径：276 A B C D E F G H I277 A 0 1 4 7 5 8 10 12 16278 B 1 0 3 6 4 7 9 11 15279 C 4 3 0 3 1 4 6 8 12280 D 7 6 3 0 2 5 3 5 9281 E 5 4 1 2 0 3 5 7 11282 F 8 7 4 5 3 0 7 5 9283 G 10 9 6 3 5 7 0 2 6284 H 12 11 8 5 7 5 2 0 4285 I 16 15 12 9 11 9 6 4 0286 287 各最短路径前驱顶点下标值：288 A B C D E F G H I289 A 0 1 1 1 1 1 1 1 1290 B 0 1 2 2 2 2 2 2 2291 C 1 1 2 4 4 4 4 4 4292 D 4 4 4 3 4 4 6 6 6293 E 2 2 2 3 4 5 3 3 3294 F 4 4 4 4 4 5 7 7 7295 G 3 3 3 3 3 7 6 7 7296 H 6 6 6 6 6 5 6 7 8297 I 7 7 7 7 7 7 7 7 8298 299 打印全部最短路径：300 V0-->V1 weight:1301 Path:V0-->V1302 V0-->V2 weight:4303 Path:V0-->V1-->V2304 V0-->V3 weight:7305 Path:V0-->V1-->V2-->V4-->V3306 V0-->V4 weight:5307 Path:V0-->V1-->V2-->V4308 V0-->V5 weight:8309 Path:V0-->V1-->V2-->V4-->V5310 V0-->V6 weight:10311 Path:V0-->V1-->V2-->V4-->V3-->V6312 V0-->V7 weight:12313 Path:V0-->V1-->V2-->V4-->V3-->V6-->V7314 V0-->V8 weight:16315 Path:V0-->V1-->V2-->V4-->V3-->V6-->V7-->V8316 V1-->V2 weight:3317 Path:V1-->V2318 V1-->V3 weight:6319 Path:V1-->V2-->V4-->V3320 V1-->V4 weight:4321 Path:V1-->V2-->V4322 V1-->V5 weight:7323 Path:V1-->V2-->V4-->V5324 V1-->V6 weight:9325 Path:V1-->V2-->V4-->V3-->V6326 V1-->V7 weight:11327 Path:V1-->V2-->V4-->V3-->V6-->V7328 V1-->V8 weight:15329 Path:V1-->V2-->V4-->V3-->V6-->V7-->V8330 V2-->V3 weight:3331 Path:V2-->V4-->V3332 V2-->V4 weight:1333 Path:V2-->V4334 V2-->V5 weight:4335 Path:V2-->V4-->V5336 V2-->V6 weight:6337 Path:V2-->V4-->V3-->V6338 V2-->V7 weight:8339 Path:V2-->V4-->V3-->V6-->V7340 V2-->V8 weight:12341 Path:V2-->V4-->V3-->V6-->V7-->V8342 V3-->V4 weight:2343 Path:V3-->V4344 V3-->V5 weight:5345 Path:V3-->V4-->V5346 V3-->V6 weight:3347 Path:V3-->V6348 V3-->V7 weight:5349 Path:V3-->V6-->V7350 V3-->V8 weight:9351 Path:V3-->V6-->V7-->V8352 V4-->V5 weight:3353 Path:V4-->V5354 V4-->V6 weight:5355 Path:V4-->V3-->V6356 V4-->V7 weight:7357 Path:V4-->V3-->V6-->V7358 V4-->V8 weight:11359 Path:V4-->V3-->V6-->V7-->V8360 V5-->V6 weight:7361 Path:V5-->V7-->V6362 V5-->V7 weight:5363 Path:V5-->V7364 V5-->V8 weight:9365 Path:V5-->V7-->V8366 V6-->V7 weight:2367 Path:V6-->V7368 V6-->V8 weight:6369 Path:V6-->V7-->V8370 V7-->V8 weight:4371 Path:V7-->V8372 */
              
             
            
           
          
         
        
       
      

关于本代码中的SeqList.h文件，可以从随笔《》拷贝一份即可。

 

Good   Good  Study, Day  Day  Up.

顺序  选择  循环  总结