算法训练 最短路
问题描述
给定一个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算法处理不了，所以立马舍弃，至于Floyd数据量太大，适用于小型测试用例，现在能使用的就只有Bellman-Ford 和队列优化的Bellman-Ford算法。先附上Bellman-Ford代码，此算法也是优化过一点点的，具体优化方案是因为Bellman算法执行到一定程度时，就已经将全部的最短路径求出来了，我们只需要找到dis数组（储存最短路径数组）不变的时候，说明最短路径已经全部求出，算法已经可以退出了。
Bellman-Ford
#include<stdio.h>
#include<string.h>
int main(){
int dis[20005],bak[20005],u[200005],v[200005],w[200005];//bak数组用来验证最短路径是否全部算完
int i,j,a,b,c,n,m,check=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d%d",&u[i],&v[i],&w[i]);
}
memset(dis,999999,sizeof dis);
dis[1]=0; //将一号顶点置为0
//核心算法
for(i=1;i<=n-1;i++){
for(i=1;i<=n;i++) bak[i]=dis[i];
for(j=1;j<=m;j++){
if(dis[v[j]]>dis[u[j]]+w[j]){ //1号顶点到v[j]顶点的路径 > 1号顶点到u[j]的距离 + v[j]到u[j]边的权值
dis[v[j]]=dis[u[j]]+w[j];
}
}
check=0;
for(i=1;i<=n;i++)
//只要有不相等的说明最短路径还没算完，退出验证的循环
if(bak[i]!=dis[i]){
check=1;
break;
}
if(check==0) break;//最短路径全部算完，退出核心算法循环
}
for(i=2;i<=n;i++) printf("%d\n",dis[i]);
return 0;
}
刚开始提交的时候把dis初始化成10001了，u v w 也只给了20005的大小，只对了80%,最后尝试改了一下，没想到还全对了，哈哈哈！！！以此鼓励。
Bellman-Ford队列优化
#include<stdio.h>
int main(){
int i,j,n,m,k,head=1,tail=1;
scanf("%d%d",&n,&m);
int dis[n+1],u[m+1],v[m+1],w[m+1],first[n+1],next[m+1],book[n+1];
//book: 储存那些元素用了 first 、next : 数组实现邻接表 dis: 储存最短路径
int que[200005]={0};
//que:队列 用处就是减少了运算的次数 已经算出最短路径的确定值 就没有必要再算了 置为1
//初始化
for(i=1;i<=n;i++){
book[i]=0;
dis[i]=999999;
first[i]=-1;
}
for(i=1;i<=m;i++){
scanf("%d%d%d",&u[i],&v[i],&w[i]);
//数组实现的邻接表 核心代码
next[i]=first[u[i]];
first[u[i]]=i;
}
//1号顶点到自己的路径当然是0啦
dis[1]=0;
//一号顶点入队
que[tail]=1; tail++;
book[1]=1;
//队列中有元素才进循环
while(head<tail){
//取队头的第一个元素 然后再从first数组找到所储存的顶点
k=first[que[head]];
while(k!=-1){
if(dis[v[k]]>dis[u[k]]+w[k]){
dis[v[k]]=dis[u[k]]+w[k];
if(book[v[k]]==0){
book[v[k]]=1;
que[tail]=v[k];
tail++;
}
}
k=next[k]; //从next中找到相连的顶点 这个顶点是first[que[head]]的下一个顶点
//好比1->3这样子 3就是1的下一个顶点
}
//这里还要把处理队头的顶点置为0，因为很有可能这个顶点还会再次入队
book[que[head]]=0;
//出队
head++;
}
for(i=2;i<=n;i++) printf("%d\n",dis[i]);
return 0;
}
弄懂了原理，还是要多做题才能理解的更深刻，毕竟容易忘掉一些细节。
加油啊！！…
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
