Floyd-Warshall算法

以你之姓@ 2021-12-17 03:03 329阅读 0赞

Floyd也是采用动态规划的方案来解决在一个有向图G=（V，E）上每对顶点间的最短路径问题。运行时间为Θ（V3）。

**算法分析：**

**　　**用邻接矩阵map\[\]\[\]存储有向图，用dist\[i\]\[j\]表示i到j的最短路径。设G的顶点为V=\{1,2,3...n\}，对于任意一对顶点i,j属于V，假设i到j有路径且中间节点皆属于集合\{1,2,3...k\}，P是其中的一条最小权值路径。就是i到j的最短路径P所通过的中间顶点最大不超过k。

设![D\_\{i,j,k\}][D_i_j_k]为从![i][]到![j][]的只以![(1..k)][1..k]集合中的节点为中间节点的最短路径的长度。

1.  若最短路径经过点k，则![D\_\{i,j,k\}=D\_\{i,k,k-1\}+D\_\{k,j,k-1\}][D_i_j_k_D_i_k_k-1_D_k_j_k-1]；
2.  若最短路径不经过点k，则![D\_\{i,j,k\}=D\_\{i,j,k-1\}][D_i_j_k_D_i_j_k-1]。

因此，![D\_\{i,j,k\}=\\mbox\{min\}(D\_\{i,k,k-1\}+D\_\{k,j,k-1\},D\_\{i,j,k-1\})][D_i_j_k_mbox_min_D_i_k_k-1_D_k_j_k-1_D_i_j_k-1]。

for k ← 1 to n do
      for i ← 1 to n do
        for j ← 1 to n do
          if (Di,k + Dk,j < Di,j) then
             Di,j←Di,k + Dk,j ;

**实现代码：**

/*************************************************************************
        > File Name: Floyd_Warshall.cpp
        > Author: He Xingjie
        > Mail: gxmshxj@163.com
        > Created Time: 2014年06月12日 星期四 15时57分22秒
        > Description: 
     ************************************************************************/
    #include<iostream>
    #include<cstdio>
    using namespace std;
    
    #define MAX 20
    #define INF 65535
    
    //map邻接矩阵，dist记录最短路径,path用于最短路径
    int map[MAX][MAX], dist[MAX][MAX], path[MAX][MAX];
    
    int Init()
    {
        int n;
    
        cin>>n;
        for (int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                cin>>map[i][j];
                dist[i][j] = map[i][j];
                path[i][j] = 0;     
            }
    
        return n;
    }
    
    void Floyd(int n)
    {
        int i, j, k;
    
        for (k=0; k<n; k++)
            for (i=0; i<n; i++)
                for (j=0; j<n; j++)
                    if (dist[i][k] != INF && dist[k][j] !=INF
                            && dist[i][j] > dist[i][k] + dist[k][j])
                    {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = k;        //i到j要经过K节点
                    }
    }
    
    void PrintShortestPath(int i, int j)
    {
        //递归打印最短路径
        
        if (path[i][j] == 0)    //表示i->j没有中间节点
        {
            printf("%d ", j+1);
            return;
        }
        else
        {
            PrintShortestPath(i, path[i][j]);
            PrintShortestPath(path[i][j], j);
        }
    }
    
    void PrintMap(int n)
    {
        int i, j;
    
        for    (i=0; i<n; i++)
        {
            for (j=0; j<n; j++)
                cout<<dist[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
    }
    
    int main()
    {
        int n;
    
        freopen("input.txt", "r", stdin);
        n = Init();
        Floyd(n);
        PrintMap(n);
    
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                if (i != j)
                {
                    cout<<i+1<<" ";
                    PrintShortestPath(i, j);
                    cout<<endl;
                }
            }
            cout<<endl;
        }
        return 0;
    }
    
    2014/6/13  23：24

** 输入数据：**

5
    0 3 8 65535 -4
    655535 0 65535 1 7
    65535 4 0 65535 65535
    2 65535 -5 0 65535
    65535 65535 65535 6 0

**输出数据：**

**![132327594369148.png][]**

**参考：**

**[http://zh.wikipedia.org/zh/%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95][http_zh.wikipedia.org_zh_E5_BC_97_E6_B4_9B_E4_BC_8A_E5_BE_B7_E7_AE_97_E6_B3_95]**

**[http://www.cppblog.com/mythit/archive/2009/04/21/80579.aspx][http_www.cppblog.com_mythit_archive_2009_04_21_80579.aspx]**

转载于:https://www.cnblogs.com/Jason-Damon/p/3787736.html

[D_i_j_k]: http://upload.wikimedia.org/math/1/3/e/13eb4441f60a145abfaeaaf70be65954.png
[i]: http://upload.wikimedia.org/math/8/6/5/865c0c0b4ab0e063e5caa3387c1a8741.png
[j]: http://upload.wikimedia.org/math/3/6/3/363b122c528f54df4a0446b6bab05515.png
[1..k]: http://upload.wikimedia.org/math/b/e/2/be2b689bcd64e85ffe238a1d88305eae.png
[D_i_j_k_D_i_k_k-1_D_k_j_k-1]: /images/20211214/57afd3edfa7c42f491747cc19b8c83a4.png
[D_i_j_k_D_i_j_k-1]: /images/20211214/00159a9ccac84e35ad2062b7e7f7aec0.png
[D_i_j_k_mbox_min_D_i_k_k-1_D_k_j_k-1_D_i_j_k-1]: /images/20211214/f64b69792e9f456d88dece433567e999.png
[132327594369148.png]: /images/20211214/07155ab3dc1143e59eeb99e33d285a0e.png
[http_zh.wikipedia.org_zh_E5_BC_97_E6_B4_9B_E4_BC_8A_E5_BE_B7_E7_AE_97_E6_B3_95]: http://zh.wikipedia.org/zh/%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95
[http_www.cppblog.com_mythit_archive_2009_04_21_80579.aspx]: http://www.cppblog.com/mythit/archive/2009/04/21/80579.aspx