最短路径——Floyd算法及优化（蓝桥杯试题集）

*对最短路径问题以及floyd算法、Dijkstra算法不是很理解的同学请移步前几篇博客~

题目链接：

http://lx.lanqiao.cn/problem.page?gpid=T15

问题描述
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入格式
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式
共n-1行，第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

解题思路：

我们看到，这是一个有负值的有向图最短路径问题，我们直到，含有负值的边我们是无法使用Dijkstra的，原因很简单，Dijkstra是采用贪心的思想

其目光比较短浅23333，Dijkstra是不会想到 如果A→B大于A→C 但是还存在一个点K，使A→B→K→C要小于AC这样的情况的

所以我们先采取全部枚举的floyd算法处理一下这道题

#include<stdio.h>
#define INF 0xFFFFFFF 
int a[8010][8010];
int fmin(int a,int b)
{
	return a<b?a:b;
}
int main()
{
	int n,m,i,j,k;
	int u,v,l;
	while(~scanf("%d%d",&n,&m))
	{
		for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		i==j?a[i][j]=0:a[i][j]=INF;
				
		while(m--)
		{
			scanf("%d%d%d",&u,&v,&l);
			a[u][v]=fmin(a[u][v],l);
		}
		for(k=1;k<=n;k++)         //存在一个k 使aik+akj路径小于aij 
        for(i=1;i<=n;i++) 
        for(j=1;j<=n;j++)          
        a[i][j]=fmin(a[i][j],a[i][k]+a[k][j]);  
     for(i=2;i<=n;i++)
     printf("%d\n",a[1][i]);
    }
 return 0;
}

显然是不行的啦=.=

然后我们可以尝试一些优化的方法:

我们把无效路径压缩一下：思路可以参考http://blog.csdn.net/sm9sun/article/details/53258503

#include<stdio.h>
#define inf 0xFFFFFFF
int dp[20011][1600][2]; //对于i点j条边所对应的点以及权值
int count[20011];       //i点总共的边数
int o[20011];           //optimum
int fmin(int a,int b)
{
	return a<b?a:b;
}           
void sx(int k)
{    
    int i;
	for(i=0;i<count[k];i++) 
    {
    	if((o[dp[k][i][0]])>(o[k]+dp[k][i][1]))
    	{
    		o[dp[k][i][0]]=o[k]+dp[k][i][1];
    		sx(dp[k][i][0]);
    	}
    	
    }
}
int main()
{
int i,j,k,n,m;
int s,e,l;
while(~scanf("%d%d",&n,&m))
{
	for(i=1;i<=n;i++)
	{
	count[i]=0;
	o[i]=inf;
    }
	for(i=1;i<=m;i++)
	{
	scanf("%d%d%d",&s,&e,&l);
	dp[s][count[s]][0]=e;
	dp[s][count[s]][1]=l;
	count[s]++;
    }
    for(i=0;i<count[1];i++)
    o[dp[1][i][0]]=fmin(o[dp[1][i][0]],dp[1][i][1]);

    for(k=2;k<=n;k++)         //存在一个k 使aik+akj路径小于aij 
    sx(k);
    for(i=2;i<=n;i++)
    printf("%d\n",o[i]);

}
return 0;
}

最后两个数据还是无法过~我们再优化一下输入

#include<stdio.h>
#define inf 0xFFFFFFF
int dp[20011][1600][2]; 
int count[20011];
int o[20011];
int fmin(int a,int b)
{
	return a<b?a:b;
}           
void sx(int k)
{    
    int i;
	for(i=0;i<count[k];i++) 
    {
    	if((o[dp[k][i][0]])>(o[k]+dp[k][i][1]))
    	{
    		o[dp[k][i][0]]=o[k]+dp[k][i][1];
    		sx(dp[k][i][0]);
    	}
    	
    }
}
void dr()
{

	int s,e,l,j;
	scanf("%d%d%d",&s,&e,&l);
	for(j=0;j<count[s];j++)
	{
		if(dp[s][j][0]==e)
		{
		dp[s][j][1]=fmin(dp[s][j][1],l);
		return;
	    }
	}	
	dp[s][count[s]][0]=e;
	dp[s][count[s]][1]=l;
	count[s]++;
	
}

int main()
{
int i,j,k,n,m;

while(~scanf("%d%d",&n,&m))
{	
	for(i=1;i<=n;i++)
	{
	count[i]=0;
	o[i]=inf;
    }
	for(i=1;i<=m;i++)
	dr();
    for(i=0;i<count[1];i++)
    o[dp[1][i][0]]=fmin(o[dp[1][i][0]],dp[1][i][1]);

    for(k=2;k<=n;k++)         //存在一个k 使aik+akj路径小于aij 
    sx(k);
    for(i=2;i<=n;i++)
    printf("%d\n",o[i]);
}
return 0;
}

后面的数据的确有了提升，但是依然不满足最后的数据~

那么对于含有负权值的最短路径问题我们该如何处理呢？请看下一篇博客——SPFA算法