dijkstra算法与bellmanford-ford结果一样吗
点击联系发帖人
时间：2016-09-12 07:04
收藏成功！
添加标签来管理你的收藏
选择标签：
删除提示：
删除收藏标签，该标签下的内容将自动移至未加标签收藏中，确认要删除该标签吗？
确定要取消收藏吗？
关注成功！
关注精选邮箱：
尚未设置接收邮箱
取消关注后，将无法收到该知识库相关的知识动态和关注周报哦！确定要取消本知识库的关注吗？
技术领域：<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
您的访问请求被拒绝 403 Forbidden - ITeye技术社区
您的访问请求被拒绝
亲爱的会员，您的IP地址所在网段被ITeye拒绝服务，这可能是以下两种情况导致：
一、您所在的网段内有网络爬虫大量抓取ITeye网页，为保证其他人流畅的访问ITeye，该网段被ITeye拒绝
二、您通过某个代理服务器访问ITeye网站，该代理服务器被网络爬虫利用，大量抓取ITeye网页
请您点击按钮解除封锁&Bellman-Ford算法 -
&Bellman-Ford算法&
中不允许边的权是负权，如果遇到负权，则可以采用Bellman-Ford算法。
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s， w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。
适用条件&范围
1.(从源点s到其它所有顶点v);
2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
3.边权可正可负(如有负权回路输出错误提示);
Bellman-Ford算法描述：
1,.初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;
2.迭代求解：反复对边集E中的每条边进行，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
描述性证明：
首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。
在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。
每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）
如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。
如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。
例如对于上图，边上方框中的数字代表权值，顶点A,B,C之间存在负权回路。S是源点，顶点中数字表示运行Bellman-Ford算法后各点的最短距离估计值。
此时d[a]的值为1，大于d[c]+w(c,a)的值-2，由此d[a]可以松弛为-2，然后d又可以松弛为-5,d[c]又可以松弛为-7.下一个周期，d[a]又可以更新为更小的值，这个过程永远不会终止。因此，在迭代求解最短路径阶段结束后，可以通过检验边集E的每条边(u,v)是否满足关系式 d[v]& d[u]+ w(u,v) 来判断是否存在负权回路。
伪代码
-------------------PASCAL------------
For i:=1 to |V|-1 do
For 每条边(u,v)∈E do
Relax(u,v,w);
For每条边(u,v)∈E do
If dis[u]+w&dis[v] Then Exit(False)
-----------------C&C++--------------
Bellman-Ford(G,w,s) ：boolean //图G ，边集 函数 w ，s为源点
1 for each vertex v ∈ V（G） do //初始化 1阶段
2 d[v] ←+∞
3 d[s] ←0; //1阶段结束
4 for i=1 to |v|-1 do //2阶段开始，双重循环。
5 for each edge（u,v） ∈E(G) do //要用到，穷举每条边。
6 If d[v]& d[u]+ w(u,v) then //松弛判断
7 d[v]=d[u]+w(u,v) //松弛操作 2阶段结束
8 for each edge（u,v） ∈E(G) do
9 If d[v]& d[u]+ w(u,v) then
10 Exit false
11 Exit true
时空复杂度
算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，仍不失为一个很实用的算法。
参考代码
----------------PASCAL-----------------
{单源最短路径的Bellman-ford算法
执行v-1次，每次对每条边进行
如有负权回路则输出&Error&
maxn=100;
maxe=maxn*(maxn-1)div 2;
edge=record
a,b,w :
edges :array[1..maxe]
dis :array[1..maxn]
pre :array[1..maxn]
e,n,s :
assign(input,'g.in');reset(input);
readln(n,s);
while not eof do
inc(e);
with edges[e] do readln(a,b,w);
(dis,sizeof(dis),$7f);//$7f是什么，解释替换 $7f 是127 $在pascal中代表后面的数是16进制
dis[s]:=0;pre[s]:=s;
procedure relax(u,v,w:integer);
if dis[u]+w&dis[v] then
dis[v]:=dis[u]+w;
pre[v]:=u;
function bellman_ford:
for i:=1 to n-1 do
for j:=1 to e do
with edges[j] do relax(a,b,w);
for i:=1 to e do
with edges[i] do
if dis[a]+w&dis[b] then exit(false);
exit(true)
procedure print_path(i:integer);
if pre[i]&&s then print_path(pre[i]);
write('--&',i)
for i:=1 to n do
write(i:3,':',dis[i]:3,':',s);
print_path(i);
writeln
{========main========}
if bellman_ford then show
else writeln('Error!!')
--------------------Matlab-------------
function ford(d,n,s) % d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2...,n），s为源点标号
for i=1:n %初始化dist，pre
dist(i)= %dist（i）为s，i之间的最短路的长度
pre(i)=NaN; %pre（i）为s到i的最短路上i的前一个顶点
dist(s)=0;
for k=1:n-1
for i=1:n %松弛操作
for j=1:n
if d(i,j)~=inf
if dist(j)&dist(i)+d(i,j)
dist(j)=dist(i)+d(i,j);
pre(j)=i;
for i=1:n
for j=1:n
if d(i,j)~=inf
if dist(i)+d(i,j)&dist(j)%判断有无负权回路
error('negetive weight circut');
Bellman-Ford算法 -
引申：SPFA算法
算法简介
(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
Bellman-Ford算法 -
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
算法代码
Procedure SPFA;
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do begin
u:=dequeue(Q);
for each v∈adj[u] do begin
tmp:=d[v];
relax(u,v);
if (tmp&&d[v]) and (not v in Q) then enqueue(v);
为本词条添加和相关影像
互动百科的词条（含所附图片）系由网友上传，如果涉嫌侵权，请与客服联系，我们将按照法律之相关规定及时进行处理。未经许可，禁止商业网站等复制、抓取本站内容；合理使用者，请注明来源于。
登录后使用互动百科的服务，将会得到个性化的提示和帮助，还有机会和专业认证智愿者沟通。
您也可以使用以下网站账号登录：
此词条还可添加&
编辑次数：5次
参与编辑人数：5位
最近更新时间： 20:07:54
贡献光荣榜工具类服务
编辑部专用服务
作者专用服务
Dijkstra算法和Bellman-Ford算法生成印尼文本摘要的比较
自动文本摘要是一种基于计算机的系统,它概括文本的同时保留文章的主题.在获取摘要过程中,用句子间的权重给每个段落建立句子的图谱;同时也考虑印尼文章段落结构的归纳演绎方法,用最短路径算法确定哪些句子部分将成为摘要的结果.实验结果表明,Dijkstra算法优于Bellman-Ford算法生成文本摘要压缩率的12%.
Abstract：
Automated Text Summarization is a computer-based system to perform text summarization that still keeps the main subject of the article.In the summarization process,we use weight of sentence,and build a graph of sentences in every paragraph.We also consider the inductive-deductive method in paragraph structure in Indone-sian articles.We use shortest part algorithm to determine which sentences will become results of summarization.In this paper,we will compare the results of summarization with Dijkstra and bellman-ford algorithms.The experi-mental result shows that Dijkstra give the better compression rate by 12%.
作者单位：
江西警察学院,江西 南昌,330100
年，卷(期)：
Keywords：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社单源最短路径问题分析--Dijkstra算法&Bellman_Ford算法
一：概念介绍
单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。形象点，如下图，假如有4个城镇A，B，C，D，它们之间有道路连通，且有长度。现在给定城镇A，求分别到其他城镇B，C，D的最短距离。正如下图，
A到B，C，D的最短路径为：
A--B--C 25
A--B--D 30
1）最短路径的最优子结构性质
该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。
假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<p(i,j)。则与p(i,j)是从i到j的最短路径相矛盾。因此该性质得证。
2）Dijkstra算法
由上述性质可知，如果存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路，
假设存在G=，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。
1.从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；
2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})
3.知道U=V，停止。
//dist[i]记录源顶点到i的最短距离
//path[i]记录从源顶点到i路径上的i前面的一个顶点
struct Graph
int matrix[10][10];
//邻接矩阵
int vertexN
void Dijkstra(Graph & graph, int & source);
void ShowPath(Graph & graph, int & source, int v);
int main()
memset(graph.matrix, 0, sizeof(graph.matrix));
cout && &请输入图的顶点数和边数:\n&;
cin && graph.vertexNum && graph.sideN//输入顶点数和边数
dist = new int[graph.vertexNum];//内存申请
path = new int[graph.vertexNum];
cout && &请输入边的关系和权值:\n&;
for (int i = 0; i & graph.sideN i++)
cin && x && y &&//输入边的关系和权值
graph.matrix[x][y] =
graph.matrix[y][x] =
cout && &\n请输入源顶点:\n&;
cin &&//输入源顶点
Dijkstra(graph, source);//求出源顶点source到其他顶点的最短路径
for (int i = 0; i & graph.vertexN i++)
if (i != source)
ShowPath(graph, source, i);//输出源顶点source到其他顶点i的最短路径
最短路径长度为：& && dist[i] &&
void Dijkstra(Graph & graph, int & source)
bool* visited = new bool[graph.vertexNum];
path[source] =
dist[source] = 0;
for (int i = 0; i & graph.vertexN i++)//初始化dist,path,visited数组
visited[i] =
if (graph.matrix[source][i]&0 && i != source)//若源顶点source与i直接邻接
dist[i] = graph.matrix[source][i];
else//若不是直接邻接，dist置为无穷大
dist[i] = INT_MAX;
path[i] = -1;
visited[source] =
for (int i = 0; i & graph.vertexNum - 1; i++)//找出除source外剩下的点的最短路径
int min = INT_MAX;
for (int j = 0; j & graph.vertexN j++)//找到权值最小的点
if (!visited[j] && dist[j] & min)
min = dist[j];
visited[minPos] =
for (int k = 0; k & graph.vertexN k++)//更新dist数组，路径的值
if (!visited[k] && graph.matrix[minPos][k]&0 && graph.matrix[minPos][k] + min & dist[k])
dist[k] = graph.matrix[minPos][k] +
path[k] = minP
void ShowPath(Graph & graph, int & source, int v)
cout && &顶点 & && source && & 到顶点 & && v && & 的最短路径是： &;
while (source != v)
s.push(v);
v = path[v];
while (!s.empty())
cout && &--& && s.top();
三：数据测试
输入数据构建下图：
输出结果：
仔细思考发现上述的Dijkstra算法有个巨大的缺陷，就是图中的边不能有负权。因为当权值可以为负时，可能在图中会存在负权回路，最短路径只要无限次地走这个负权回路，便可以无限制地减少它的最短路径权值，这就变相地说明最短路径不存在，Dijkstra算法无法终止。下图说明从u到v的最短路径是不存在的。那么，应该用什么方法求解？
上面我们说Dijkstra算法无法终止，我们可能会想，可不可以试图让Dijkstra算法终止呢？当Dijkstra算法运行时，突然找到了一个负权回路，这下糟糕做不下去了，那么赶快终止算法跳出循环，报告给我们：我找到了负权回路。这个想法是很好的，但是如何判断碰到负权回路是个问题，读者有兴趣可以去实践一下。为了处理存在负权边的情况，我们采用另外一种非常著名的方法：Bellman_Ford算法。
五：Bellman_Ford算法讲解
Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德?贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特?福特（Lester Ford）发明。
Bellman-Ford算法的流程如下：
给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；以下操作循环执行至多n-1次，n为顶点数：对于每一条边e(u, v)，如果Distant[u] + w(u, v) & Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) & Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E)。
代码如下：
#define MAX 10000
//假设权值最大不超过10000
struct Edge
//所有边的集合
//dist[i]记录源顶点到i的最短距离
//path[i]记录从源顶点到i路径上的i前面的一个顶点
bool BellmanFord()
for (int i = 0; i & nodeN i++)
dist[i] = (i == original) ? 0 : MAX;
for (int i = 1; i &= nodeNum - 1; i++)
for (int j = 0; j & edgeN j++)
if (dist[edge[j].v]&dist[edge[j].u] + edge[j].weight)
dist[edge[j].v] = dist[edge[j].u] + edge[j].
path[edge[j].v] = edge[j].u;
bool flag =//标记是否有负权回路
for (int i = 0; i & edgeN i++)//判断是否有负权回路
if (dist[edge[i].v]&dist[edge[i].u] + edge[i].weight)
void Print()
for (int i = 0; i & nodeN i++)
if (i != original)
cout && &顶点 & && original && & 到顶点 & && p && & 的最短路径是： &;
while (original != p)
s.push(p);
p = path[p];
while (!s.empty())
cout && &--& && s.top();
最短路径长度是：& && dist[i] &&
int main()
------------case 1:
-----------case 2:
cout && &请输入图的顶点数，边数，源点：&;
cin && nodeNum && edgeNum &&
dist = new int[nodeNum];
path = new int[nodeNum];
edge = new Edge[edgeNum];
cout && &请输入& && edgeNum && &条边的信息：\n&;
for (int i = 0; i & edgeN i++)
cin && edge[i].u && edge[i].v && edge[i].
if (BellmanFord())
cout && &Sorry,it have negative circle!\n&;
两组数据测试如下图：
</p(i,j)。则与p(i,j)是从i到j的最短路径相矛盾。因此该性质得证。
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'}
添加标签来管理你的收藏
选择标签：
删除提示：
删除收藏标签，该标签下的内容将自动移至未加标签收藏中，确认要删除该标签吗？
确定要取消收藏吗？
关注成功！
关注精选邮箱：
尚未设置接收邮箱
取消关注后，将无法收到该知识库相关的知识动态和关注周报哦！确定要取消本知识库的关注吗？
技术领域：<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
您的访问请求被拒绝 403 Forbidden - ITeye技术社区
您的访问请求被拒绝
亲爱的会员，您的IP地址所在网段被ITeye拒绝服务，这可能是以下两种情况导致：
一、您所在的网段内有网络爬虫大量抓取ITeye网页，为保证其他人流畅的访问ITeye，该网段被ITeye拒绝
二、您通过某个代理服务器访问ITeye网站，该代理服务器被网络爬虫利用，大量抓取ITeye网页
请您点击按钮解除封锁&Bellman-Ford算法 -
&Bellman-Ford算法&
中不允许边的权是负权，如果遇到负权，则可以采用Bellman-Ford算法。
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s， w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。
适用条件&范围
1.(从源点s到其它所有顶点v);
2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
3.边权可正可负(如有负权回路输出错误提示);
Bellman-Ford算法描述：
1,.初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;
2.迭代求解：反复对边集E中的每条边进行，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
描述性证明：
首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。
在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。
每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）
如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。
如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。
例如对于上图，边上方框中的数字代表权值，顶点A,B,C之间存在负权回路。S是源点，顶点中数字表示运行Bellman-Ford算法后各点的最短距离估计值。
此时d[a]的值为1，大于d[c]+w(c,a)的值-2，由此d[a]可以松弛为-2，然后d又可以松弛为-5,d[c]又可以松弛为-7.下一个周期，d[a]又可以更新为更小的值，这个过程永远不会终止。因此，在迭代求解最短路径阶段结束后，可以通过检验边集E的每条边(u,v)是否满足关系式 d[v]& d[u]+ w(u,v) 来判断是否存在负权回路。
伪代码
-------------------PASCAL------------
For i:=1 to |V|-1 do
For 每条边(u,v)∈E do
Relax(u,v,w);
For每条边(u,v)∈E do
If dis[u]+w&dis[v] Then Exit(False)
-----------------C&C++--------------
Bellman-Ford(G,w,s) ：boolean //图G ，边集 函数 w ，s为源点
1 for each vertex v ∈ V（G） do //初始化 1阶段
2 d[v] ←+∞
3 d[s] ←0; //1阶段结束
4 for i=1 to |v|-1 do //2阶段开始，双重循环。
5 for each edge（u,v） ∈E(G) do //要用到，穷举每条边。
6 If d[v]& d[u]+ w(u,v) then //松弛判断
7 d[v]=d[u]+w(u,v) //松弛操作 2阶段结束
8 for each edge（u,v） ∈E(G) do
9 If d[v]& d[u]+ w(u,v) then
10 Exit false
11 Exit true
时空复杂度
算法时间复杂度O(VE)。因为算法简单，适用范围又广，虽然复杂度稍高，仍不失为一个很实用的算法。
参考代码
----------------PASCAL-----------------
{单源最短路径的Bellman-ford算法
执行v-1次，每次对每条边进行
如有负权回路则输出&Error&
maxn=100;
maxe=maxn*(maxn-1)div 2;
edge=record
a,b,w :
edges :array[1..maxe]
dis :array[1..maxn]
pre :array[1..maxn]
e,n,s :
assign(input,'g.in');reset(input);
readln(n,s);
while not eof do
inc(e);
with edges[e] do readln(a,b,w);
(dis,sizeof(dis),$7f);//$7f是什么，解释替换 $7f 是127 $在pascal中代表后面的数是16进制
dis[s]:=0;pre[s]:=s;
procedure relax(u,v,w:integer);
if dis[u]+w&dis[v] then
dis[v]:=dis[u]+w;
pre[v]:=u;
function bellman_ford:
for i:=1 to n-1 do
for j:=1 to e do
with edges[j] do relax(a,b,w);
for i:=1 to e do
with edges[i] do
if dis[a]+w&dis[b] then exit(false);
exit(true)
procedure print_path(i:integer);
if pre[i]&&s then print_path(pre[i]);
write('--&',i)
for i:=1 to n do
write(i:3,':',dis[i]:3,':',s);
print_path(i);
writeln
{========main========}
if bellman_ford then show
else writeln('Error!!')
--------------------Matlab-------------
function ford(d,n,s) % d为已知图的邻接矩阵，n为顶点数（各顶点标号为1，2...,n），s为源点标号
for i=1:n %初始化dist，pre
dist(i)= %dist（i）为s，i之间的最短路的长度
pre(i)=NaN; %pre（i）为s到i的最短路上i的前一个顶点
dist(s)=0;
for k=1:n-1
for i=1:n %松弛操作
for j=1:n
if d(i,j)~=inf
if dist(j)&dist(i)+d(i,j)
dist(j)=dist(i)+d(i,j);
pre(j)=i;
for i=1:n
for j=1:n
if d(i,j)~=inf
if dist(i)+d(i,j)&dist(j)%判断有无负权回路
error('negetive weight circut');
Bellman-Ford算法 -
引申：SPFA算法
算法简介
(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
Bellman-Ford算法 -
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
算法代码
Procedure SPFA;
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do begin
u:=dequeue(Q);
for each v∈adj[u] do begin
tmp:=d[v];
relax(u,v);
if (tmp&&d[v]) and (not v in Q) then enqueue(v);
为本词条添加和相关影像
互动百科的词条（含所附图片）系由网友上传，如果涉嫌侵权，请与客服联系，我们将按照法律之相关规定及时进行处理。未经许可，禁止商业网站等复制、抓取本站内容；合理使用者，请注明来源于。
登录后使用互动百科的服务，将会得到个性化的提示和帮助，还有机会和专业认证智愿者沟通。
您也可以使用以下网站账号登录：
此词条还可添加&
编辑次数：5次
参与编辑人数：5位
最近更新时间： 20:07:54
贡献光荣榜工具类服务
编辑部专用服务
作者专用服务
Dijkstra算法和Bellman-Ford算法生成印尼文本摘要的比较
自动文本摘要是一种基于计算机的系统,它概括文本的同时保留文章的主题.在获取摘要过程中,用句子间的权重给每个段落建立句子的图谱;同时也考虑印尼文章段落结构的归纳演绎方法,用最短路径算法确定哪些句子部分将成为摘要的结果.实验结果表明,Dijkstra算法优于Bellman-Ford算法生成文本摘要压缩率的12%.
Abstract：
Automated Text Summarization is a computer-based system to perform text summarization that still keeps the main subject of the article.In the summarization process,we use weight of sentence,and build a graph of sentences in every paragraph.We also consider the inductive-deductive method in paragraph structure in Indone-sian articles.We use shortest part algorithm to determine which sentences will become results of summarization.In this paper,we will compare the results of summarization with Dijkstra and bellman-ford algorithms.The experi-mental result shows that Dijkstra give the better compression rate by 12%.
作者单位：
江西警察学院,江西 南昌,330100
年，卷(期)：
Keywords：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社单源最短路径问题分析--Dijkstra算法&Bellman_Ford算法
一：概念介绍
单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。形象点，如下图，假如有4个城镇A，B，C，D，它们之间有道路连通，且有长度。现在给定城镇A，求分别到其他城镇B，C，D的最短距离。正如下图，
A到B，C，D的最短路径为：
A--B--C 25
A--B--D 30
1）最短路径的最优子结构性质
该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。
假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<p(i,j)。则与p(i,j)是从i到j的最短路径相矛盾。因此该性质得证。
2）Dijkstra算法
由上述性质可知，如果存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路，
假设存在G=，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。
1.从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；
2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})
3.知道U=V，停止。
//dist[i]记录源顶点到i的最短距离
//path[i]记录从源顶点到i路径上的i前面的一个顶点
struct Graph
int matrix[10][10];
//邻接矩阵
int vertexN
void Dijkstra(Graph & graph, int & source);
void ShowPath(Graph & graph, int & source, int v);
int main()
memset(graph.matrix, 0, sizeof(graph.matrix));
cout && &请输入图的顶点数和边数:\n&;
cin && graph.vertexNum && graph.sideN//输入顶点数和边数
dist = new int[graph.vertexNum];//内存申请
path = new int[graph.vertexNum];
cout && &请输入边的关系和权值:\n&;
for (int i = 0; i & graph.sideN i++)
cin && x && y &&//输入边的关系和权值
graph.matrix[x][y] =
graph.matrix[y][x] =
cout && &\n请输入源顶点:\n&;
cin &&//输入源顶点
Dijkstra(graph, source);//求出源顶点source到其他顶点的最短路径
for (int i = 0; i & graph.vertexN i++)
if (i != source)
ShowPath(graph, source, i);//输出源顶点source到其他顶点i的最短路径
最短路径长度为：& && dist[i] &&
void Dijkstra(Graph & graph, int & source)
bool* visited = new bool[graph.vertexNum];
path[source] =
dist[source] = 0;
for (int i = 0; i & graph.vertexN i++)//初始化dist,path,visited数组
visited[i] =
if (graph.matrix[source][i]&0 && i != source)//若源顶点source与i直接邻接
dist[i] = graph.matrix[source][i];
else//若不是直接邻接，dist置为无穷大
dist[i] = INT_MAX;
path[i] = -1;
visited[source] =
for (int i = 0; i & graph.vertexNum - 1; i++)//找出除source外剩下的点的最短路径
int min = INT_MAX;
for (int j = 0; j & graph.vertexN j++)//找到权值最小的点
if (!visited[j] && dist[j] & min)
min = dist[j];
visited[minPos] =
for (int k = 0; k & graph.vertexN k++)//更新dist数组，路径的值
if (!visited[k] && graph.matrix[minPos][k]&0 && graph.matrix[minPos][k] + min & dist[k])
dist[k] = graph.matrix[minPos][k] +
path[k] = minP
void ShowPath(Graph & graph, int & source, int v)
cout && &顶点 & && source && & 到顶点 & && v && & 的最短路径是： &;
while (source != v)
s.push(v);
v = path[v];
while (!s.empty())
cout && &--& && s.top();
三：数据测试
输入数据构建下图：
输出结果：
仔细思考发现上述的Dijkstra算法有个巨大的缺陷，就是图中的边不能有负权。因为当权值可以为负时，可能在图中会存在负权回路，最短路径只要无限次地走这个负权回路，便可以无限制地减少它的最短路径权值，这就变相地说明最短路径不存在，Dijkstra算法无法终止。下图说明从u到v的最短路径是不存在的。那么，应该用什么方法求解？
上面我们说Dijkstra算法无法终止，我们可能会想，可不可以试图让Dijkstra算法终止呢？当Dijkstra算法运行时，突然找到了一个负权回路，这下糟糕做不下去了，那么赶快终止算法跳出循环，报告给我们：我找到了负权回路。这个想法是很好的，但是如何判断碰到负权回路是个问题，读者有兴趣可以去实践一下。为了处理存在负权边的情况，我们采用另外一种非常著名的方法：Bellman_Ford算法。
五：Bellman_Ford算法讲解
Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德?贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特?福特（Lester Ford）发明。
Bellman-Ford算法的流程如下：
给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；以下操作循环执行至多n-1次，n为顶点数：对于每一条边e(u, v)，如果Distant[u] + w(u, v) & Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) & Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E)。
代码如下：
#define MAX 10000
//假设权值最大不超过10000
struct Edge
//所有边的集合
//dist[i]记录源顶点到i的最短距离
//path[i]记录从源顶点到i路径上的i前面的一个顶点
bool BellmanFord()
for (int i = 0; i & nodeN i++)
dist[i] = (i == original) ? 0 : MAX;
for (int i = 1; i &= nodeNum - 1; i++)
for (int j = 0; j & edgeN j++)
if (dist[edge[j].v]&dist[edge[j].u] + edge[j].weight)
dist[edge[j].v] = dist[edge[j].u] + edge[j].
path[edge[j].v] = edge[j].u;
bool flag =//标记是否有负权回路
for (int i = 0; i & edgeN i++)//判断是否有负权回路
if (dist[edge[i].v]&dist[edge[i].u] + edge[i].weight)
void Print()
for (int i = 0; i & nodeN i++)
if (i != original)
cout && &顶点 & && original && & 到顶点 & && p && & 的最短路径是： &;
while (original != p)
s.push(p);
p = path[p];
while (!s.empty())
cout && &--& && s.top();
最短路径长度是：& && dist[i] &&
int main()
------------case 1:
-----------case 2:
cout && &请输入图的顶点数，边数，源点：&;
cin && nodeNum && edgeNum &&
dist = new int[nodeNum];
path = new int[nodeNum];
edge = new Edge[edgeNum];
cout && &请输入& && edgeNum && &条边的信息：\n&;
for (int i = 0; i & edgeN i++)
cin && edge[i].u && edge[i].v && edge[i].
if (BellmanFord())
cout && &Sorry,it have negative circle!\n&;
两组数据测试如下图：
</p(i,j)。则与p(i,j)是从i到j的最短路径相矛盾。因此该性质得证。
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'}
我要回帖
更多关于 bellmanford 的文章
更多推荐
- ·战争艺术自走棋下载赤潮自走棋超高胜率卡组阵容怎么搭配_自走棋超高胜率卡组阵容推荐
- ·《阿玛拉王国惩罚中武器等级怎么看:惩罚》如何重置加点
- ·幻想纹章2.2最强人物1.4隐藏人物怎么解锁
- ·在优玩电竞平台官网客服圈，请问达‏尔优A980PROMAX的认可度怎样？
- ·杭州游戏开发公司有哪些哪家游戏公司值得去工作？
- ·财务管理实训报告十九题怎么做。
- ·Cheinaweiweiyixoa
- ·用西红柿和黄瓜的故事和高脚杯和期盼编写故事
- ·我的孩子是个残疾人的不便孩子，今年上大一，因为行动不便得到学校专业的调剂和床位的特殊安排，想写信致谢，
- ·60001-50定额自考哪一个专业容易考业
- ·做跃层，别墅挑空要不要改隔层中间打水泥隔层，20平米左右，施工和材料费大概共需要多少银两？
- ·怎么自考本科多少钱学历
- ·320x1.74怎么样2.9x0.39验算丶竖式
- ·75kw柴油发电机油耗组喷油嘴拆卸注意什么事项？
- ·护理过满月宝宝肚脐怎么护理水平面怎么画
- ·徐悲鸿十二生肖景泰蓝栩栩如生 比喻的是什么生肖？
- ·如何对心血管重症监护室探视时间病房家属解释探视制度
- ·请大家分析下，这大家是什么意思晶体管？
- ·公卫执业医师资格分数成绩何时出15
- ·杨紫家有儿女剧照有白血病?
- ·dijkstra算法与bellmanford-ford结果一样吗
- ·2.6米阳台移门几扇高2.29宽2.64做几扇门好，做上亮子好还是不做好？
- ·这句话的详细解析 越详细越好 英文
- ·郑大一附院网上预约有互助献血小板的吗
- ·求助一道关于正定矩阵的如何证明矩阵半正定题
- ·我有一个表姐在大学读的是金融，现在的工作每天一堂金融课和股票打交道
- ·2016蒙古国大选人民银行2016年业务操作岗招聘报名方式是怎样的
- ·作者写了萧邦快乐钻石女表特点故居哪些方面分别有啥特点
- ·北京市中学生学籍号的学籍号能改吗
- ·BBU和RRU有什么是rru拉远区别，都有什么是rru拉远作用
- ·艾美达贝朗输液泵说明书使用说明书
- ·一年中第三人称单数是什么最大的两个是什么
- ·右侧缺血性股骨头坏死死北京年轮能治疗吗,想去这个医
- ·火灾报警控制器型号的屏蔽状态是否受复位操作影响
- ·太河水库移民安置政策驾校优惠政策
- ·俗语说的“姑姑用用的乱动”中的“雇佣合同怎么写”怎么写
