最短路径算法—Bellman-Ford（poj1860 currency exchange）
Bellman-Ford算法详讲
该算法旨在有效解决单源最短路径问题，在处理仅含非负权重边的图时表现良好。然而，在存在某条边具有负权重的情况下，则可能导致计算所得的最短路径并非全局最优解。
此时，则有必要调用其他算法来计算最短路径。Bellman-Ford算法在众多路径finding算法中应用最为广泛。该方法源自理查德·贝尔曼（Richard Bellman）与小莱斯特·福特（Lester Ford）的卓越贡献
适用条件&范围：
单源最短路径(从源点s到其它所有顶点v);
有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
边权可正可负(如有负权回路输出错误提示);
差分约束系统;
具体来说，在图论中
在以下步骤中进行如下操作：首先，在图中初始化所有顶点的距离值Distant为无穷大，并将起始顶点的距离设为零；接着，在每次迭代中遍历每条边e(u, v)，若当前顶点u的距离加上边e(u, v)的权重w(e)小于顶点v的距离，则更新顶点v的距离值为u的距离加上权重w(e)；如果在某次迭代中没有任何距离值发生更新，则表明已经找到了所有顶点的最短路径或存在不可达的顶点而无需继续计算；此时程序将终止并输出结果
为确定图中是否存在权值总和为负数的回路而进行了检测。当检查所有边e(u, v)时发现有满足Distant[u] + w(u, v) < Distant[v]的情况出现时，则判定该图存在负环回路（即无法求解从单一源点出发到各顶点的最短路径问题）。反之，在未发现上述情况时，则表明数组Distant[n]中的数值代表了源点s到各顶点v的具体最短距离长度。
可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).
Bellman－Ford算法的主要组成部分包含三部分：首先对每个节点都维护一个数值来记录其到起始节点的距离；其次通过执行n−1次迭代来更新各节点之间的最短路径估计值；最后通过遍历每条边来检测是否存在权值为负的环路。具体来说，在初始化阶段将起始节点的距离设置为零而其他节点的距离设为无穷大以表示初始不可达状态。随后在每次迭代中对每条边进行松弛操作从而逐步优化各节点间的最短路径估计值。完成所有迭代后需再次遍历所有边验证是否存在违反最短路径条件的情况如果发现就表明图中存在可到达的负权环否则算法结束并返回正确的结果。
为了使第三部分有效运行而不至于陷入无法收敛的情况，在图中存在从源点可达且具有负权值的回路时。
测试代码如下：（下面为有向图的Bellman-Ford算法）
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, original; //点，边，起点
typedef struct Edge //边
{
int u, v;
int cost;
}Edge;
Edge edge[N];
int dis[N], pre[N];
bool Bellman_Ford()
{
for(int i = 1; i <= nodenum; ++i) //初始化
dis[i] = (i == original ? 0 : MAX);
for(int i = 1; i <= nodenum - 1; ++i)
for(int j = 1; j <= edgenum; ++j)
if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）
{
dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
pre[edge[j].v] = edge[j].u;
}
bool flag = 1; //判断是否含有负权回路
for(int i = 1; i <= edgenum; ++i)
if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
{
flag = 0;
break;
}
return flag;
}
void print_path(int root) //打印最短路的路径（反向）
{
while(root != pre[root]) //前驱
{
printf("%d-->", root);
root = pre[root];
}
if(root == pre[root])
printf("%d\n", root);
}
int main()
{
scanf("%d%d%d", &nodenum, &edgenum, &original);
pre[original] = original;
for(int i = 1; i <= edgenum; ++i)
{
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);
}
if(Bellman_Ford())
for(int i = 1; i <= nodenum; ++i) //每个点最短路
{
printf("%d\n", dis[i]);
printf("Path:");
print_path(i);
}
else
printf("have negative circle\n");
return 0;
}最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(C/C++)
相关文章：
1.Dijkstra算法：
http://www.wutianqi.com/?p=1890
2.Floyd算法：
http://www.wutianqi.com/?p=1903
Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特•福特（Lester Ford）发明。Bellman-Ford算法的流程如下：
给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，
- 数组Distant[i]存储从源点s到顶点i的距离，在初始化阶段将所有元素设置为空，并使索引s的位置赋值为0。
该过程持续最多n−1次迭代（其中n代表顶点数量）：
针对每条边e连接u和v节点（记作e(u,v)），当且仅当前节点u的距离加上边权w(e)小于目标节点v的距离时，则更新目标节点v的距离值为当前距离与边权之和。
如果在某次迭代中所有节点的距离值均未发生变化，则表明最短路径已寻找到或存在不可达节点而提前退出循环；否则继续进行下一次迭代。
为了判断图中是否存在权值和小于零的环。针对每一条边e(u, v)，若某条边满足Distant[u] + w(u, v) < Distant[v]的情况，则称该图包含一个负权环。此性质表明该图无法求解单源最短路径问题。反之，在满足所有条件的情况下，数组Distant[n]存储了源点s到各顶点v的最短距离。
显然地，在单源最短路径问题中使用贝尔曼-福特算法计算从单一源点到所有其他节点的最短路径的时间复杂度为O(VE)。
首先介绍一下松弛计算。如下图：
在松弛计算前，在图中各节点之间已经确定了初始的距离估计值。然而，在某些特定情况下（例如当某条边上的权重较低时），节点A的距离加上该边上赋予的小于当前节点间距离差异（此处指小于当前节点间距离差异），这将导致目标节点的距离发生相应变化并被重新评估。当然，在某些特定情况下（例如当某条边上的权重较高时），这样的操作可能会导致目标节点的距离发生相应变化并被重新评估）。这一过程的意义在于发现了通向目标节点的一条更短路径，并且这条路径首先经过了A节点并通过权重为2的边与目标节点相连
则不会修改点B的值，因为3＋4>6。
该算法大致可分为三个阶段：首先初始化各个节点的距离值；接着经过n−1次完整的遍历所有边的操作；最后对所有边进行松弛操作来检测是否存在负权环。
第一阶段：初始化各个节点的距离值。
每个节点存储一个距离值：源节点距离设为零；其余节点初始距离设为无穷大。
第二阶段：经过n−1次完整的遍历所有边的操作。
第三阶段：对所有边进行松弛操作来检测是否存在负权环。
对于每条边(edge (u, v))：
如果满足d(v) > d(u) + w(u, v)，则表示存在可到达的负权环而返回false。
之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。
考虑如下的图：
在第一次遍历结束后，在线更新过程中，我们发现：点B的新值为5、点C的新值为8；随后，在注意到具有-10权重的一条边时：该条边的存在使得点A的新值进一步更新至-2（计算过程如上所示）。
第二次遍历结束后，在点B、C和A处分别变化为3、6和-4。由于存在负权环路中的一条负边，在每次遍历过程中各节点值持续下降。
回顾bellman-ford算法的第三阶段，在该阶段系统性地遍历每一条边以执行特定操作：即判断是否满足D_{v} > D_{u} + w(u,v)这一条件。由于第二阶段循环次数固定，在存在无法收敛情况时可以通过第三阶段的操作及时发现这些问题。因此，在第三阶段执行此检查时就可及时发现问题。
此时，点A的值为－2，点B的值为5，边AB的权重为5，5 > -2 + 5. 检查出来这条边没有收敛。
此算法能够处理带有负权值的边所构成图中的单源最短路径问题。
以下是Bellman-Ford代码:
||
||
/*
* About: Bellman-Ford算法
* Author: Tanky Woo
* Blog: www.WuTianqi.com
*/
#include <iostream>
using namespace std;
const int maxnum = 100;
const int maxint = 99999;
// 边，
typedef struct Edge{
int u, v; // 起点，重点
int weight; // 边的权值
}Edge;
Edge edge[maxnum]; // 保存边的值
int dist[maxnum]; // 结点到源点最小距离
int nodenum, edgenum, source; // 结点数，边数，源点
// 初始化图
void init()
{
// 输入结点数，边数，源点
cin >> nodenum >> edgenum >> source;
for(int i=1; i<=nodenum; ++i)
dist[i] = maxint;
dist[source] = 0;
for(int i=1; i<=edgenum; ++i)
{
cin >> edge[i].u >> edge[i].v >> edge[i].weight;
if(edge[i].u == source) //注意这里设置初始情况
dist[edge[i].v] = edge[i].weight;
}
}
// 松弛计算
void relax(int u, int v, int weight)
{
if(dist[v] > dist[u] + weight)
dist[v] = dist[u] + weight;
}
bool Bellman_Ford()
{
for(int i=1; i<=nodenum-1; ++i)
for(int j=1; j<=edgenum; ++j)
relax(edge[j].u, edge[j].v, edge[j].weight);
bool flag = 1;
// 判断是否有负环路
for(int i=1; i<=edgenum; ++i)
if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
{
flag = 0;
break;
}
return flag;
}
int main()
{
//freopen("input3.txt", "r", stdin);
init();
if(Bellman_Ford())
for(int i = 1 ;i <= nodenum; i++)
cout << dist[i] << endl;
return 0;
}例题：poj1860
Currency Exchange
| Time Limit: 1000MS | Memory Limit: 30000K | |
|---|---|---|
| Total Submissions: 34920 | Accepted: 13397 |
Description
位于该市的多个货币兑换点正在运营。每个兑换点专注于两种特定货币，并且仅在这两种货币之间进行兑换操作。值得注意的是，在同一城市中可能存在多个兑换点专注于相同的货币对交易。每个兑换点都有独特的汇率设置：将A转换为B的汇率表示为每1单位A可换取的B的数量。此外，请注意所有手续费均按原始货币计算。
举个例子：如果您希望将100美元兑换成卢布进行操作，则需要考虑当前汇率以及手续费的影响：具体来说，在某个兑换点处使用29.75的汇率并支付0.39单位美元作为手续费的情况下（注：这里的"units"是指原始货币），您最终能够获得的资金总量将是(100 - 0.39) * 29.75 = 2963.3975卢布。
现在我们假设有N种不同的可交易货币，并给每个货币分配唯一的整数编号（从1到N）。这样就可以用6个参数来描述任意一个兑换点：包括两个待交换货币的编号（A和B）、以及四种相关参数——即AB方向上的汇率值和相应的手续费（分别记作R_AB、C_AB、R_BA和C_BA）。
我们的目标是帮助某位投资者评估其资金流动方案是否可行——具体来说就是判断是否存在一种资金流动路径能够让投资者最终拥有与最初相同的资金规模的同时实现财富增长。
Input
The first line of the input contains four numbers: N - the number of currencies, M - the number of exchange points, S - the number of currency Nick has and V - the quantity of currency units he has. The following M lines contain 6 numbers each - the description of the corresponding exchange point - in specified above order. Numbers are separated by one or more spaces. 1<=S<=N<=100, 1<=M<=100, V is real number, 0<=V<=10 3.
For each point exchange rates and commissions are real, given with at most two digits after the decimal point, 10 -2<=rate<=10 2, 0<=commission<=10 2.
Let us call some sequence of the exchange operations simple if no exchange point is used more than once in this sequence. You may assume that ratio of the numeric values of the sums at the end and at the beginning of any simple sequence of the exchange operations will be less than 10 4.
Output
If Nick is able to enhance his financial status, return YES; otherwise, do not return YES but rather NO into the specified file.
Sample Input
Sample Output
设有N种不同的货币，在这些货币中存在部分能够实现互相兑换的情形下，请确定是否存在这样一种情况：即从某一种选定的起始货币出发，在经过若干中间环节之后能够最终兑剧行回该起始货币本身的同时还能使所获得的资金总额较初始有所增加？
以初始兑换的货币为出发点，在汇率网络中应用Bellman-Ford算法进行处理。若能实现目标，则表明图中存在可无限增大的回路。可以通过该算法检测回路的存在性并得出结论：如果在计算过程中发现已将货币兑换回原始货币并获得更高金额，则立即终止算法。此外，在计算过程中应确保所有货币值均为非负数，并设置所有初始路径长度为零；当前持有的货币数量设为v；按照给定的兑换规则对边进行松弛处理即可完成计算过程
#include<iostream>
#include<cstring>
using namespace std;
int n,m,s;
int num;
double v,dis[205];
struct edge
{
int v1;
int v2;
double rat;
double com;
}edges[410];
bool bellmanford()
{
for(int i=1;i<n;i++)
{
bool flag=false;
for(int j=0;j<num;j++)
{
int v1=edges[j].v1;
int v2=edges[j].v2;
if((dis[v1]-edges[j].com)*edges[j].rat>dis[v2])
{
dis[v2]=(dis[v1]-edges[j].com)*edges[j].rat;
flag=true;
}
}
if(flag==false) break;
}
for(int j=0;j<num;j++)
{
int v1=edges[j].v1;
int v2=edges[j].v2;
if((dis[v1]-edges[j].com)*edges[j].rat>dis[v2]) return true;
}
return false;
}
int main()
{
while(cin>>n>>m>>s>>v)
{
num=0;
for(int i=0;i<m;i++)
{
cin>>edges[num].v1>>edges[num].v2>>edges[num].rat>>edges[num].com;
edges[num+1].v1=edges[num].v2; edges[num+1].v2=edges[num].v1;
num++;
cin>>edges[num].rat>>edges[num].com;
num++;
}
for(int i=1;i<=n;i++) dis[i]=0;
dis[s]=v;
if(bellmanford()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}