求每对顶点间的最短路径

忘是亡心i 2021-11-29 17:58 268阅读 0赞

用动态规划的方法，解决有些爱那个图G=（V，E）上每对顶点间的最短路径问题。路径图用邻接矩阵存储。具体的描述参考：[http://tayoto.blog.hexun.com/26047245\_d.html][http_tayoto.blog.hexun.com_26047245_d.html]里面的第一点的介绍。

直接上代码：

/*************************************************************************
        > File Name: show_all_pairs_shortest_path.cpp
        > Author: He Xingjie
        > Mail: gxmshxj@163.com
        > Created Time: 2014年06月10日 星期二 17时32分37秒
        > Description: 
     ************************************************************************/
    #include<iostream>
    #include<cstdio>
    #include<stack>
    
    using namespace std;
    
    #define MAX 50
    #define INF 65535
    
    int map[MAX][MAX], dist[MAX], path[MAX][MAX];
    
    void ExtendShortestPaths(int n)
    {
        int i, j, k;
    
        for (i=0; i<n; i++)
            for (j=0; j<n;j++)
                for (k=0; k<n; k++)
                    if (map[i][j] > map[i][k] + map[k][j])
                    {
                        map[i][j] = map[i][k] + map[k][j];
                        path[i][j] = path[k][j];
                    }
    }
    
    void ShowAllPairsShortestPaths(int n)
    {
        int i;
    
        for (i=1; i<n-1; i++)
            ExtendShortestPaths(n);
    }
    
    void PrintMap(int n)
    {    
        printf("Map:\n");
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
                cout<<map[i][j]<<"  ";
            cout<<endl;
        }
    }
    
    void PrintShortestPaths(int n)
    {
        int i, j;
        stack<int> st;
    
        printf("Shortest Path:\n");
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)
            {
                st.push(j+1);
                int pre = path[i][j];
                while (pre != i+1 && pre != 0)
                {
                    /*
                     *st.push(path[i][pre-1]);
                     *pre = path[i][pre-1];
                     */
                    st.push(pre);
                    pre = path[i][pre-1];
                    
                }
                printf("%d: %d", map[i][j], i+1);
    
                while (!st.empty())
                {
                    printf("->%d",st.top());
                    st.pop();
                }
                printf("\n");
            }
    }
    
    int main()
    {
        int n;
    
        freopen("input.txt", "r", stdin);
    
        cin>>n;
        for (int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                cin>>map[i][j];
                if (map[i][j] != INF)
                    path[i][j] = i+1;
                else
                    path[i][j] = 0;
            }
    
        ShowAllPairsShortestPaths(n);
        
        PrintMap(n);
    
        PrintShortestPaths(n);
    
        return 0;
    }
    
    2014/6/10 22：16

输入数据：

5
    0 3 8 65535 -4
    65535 0 65535 1 7
    65535 4 0 65535 65535
    2 65535 -5 0 65535
    65535 65535 65535 6 0
    
    //最大值设置为65535

输出结果：

![102220087495794.png][]

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

[http_tayoto.blog.hexun.com_26047245_d.html]: http://tayoto.blog.hexun.com/26047245_d.html
[102220087495794.png]: /images/20211129/3b36898cf25445499b5444dd2f75f53a.png