http://hi.baidu.com/11magic/home
http://hi.baidu.com/zhaicong123/home
http://www.cnblogs.com/gzydn/
基础代码--数据结构
2009年10月22日 星期四 20:44
·栈:表达式求值
·队列、循环队列
·并查集
·串的相关运算(基本函数,KMP算法)
·散列表(hash排序,处理冲突)
·链表
·二叉树(遍历,赫夫曼树,最近公共祖先)
1.并查集
并查集主要操作:1.合并两个不相交的集合 2.判断两元素是否属于同一个集合 3.路径压缩
Program DisJointSets;{路径压缩的并查集}
Const maxn=10000;
Var
a,b,i,n,m,p:longint;
father:array[0..maxn]of longint;
Function getfather(i:longint):longint;
Begin
if father[i]=i then exit(i);
father[i]:=getfather(father[i]);{路径压缩}
exit(father[i]);
End;
Procedure join(a,b:longint);
Var
x,y:longint;
Begin
x:=getfather(a);
y:=getfather(b);
if x<>y then father[x]:=y;{注意不是father[a]:=b}
End;
Begin
readln(n,m,p);
for i:=1 to n do father[i]:=i;{初始化并查集}
for i:=1 to m do
begin
readln(a,b);
join(a,b);
end;
for i:=1 to p do
begin
readln(a,b);
if getfather(a)=getfather(b) then writeln('Yes') else writeln('No');
end;
End.
2.KMP算法
处理子串匹配与记录位置过程:首先对匹配串B串进行预处理(Pretreatment),得到P[j]数组,表示当匹配到B数组的第j个字母时而j+1个字母不能匹配了,新的j最大值是多少。即P[j]是满足B[1..P[j]]=B[j-P[j]+1..j]的最大值,也可以将P[j]理解为当下一位无法匹配是,起点指针应向后移几位。或者说,当满足B[1..P[j]]=B[j-P[j]+1..j]的最大值P[j]是起点可以移动的最大值。
Program KMP;
Const
maxn=1000;
Var
i,j,m,n:longint;
a,b:string;
p:array[0..maxn]of longint;
Procedure pretreatment;
Var
i,j:longint;
Begin
p[1]:=0;
j:=0;
for i:=2 to m do
begin
while (j>0)and(b[j+1]<>b[i]) do j:=p[j];
if b[j+1]=b[i] then inc(j);
p[i]:=j;
end;
End;
Begin
readln(a);readln(b);
n:=length(a);m:=length(b);
fillchar(p,sizeof(p),0);
pretreatment;
j:=0;
for i:=1 to n do
begin
while (j>0)and(b[j+1]<>a[i]) do j:=p[j];
if b[j+1]=a[i] then inc(j);
if j=m then
begin
writeln('Patten occurs with shift:',i-m+1);{找到一个匹配点}
j:=p[j];
end;
end;
End.
3.康托展开
X=a[1]*n!+a[2]*(n-1)!+...+a[n]*1!(从左往右编号1..n)
其中a[i]表示从i..1中比num[i]小的数字的个数。
Function ct(p:arr):longint;
Var
i,j,t,ans:longint;
Begin
for i:=1 to n-1 do
begin
t:=0;
for j:=2 to n do
if p[j]
0 then dis[i]:=a[1,i] else dis[i]:=maxlongint;
dis[1]:=0;
cost:=0;
for t:=1 to n-1 do
begin
min:=maxlongint;k:=0;
for i:=1 to n do
if (dis[i]<>0)and(dis[i]0)and(dis[i]>a[k,i]) then
begin
dis[i]:=a[k,i];
closest[i]:=k;
end;
end;
End;
2. Kruskal算法
思路:将边从小到大排序,依次枚举排序后每条边,判断边的2个顶点是否属于同一个集合,如果不是,就将两顶点集合运用并查集合并。
Function getfather(i:longint):longint;
Begin
if father[i]<>i then
father[i]:=getfather(father[i]);
exit(father[i]);
End;
Procedure kruskal;
Var
t1,t2:longint;
Begin
for i:=1 to n do
father[i]:=i;
qs(1,m);
for i:=1 to m do
begin
t1:=getfather(e[i].v1);
t2:=getfather(e[i].v2);
if t1<>t2 then
begin
father[t1]:=t2;
inc(cost,e[i].s);
end;
end;
End;
基础代码--最短路径SPFA算法
图论常用算法--最短路径4 SPFA算法
2010-02-07 14:49
算法描述:
d[i]:=maxint,d[s]:=0; 边界条件
d[i]:=min{d[x],d[x]+w[x,i]}; 递推关系
BELLMAN中X取1 到 N ,SPFA中X 取 已更新的边的点
{SPFA本质上为BELLMAN的优化,BELLMAN是对所有的边做N-1次松弛操作,而SPFA只对更新后的路径做松弛操作}
{用队列来维护,与BFS相似,但SPFA一个顶点可重复入队,因为更新后的边可能再次更新其它边}
1) 数据结构:邻接矩阵
var g:array[1..50,1..50]of integer;
d,path:array[1..50]of integer;
2)算法实现:
procedure spfa(a:integer);
var q:array[1..50]of integer;
visted:array[1..50]of boolean;
head,tail:integer;
begin
for i:=1 to n do d[i]:=maxint div 2;d[a]:=0;path[a]:=a;
fillchar(q,sizeof(q),0); head:=0;tail:=0;
fillchar(visted,sizeof(visted),false);
inc(tail);q[tail]:=a;visted[a]:=true;
while head<>tail do
begin
head:=(head mod n)+1;x:=q[head];visted[x]:=false;
for i:=1 to n do
if (g[x,i]>0)and(d[x]+g[x,i]tail do
begin
head:=(head mod n)+1;x:=q[head];visted[x]:=false;
for i:=1 to n do
if (g[x,i]>0)and(d[x]+g[x,i]=v-1 then
begin writeln('Bad exist');halt;end;{表明存在负权边}
if not flag[ljb[t,i]] then
begin{入队}
rear:=rear mod maxn+1;
q[rear]:=ljb[t,i];
flag[ljb[t,i]]:=true;
end;
end;
head:=head mod maxn+1;
flag[t]:=false;{出队}
end;
End;
Procedure ouit;
Begin
for i:=2 to v do
writeln(1,'-->',i,' ',d[i]);
End;
Begin
assign(input,'dij.in');
reset(input);
init;
close(input);
spfa;
ouit;
End.
2010-07-29 11:41
求最短路径的算法有许多种,除了排序外,恐怕是OI界中解决同一类问题算法最多的了。最熟悉的无疑是Dijkstra,接着是Bellman-Ford,它们都可以求出由一个源点向其他各点的最短路径;如果我们想要求出每一对顶点之间的最短路径的话,还可以用Floyd-Warshall。
SPFA是这篇日志要写的一种算法,它的性能非常好,代码实现也并不复杂。特别是当图的规模大,用邻接矩阵存不下的时候,用SPFA则可以很方便地面对临接表。每个人都写过广搜,SPFA的实现和广搜非常相似。
如何求得最短路径的长度值?
首先说明,SPFA是一种单源最短路径算法,所以以下所说的“某点的最短路径长度”,指的是“某点到源点的最短路径长度”。
我们记源点为S,由源点到达点i的“当前最短路径”为D[i],开始时将所有D[i]初始化为无穷大,D[S]则初始化为0。算法所要做的,就是在运行过程中,不断尝试减小D[]数组的元素,最终将其中每一个元素减小到实际的最短路径。
过程中,我们要维护一个队列,开始时将源点置于队首,然后反复进行这样的操作,直到队列为空:
(1)从队首取出一个结点u,扫描所有由u结点可以一步到达的结点,具体的扫描过程,随存储方式的不同而不同;
(2)一旦发现有这样一个结点,记为v,满足D[v] > D[u] + w(u, v),则将D[v]的值减小,减小到和D[u] + w(u, v)相等。其中,w(u, v)为图中的边u-v的长度,由于u-v必相邻,所以这个长度一定已知(不然我们得到的也不叫一个完整的图);这种操作叫做松弛。
引用
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
松弛操作的原理是著名的定理:“三角形两边之和大于第三边”,在信息学中我们叫它三角不等式。所谓对i,j进行松弛,就是判定是否d[j]>d[i]+w[i,j],如果该式成立则将d[j]减小到d[i]+w[i,j],否则不动。
(3)上一步中,我们认为我们“改进了”结点v的最短路径,结点v的当前路径长度D[v]相比于以前减小了一些,于是,与v相连的一些结点的路径长度可能会相应地减小。注意,是可能,而不是一定。但即使如此,我们仍然要将v加入到队列中等待处理,以保证这些结点的路径值在算法结束时被降至最优。当然,如果连接至v的边较多,算法运行中,结点v的路径长度可能会多次被改进,如果我们因此而将v加入队列多次,后续的工作无疑是冗余的。这样,就需要我们维护一个bool数组Inqueue[],来记录每一个结点是否已经在队列中。我们仅将尚未加入队列的点加入队列。
算法能否结束?
对于不存在负权回路的图来说,上述算法是一定会结束的。因为算法在反复优化各个最短路径长度,总有一个时刻会进入“无法再优化”的局面,此时一旦队列读空,算法就结束了。然而,如果图中存在一条权值为负的回路,就糟糕了,算法会在其上反复运行,通过“绕圈”来无休止地试图减小某些相关点的最短路径值。假如我们不能保证图中没有负权回路,一种“结束条件”是必要的。这种结束条件是什么呢?
思考Bellman-Ford算法,它是如何结束的?显然,最朴素的Bellman-Ford算法不管循环过程中发生了什么,一概要循环|V|-1遍才肯结束。凭直觉我们可以感到,SPFA算法“更聪明一些”,就是说我们可以猜测,假如在SPFA中,一个点进入队列——或者说一个点被处理——超过了|V|次,那么就可以断定图中存在负权回路了。
最短路径本身怎么输出?
在一幅图中,我们仅仅知道结点A到结点E的最短路径长度是73,有时候意义不大。这附图如果是地图的模型的话,在算出最短路径长度后,我们总要说明“怎么走”才算真正解决了问题。如何在计算过程中记录下来最短路径是怎么走的,并在最后将它输出呢?
Path[]数组,Path[i]表示从S到i的最短路径中,结点i之前的结点的编号。注意,是“之前”,不是“之后”。最短路径算法的核心思想成为“松弛”,原理是三角形不等式,
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
是上文已经提及的。我们只需要在借助结点u对结点v进行松弛的同时,标记下Path[v] = u,记录的工作就完成了。
前面已经说到,Bellman-Ford存在大量的废运算,即使优化过仍是这样。SPFA作为Bellman-Ford的一个改进,尽可能地减少了废运算,从而提高了效率。
Bellman-Ford是枚举每条路径从而算出结果的,也就是一个点是否需要松弛依赖于其连接的点。SPFA的思想是用一个队列存放所有需要松弛的点,初始时队列中只有源点s,进行计算时,若队列为空则算法结束,否则将队首顶点取出后对其相邻的点基于取出地点进行松弛。如果某邻点松弛成功(改变了d中对应的值)并且那个点不在队列中,则将其入队。在进行以上操作时需要记录每个点进入队列的次数。如果有点进入队列超过|V|次则说明图存在负权回路,退出算法并返回false。
算法核心代码如下:(针对有向图,Pascal语言)
function spfa(s:longint):boolean;
var i,j,k,l,r:longint;
q:array[1..maxn*maxn] of longint;
f:array[1..maxn] of boolean;
t:array[1..maxn] of longint;
begin
l:=1;r:=1;q[1]:=s;fillchar(f,sizeof(f),false);f[s]:=true;
fillchar(t,sizeof(t),0);t[s]:=1;
for i:=1 to n do begin
d[i]:=100000000;
closest[i]:=-1;
end;
d[s]:=0;
while l<=r do begin
i:=q[l];inc(l);
for j:=1 to edge[i,0] do begin
k:=edge[i,j];
if (d[k]>d[i]+cost[i,k]) then begin
d[k]:=d[i]+cost[i,k];
closest[k]:=i;
if not f[k] then begin
f[k]:=true;
inc(t[k]);
if t[k]>n then exit(false);
inc(r);
q[r]:=k;
end;
end;
end;
f[i]:=false;
end;
exit(true);
end;
为了方便计算连到某个点的所有边,此处的edge数组用二维数组表示,edge[i,0]表示i的度(连到i的边数),edge[i,1..edge[i,0]]分别存放每一条边另一端的顶点。
这里的队列p长度n^2可能比较危险。事实上队列中元素的上限为n,完全可以滚动数组来把p的长度压为n,但是这样程序理解和实现起来可能会比较困难,所以入门时这样就行了。
SPFA的复杂度很难计算,一般公认为O(kE),k为常数。
三、Bellman-Ford、SPFA、朴素Dijkstra效率实测
评测环境:WindowsXP,FreePascal2.40,Pentium(R) Dual-Core CPU T4300@2.10GHz,2G内存
可以看出,SPFA是优于优化后的Bellman-Ford的,所以尽可能地用SPFA吧,记得滚动那个队列数组- -
关于Dijkstra,测试的那个程序是朴素的,也就是不含堆优化的。如果加了二叉堆优化是肯定会优于SPFA的。至于怎么优化请参看前一篇里Prim的优化,实质上是一样的……
附:SPFA的两个优化
转自http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=257702,作者zkw
SPFA与堆优化的Dijkstra的速度之争不是一天两天了,不过从这次USACO月赛题来看,SPFA用在分层图上会比较慢。标程是堆优化的Dijkstra,我写了一个非常朴素的SPFA,只能过6/11个点。SPFA是按照FIFO的
原则
组织架构调整原则组织架构设计原则组织架构设置原则财政预算编制原则问卷调查设计原则
更新距离的,没有考虑到距离标号的作用。实现中 SPFA 有两个非常著名的优化:SLF 和 LLL。
SLF:Small Label First 策略。
实现方法是,设队首元素为
,队列中要加入节点
,在
时加到队首而不是队尾,否则和普通的 SPFA 一样加到队尾。
LLL:Large Label Last 策略。
实现方法是,设队列
中的队首元素为
,距离标号的平均值为
,每次出队时,若
,把
移到队列末尾,如此反复,直到找到一个
使
,将其出队。
加上SLF优化后程序多了一行,过了9/11个点。你问我怎么用SPFA AC这个题?利用分层图性质,算完一层再算一层,对每一层计算用SPFA,加上上面的优化,程序飞快:最强的优化要利用题目的特殊性质。
类别:默认分类 |
| 添加到搜藏 | 分享到i贴吧 | 浏览(43) | 评论 (0)
上一篇:求含有负权边的图的单源最短路径... 下一篇:vijos p1210 盒子与球 stirling...
相关文章:
基础代码--最短路径
2009年10月26日 星期一 21:53
·Dijkstra算法求单源最短路
·Floyd算法求多源最短路
·SPFA算法
1. Dijkstra算法求单源最短路
基本思路:每次加入当前未确定最短路径的点中,到v0路径dis[i]最短的点,然后对其他未加入的点的路径进行更新,重复直到找不到这样的点为止。
注意点:时刻留意dis[i]为0的点,要么把他初始化设为一个很大的数,要么在程序中得时刻判断,建议使用前者。
代码:Program Shortest_Path_Dijkstra;
Const
maxn=100;
Var
n,e,i,j,v0:longint;
a:array[0..maxn,0..maxn]of longint;
dis,pre:array[0..maxn]of longint;
flag:array[0..maxn]of boolean;
Procedure init;
Var
x,y,d:longint;
Begin
readln(n);readln(e);
for i:=1 to n do
for j:=1 to n do
if i<>j then a[i,j]:=32000 else a[i,j]:=0;{ 给a[i,j]赋初值}
for i:=1 to e do
begin
readln(x,y,d);
a[x,y]:=d;a[y,x]:=d;
end;
End;
Procedure dijkstra(v0:longint);{千万要注意dis[i]=0 的点}
Var
min,minj:longint;
Begin
fillchar(dis,sizeof(dis),0);
fillchar(pre,sizeof(pre),0);
fillchar(flag,sizeof(flag),false);
flag[v0]:=true;
for i:=1 to n do
begin
dis[i]:=a[v0,i];
if dis[i]<>0 then pre[i]:=v0 else pre[i]:=0;
end;
repeat
min:=maxlongint;
minj:=0;
for j:=1 to n do
if (not flag[j])and(dis[j]0 then
begin
flag[minj]:=true;
for j:=1 to n do
if (not flag[j])and(dis[minj]+a[minj,j]0 then writeln(pre[i],' ',i);
for i:=1 to n do
if dis[i]<>0 then writeln(v0,'--->',i,':',dis[i]);
End;
Begin
assign(input,'dij.in');
assign(output,'dij.out');
reset(input);
rewrite(output);
init;
v0:=1;
dijkstra(v0);
ouit;
close(input);
close(output);
End.
Floyd算法求多源最短路
使用类似传递闭包的算法,进行增广。
Program Shortest_Path_Floyd;
Const
maxn=100;
Var
n,m,i,j,k:longint;
d,pre:array[0..maxn,0..maxn]of longint;
Procedure init;
Var
x,y,len:longint;
Begin
fillchar(d,sizeof(d),0);
fillchar(pre,sizeof(pre),0);
readln(n,m);
for i:=1 to n do
for j:=1 to n do
d[i,j]:=30000;
for i:=1 to m do
begin
readln(x,y,len);
d[x,y]:=len;
d[y,x]:=len;
pre[x,y]:=x;
pre[y,x]:=y;
end;{读入各边,并将pre数组初始化}
End;
Procedure floyd;{关键过程}
Begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if d[i,k]+d[k,j]',j);
end;
End;
Procedure ouit;
Begin
for i:=1 to n do
for j:=1 to n do
if i',j,':');
print(i,j);
writeln;
end;
End;
Begin
Assign(input,'floyd.in');
Assign(output,'floyd.out');
Reset(input);
Rewrite(output);
init;
floyd;
ouit;
Close(input);
Close(output);
End.
Dijkstra算法
Posted on 2009-07-09 17:19 YDN 阅读(3246) 评论(0) 编辑 收藏 所属分类: 树和图, 贪心
Dijkstra算法又称为单源最短路径,所谓单源是在一个有向图中,从一个顶点出发,求该顶点至所有可到达顶点的最短路径问题。
设G=(V,E)是一个有向图,V表示顶点,E表示边。它的每一条边(i,j)属于E,都有一个非负权W(I,j),在G中指定一个结点v0,要求把从v0到G的每一个接vj(vj属于V)的最短有向路径找出来(或者指出不存在)。
Dijstra算法是运用贪心的策略,从源点开始,不断地通过相联通的点找出到其他点的最短距离
基本思想是:
设置一个顶点的集合s,并不断地扩充这个集合,一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点,并且调整非s中点的最短路径长度,找当前最短路径点,将其加入到集合s,直到终点在s中。
基本步骤:
1、把所有结点分成两组:
第一组:包括已经确定最短路径的结点;
第二组:包括尚未确定最短路径的结点。
2、开始时,第一组只包含起点,第二组包含剩余的点;
3、用贪心的策略,按最短路径长度递增的顺序把第二组的结点加到第一组去,直到v0可达的所有结点都包含于第一组中。在这个过程中,不断更新最短路径,总保持从v0到第一组各结点的最短路径长度dist都不大于从v0到第二组任何结点的路径长度。
4、每个结点对应一个距离值,第一组结点对应的距离就是v0到此结点的最短路径长度,第二组结点对应的距离值就是v0由第一组结点到此结点的最短路径长度。
5、直到所有的顶点都扫描完毕(v0可达的所有结点都包含于第一组中),找到v0到其它各点的所有最短路径。
动画演示:http://www.jcc.jx.cn/kejiandb/Dijkstra.swf
如图:求0点到其他点的最短路径。
INCLUDEPICTURE "http://images.cnblogs.com/cnblogs_com/gzydn/dj2.jpg" \* MERGEFORMATINET
(1)开始时,s1={v0},s2={v1,v2,v3,v4},v0到各点的最短路径是{0,10,&,30,100};
(2)在还未进入s1的顶点之中,最短路径为v1,因此s1={v0,v1},由于v1到v2有路径,因此v0到各点的最短路径更新为{0,10,60,30,100};
(3)在还未进入s1的顶点之中,最短路径为v3,因此s1={v0,v1,v3},由于v3到v2、v4有路径,因此v0到各点的最短路径更新为{0,10,50,30,90};
(4)在还未进入s1的顶点之中,最短路径为v2,因此s1={v0,v1,v3,v2},由于v2到v4有路径,因此v0到各点的最短路径更新为{0,10,50,30,60};
数据结构:
(1)用一个二维数组a[i..j,i..j]来存储各点之间的距离,10000表示无通路:
(2)用数组dist[i..j]表示最短路径;
(3)用集合s表示找到最短路径的结点。
INCLUDEPICTURE "http://www.cnblogs.com/Images/OutliningIndicators/ExpandedBlockStart.gif" \* MERGEFORMATINET Code
1//单源最短路(dijkstra算法)
2program dijkstra;
3const max=10000; //表示无通路
4type jihe=set of 0..100; //顶点数
5var
6 a:array[0..100,0..100] of integer;//各点之间的距离
7 dist:array[0..100] of integer; //最短路径
8 i,j,k,m,n:integer;
9 s:jihe;
10
11procedure init;
12begin
13 s:=[0]; //开始集合只包含源点
14 readln(n);
15 assign(input,'dijs.in');reset(input);
16 for i:=0 to n do //读入各点之间的距离
17 for j:=0 to n do
18 read(a[i,j]);
19 for i:=0 to n do //源点到各点之间的直接距离
20 dist[i]:=a[0,i];
21end;
22
23procedure dijsk;
24begin
25 for i:=0 to n do
26 begin
27 m:=0;
28 dist[m]:=max; //初始化源点到各点的最小距离为无穷
29 for j:=1 to n do
30 if(not(j in s))and(dist[m]>dist[j]) then //找出当前的最小距离
31 m:=j; //记录找到的顶点
32 s:=s+[m]; //把顶点加入集合
33 for k:=0 to n do //更新经过新节点到其它点之间的最小距离
34 if(not(k in s))and(dist[k]>dist[m]+a[m,k]) then
35 dist[k]:=dist[m]+a[m,k];
36 end;
37end;
38
39begin
40 init;
41 dijsk;
42 for i:=1 to n do
43 writeln(i,':',dist[i]);
44 close(input);
45end.
Floyd最短路径算法
Posted on 2009-07-10 16:26 YDN 阅读(2762) 评论(0) 编辑 收藏 所属分类: 树和图
在图论中经常会遇到这样的问题,在一个有向图里,求出任意两个节点之间的最短距离。当节点之间的权值是正值的时候,我们可以采用Dijkstra算法,用贪心策略加于解决。但当节点之间的权值有负数的时候,Dijkstra就行不通了,这里介绍另外一种算法——Floyd最短路径算法。
问题描述:
如果有一个矩阵D=[d(ij)],其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通,那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序,通过这个距离矩阵D,把任意两个城市之间的最短路径找出来。
【
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
】
如何找出最短路径呢,这里需要用到动态规划的思想,对于任何一个城市而言,i 到 j 的最短距离不外乎存在经过 i 与 j 之间的k和不经过k两种可能,所以可以令k=1,2,3,...,n(n是城市的数目),再检查d(ij)与d(ik)+d(kj)的值;在此d(ik)与d(kj)分别是目前为止所知道的 i 到 k 与 k 到 j 的最短距离,因此d(ik)+d(kj)就是 i 到 j 经过k的最短距离。所以,若有d(ij)>d(ik)+d(kj),就表示从 i 出发经过 k 再到j的距离要比原来的 i 到 j 距离短,自然把i到j的d(ij)重写为d(ik)+d(kj)<这里就是动态规划中的决策>,每当一个k查完了,d(ij)就是目前的 i 到 j 的最短距离。重复这一过程,最后当查完所有的k时,d(ij)里面存放的就是 i 到 j 之间的最短距离了<这就是动态规划中的记忆化搜索>。利用一个三重循环产生一个存储每个结点最短距离的矩阵.
用三个for循环把问题解决了,但是有一个问题需要注意,那就是for循环的嵌套的顺序:我们可能随手就会写出这样的枚举程序,但是仔细考虑的话,会发现是有问题的:
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do
if.....
问题出在我们太早的把i-k-j的距离确定下来了,假设一旦找到了i-p-j最短的距离后,i到j就相当处理完了,以后不会在改变了,一旦以后有使i到j的更短的距离时也不能再去更新了,所以结果一定是不对的。所以应当象下面一样来写程序:
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if .....
这样作的意义在于固定了k,把所有i到j而经过k的距离找出来,然后象开头所提到的那样进行比较和重写,因为k是在最外层的,所以会把所有的i到j都处理完后,才会移动到下一个K。
【Floyd算法实例】
现有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权代表城市之间的距离。求每个城市的最短距离
【输入】 第一行两个数v,e,分别代表城市数和边数 以下e行,每行为两个顶点和它们之间的边权。
【输出】 所有可能连接的城市的最短距离。
【输入样例】
6 10
1 2 10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 6
4 5 18
4 6 14
5 6 33
【输出样例】
1 2 10
1 3 15
1 4 16
1 5 19
1 6 21
2 3 5
2 4 6
2 5 24
2 6 11
3 4 6
3 5 24
3 6 16
4 5 18
4 6 14
5 6 32
INCLUDEPICTURE "http://www.cnblogs.com/Images/OutliningIndicators/ExpandedBlockStart.gif" \* MERGEFORMATINET Code
1program floyd_example;
2const
3 maxn=10;
4var
5 n,s,t,i,j:integer;
6 dist:array[1..maxn,1..maxn] of real;
7 prev:array[1..maxn,1..maxn] of 0..maxn;
8procedure init;
9 var
10 m,i,u,v:integer;
11 begin
12 assign(input,'floyd.in');
13 reset(input);
14 assign(output,'floyd.out');
15 rewrite(output);
16 readln(n,m);
17 fillchar(prev,sizeof(prev),0);
18 for u:=1 to n do
19 for v:=1 to n do
20 dist[u,v]:=1e10;
21 for i:=1 to m do
22 begin
23 readln(u,v,dist[u,v]);
24 dist[v,u]:=dist[u,v];
25 prev[u,v]:=u;
26 prev[v,u]:=v;
27 end;
28 end;{init}
29procedure floyd;
30 var
31 i,j,k:integer;
32 begin
33 for k:=1 to n do
34 for i:=1 to n do
35 for j:=1 to n do
36 if (dist[i,k]+dist[k,j]
本文档为【最短路径算法-】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。