Bellman-Ford算法的特点是能够解决带负权值的最短路径问题,并且实现起来比较简单。整个循环体循环V-1次,每次循环遍历图中的每一条边(u,v),并对点V做松弛操作。可以证明,通过V*E次的操作,最后得到的dist[i]值就是从原点到点i的最短路径。具体的Bellman-Ford的正确性证明见《算法导论》
但是,Bellman-Ford算法有一种情况不能处理,即图中存在从源可达的负权回路。如果出现这种情况,我们可以绕这这个环无限次,得到的最短路径即为负无穷。所以,这种情况下的最短路径问题是没有意义的。在Bellman-Ford算法中,还有一个对每条边的松弛判断,即验证上述情况。如果真的出现了从源可达的负权回路,算法返回false.
#include<iostream> using namespace std; class edge { public: int s,e; long long cost; }; int p,n,s,e,m; long long dist[301]; int pre[301]; long long maximum=1<<30; bool Bellman_Ford(edge*a,int m,int s) { for(int i=0;i<n;i++) { dist[i]=maximum; pre[i]=i; } dist[s]=0; for(int i=0;i<n-1;i++) { for(int j=0;j<m;j++) { int start=a[j].s; int end=a[j].e; if(dist[start]!=maximum&&(dist[start]+a[j].cost)<dist[end]) { dist[end]=dist[start]+a[j].cost; } } } for(int j=0;j<m;j++) { int start=a[j].s; int end=a[j].e; if(dist[start]!=maximum&&(dist[start]+a[j].cost)<dist[end]) return false; } return true; } int main() { //cout<<maximum<<endl; cin>>p; while(p--) { cin>>n; cin>>s>>e; cin>>m; edge a[m]; for(int i=0;i<m;i++) { cin>>a[i].s>>a[i].e>>a[i].cost; } if(Bellman_Ford(a,m,s)) { if(dist[e]==maximum) cout<<"infinity"<<endl; else cout<<dist[e]<<endl; } else cout<<"infinity"<<endl; } return 0; }
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1236http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1647http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1712http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1322Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 867首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1282朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1673题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2483AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1190二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2136网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 870trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 916bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1078我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1662LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2847zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1369染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 755线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 782快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3083斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1285本文大量 ...
相关推荐
单源最短路径--分支限界法
用贪心算法解单源最短路径问题 明确单源最短路径问题的概念;利用贪心算法解决单源最短路径问题;并通过本例熟悉贪心算法在程序设计中的应用方法。
A、掌握图中单源最短路径的概念; B、掌握Dijkstra算法的原理;
1.分支限界法求解单源最短路径 2.C++源码+程序说明文档 3.源码带详细注释
Bellman-Ford算法(单源最短路径) 矩阵是在main函数里输入的 可以处理带负权的图
经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径
Bellman-Ford算法是一种用于计算图中单源最短路径的算法,可以处理带有负权边的图。使用Python实现了这个算法。 Bellman-Ford算法是一种用于计算图中单源最短路径的算法,它可以处理带有负权边的图。以下是Bellman-...
单元最短路径,为广大计算机专业学生算法所需实验报告而准备
关于单源最短路径的问题非常典型,这里没有给出分析与证明,仅仅给出了实现。 需要指出的是,许多实现仅给出了最短路径的长度,而没有给出“最短路径”,这里用给出了实现。 如程序中那样,定义一个数组p[N],其中...
C#,图论与图算法,有向图单源最短路径的贝尔曼·福特(Bellman Ford)算法与源代码 贝尔曼·福特(Bellman Ford)算法是一种用于计算带权有向图中单源最短路径(SSSP:Single-Source Shortest Path)的算法。该算法...
有很长时间没有上传了,主要是因为这些天出了些小事。这个是用分支限界法求解单源最短路径问题的算法。
单源最短路径C语言实现,简单易懂,适合算法学习
分支限界法 (1)描述:采用广度优先产生状态空间树的结点,并使用剪枝函数的方法称为分枝限界法。 所谓“分支”是采用广度优先的策略,依次生成扩展结点的所有分支(即:儿子结点)。 所谓“限界”是在结点扩展...
算法设计与分析课内实验——动态规划求单源最短路径。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境)
在算法中,利用结点间的控制关系进行剪枝。从源顶点s出发,2条不同路径到达图G的同一顶点。由于两条路径的路长不同,因此可以将路长长的路径所对应的树中的结点为根的子树剪去。
基于贪心法求解单源最短路径问题 完整实验报告,结尾有实验代码
给定一个带权有向图 G=(V,E) ,其中每条边的权是一个整数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权...这个问题通常称为单源最短路径问题。
用python实现迪杰斯特拉算法,单源最短路径,有向图权值无负值,用邻接矩阵来存储有向图,实现路径存储和路径打印
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 ...(包括输入格式、算法、输出格式) ...(除了截图外,实验结果还用图表进行了分析) ...
用C++实现的贪心算法 Dijkstra 单源最短路径,并包含大量的注释,对理解程序很有帮助