最短路径 | Floyd-Warshall算法（HDU2112）

HDU Today（HDU2112）

Time Limit: 15000/5000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

Problem Description
经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。

Input
输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。
Output
如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。

Sample Input
6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1
Sample Output
50

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2112

题解【Floyd-Warshall算法】

// Timelimit:5000MS
// Floyd + map
// 4352MS / 1548K

#include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

int n; //输入数据的组数    
const int inf=0xffffff; //表示+∞ 
int mmap[155][155]; //从图的起始节点到中止结点所花费的时间 

int main()
{
    //提交到oj的时候记得注释掉【坑点二】
    freopen("C:\\Users\\Desktop\\AK\\图\\read1.txt","r",stdin);
    freopen("C:\\Users\\Desktop\\AK\\图\\out1.txt","w",stdout);

    while((cin>>n)&&n!=-1)
    {
        map<string,int>m; //从string到int的映射 
        //map<string,int>::iterator iter;
        string start,end; //出发的起点和目的地 
        m.clear(); //清空映射m 
        
        //初始化图 
        for(int i=1;i<=153;i++)
        {
            for(int j=1;j<=153;j++)
            {
                if(i!=j)mmap[i][j]=inf; // 花费的时间为+∞ 
                else mmap[i][j]=0; //如果起始结点等于中止结点，花费的时间为0 
            }
        }
        
        cin>>start>>end;
        m[start]=1; //将起点映射为1 
        m[end]=2; //将目的地映射为2 
        int pre=2; //pre:图的顶点个数 
        
        //读取并处理数据 
        for(int i=1;i<=n;i++)
        {
            string s,e; //字符串 
            int t; //时间 
            cin>>s>>e>>t;
        
            //插入一个pair对象
            // m.insert( make_pair(key, value))返回一个pair对象
            //当map中没有与key相匹配的键值时，其first是指向插入元素对的迭代器，其second为true
            //若map中已经存在与key相等的键值时，其first是指向该元素对的迭代器，second为false。
            pair<map<string,int>::iterator,bool> pair1=m.insert(make_pair(s,++pre));  
            if(pair1.second==0)pre--; //如果pair插入不成功【映射m中已经存在此pair对象】 
                
            pair<map<string,int>::iterator,bool> pair2=m.insert(make_pair(e,++pre));
            if(pair2.second==0)pre--;
                
            if(mmap[m[s]][m[e]]>t) //处理数据，并放入数组mmap中 
            {
                mmap[m[s]][m[e]]=t;
                mmap[m[e]][m[s]]=t; //无向图【坑点一】 
                                    //公交车从起点到终点和从终点到起点花费的时间相同 
            }
        }
        
        // 核心代码 
        for(int k=1;k<=pre;k++) //k：i->j的中间点【中间媒介,可能不止一个】 
        {
            for(int i=1;i<=pre;i++) //遍历图中所有结点 
            {
                for(int j=1;j<=pre;j++)
                {
                    if(mmap[i][j]>mmap[i][k]+mmap[k][j])）
                    //如果经过中间点花费的时间短，就刷新i到j所花费的时间 
                    {
                        mmap[i][j]=mmap[i][k]+mmap[k][j];
                    }
                }
            }
        }
        
        //输出结果 
        if(m[start]==m[end])printf("0\n"); //如果起点等于终点，则输出0 
        else if(mmap[1][2]==inf)printf("-1\n"); //如果不能从起点到达终点，则输出-1 
        else printf("%d\n",mmap[1][2]); //否则，输出从起点到终点花费的时间 
    }
    fclose(stdin);
    fclose(stdout); // 提交到oj上面时，记得将这几行代码注释掉，否则会WA【坑点二】 
    return 0;
}

Floyd-Warshall算法

基本思想：

根据以往的经验，如果要让任意两个点（例如从顶点a到顶点b）之间的路程变短，只能引入第三个点（顶点k），通过这个顶点k中转，即a->k->b，才有可能缩短原来从顶点a到顶点b的路程。

有些时候甚至不只通过一个中转点，而是经过两点中转点或者更多，即a->k1->k2->b或者a->k1->k2->k3->......->b，使得从顶点a到顶点b的路径更短。

那么，这些中转点是一个含有n个顶点的图中的那些点呢？这就需要我们去判断。

假设我们将1号顶点看成中转点，求图中任意两点之间的最短路径，只需要判断mmap[i][1]+mmap[1][j]是否会比mmap[i][j]小即可。

if(mmap[i][j]>mmap[i][k]+mmap[k][j])

其中，mmap[i][j]表示从i号顶点到j号顶点之间的路程，mmap[i][1]+mmap[1][j]表示从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。i是1~n的循环，j也是1~n的循环。代码实现如下：

for(int i=1;i<=pre;i++) //遍历图中所有结点 
{
     for(int j=1;j<=pre;j++)
     {
         if(mmap[i][j]>mmap[i][k]+mmap[k][j]) //如果经过中间点花费的时间短，就刷新i到j所花费的时间 
         {
             mmap[i][j]=mmap[i][k]+mmap[k][j];
         }
     }
}

我们发现图中每个顶点都有可能使得另外两个顶点之间的路程变短，因此，还需要一个1~n的循环，遍历图中每个顶点。

核心代码：

for(int k=1;k<=pre;k++) //k：i->j的中间点【中间媒介,可能不止一个】 
{
    for(int i=1;i<=pre;i++) //遍历图中所有结点 
    {
        for(int j=1;j<=pre;j++)
        {
            if(mmap[i][j]>mmap[i][k]+mmap[k][j]) //如果经过中间点花费的时间短，就刷新i到j所花费的时间 
            {
                mmap[i][j]=mmap[i][k]+mmap[k][j];
            }
        }
    }
}

特别注意：

Floyd-Warshall算法可以求出任意两个点之间的最短路径，它的时间复杂度为O(N^3)。令人震撼的是它的核心代码只有五行，这实现起来非常容易。

如果题目对于时间复杂度要求不高，使用Floyd-Warshall算法来求指定两点之间的最短路径或者指定一个点到其余各个顶点的最短路径是可行的。

Floyd-Warshall算法不能解决带有“负权回路” / “负权环”的图的最短路径问题，因为带有“负权回路”的图没有最短路径。

例如下面这个图就不存在从1号顶点到3号顶点的最短路径，因为在1->2->3->1->2->3......1->2->3这样的路径中，每绕一次1->2->3这样的负权环，最短路径就会减3，永远都找不到最短路径。

带有负权回路的图

小结论：如果一个图中带有“负权回路”，那么这个图不存在最短路径。

PS：当然，这道题目还有其他的解法，将在后面的内容介绍。

写在最后:

参考资料：

• 《啊哈！算法》（文字来源）
• 极客学院：算法 6：只有五行的 Floyd 最短路算法

打一波广告，自己的公众号，不是技术文，主要是分享自己的一些想法，欢迎前来关注，非喜勿喷。

我锨说