SPFA 原理 pascal语言
program SPFA1(input,output);
var
used:array[1..100] of boolean;
line,len:array[1..100] of longint;
flat:array[1..100,1..100] of longint;
i,n,a,b:longint;
procedure SPFA(s:longint);
var
f,r,k:longint;
begin
f:=1;
r:=1;
line[f]:=s;
used[s]:=true;
for i:=1 to n do len[i]:=maxlongint;
len[s]:=0;
while f<=r do
begin
k:=line[f];
for i:=1 to n do
if len[i]>flat[k,i]+len[k] then
begin
len[i]:=flat[k,i]+len[k];
if used[i]=false then
begin
used[i]:=true;
inc(r);
line[r]:=k;
end;
end;
used[k]:=false;
inc(f);
end;
end;
begin
//assign(input,'SPFA.in');reset(input);
//assign(output,'SPFA.out');rewrite(output);
readln(n);
for i:=1 to n do
readln(a,b,flat[a,b]);
SPFA(4);
writeln(len[n]);
close(input);
close(output);
end.
这是SPFA，请采纳谢谢。
10^5那么小,广度优先遍历.
----13.1.21 upgrade------
本来不想写的,看到那位大哥说dp,实在觉得不贴对不起我这回答.
好吧说bfs算是我敷衍了.这个其实是spfa.这题其实可以看成图论.
var k,t,x,y,head,tail:longint;
queue,distant:array[1..100010]of longint;
hash:array[1..100010]of boolean;
begin
for i:=1 to 100010 do
distant[i]:=1000000;
readln(x,y);
distant[x]:=0;
queue[1]:=x;
hash[x]:=true;
head:=0;
tail:=1;
repeat
inc(head);
hash[head]:=false;
k:=distant[queue[head]];
if(queue[head]=y)then begin
writeln(k);
break;
end;
if(queue[head]>1)then begin
t:=queue[head]-1;
if(distant[t]>k+1)then begin
distant[t]:=k+1;
if(not hash[t])then begin
inc(tail);
queue[tail]:=t;
hash[t]:=true;
end;
end;
end;
if(queue[head]<100000)then begin
t:=queue[head]+1;
if(distant[t]>k+1)then begin
distant[t]:=k+1;
if(not hash[t])then begin
inc(tail);
queue[tail]:=t;
hash[t]:=true;
end;
end;
end;
if(queue[head]shl 1<=100000)then begin
t:=queue[head]shl 1;
if(distant[t]>k+1)then begin
distant[t]:=k+1;
if(not hash[t])then begin
inc(tail);
queue[tail]:=t;
hash[t]:=true;
end;
end;
end;
until head=tail;
end.
设Dist[I]代表S到I点的当前最短距离，Fa[I]代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist[S]=0，Fa全部为0。
维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。
每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。
SPFA在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右(怎么证明的作者也不知道)。
const maxl=maxlongint;
var
g:array[1..100,1..100]of shortint;
b:array[1..1000]of boolean;
h,dis:array[1..1000]of longint;
x,s,e,i,j:longint;
procedure inp;
begin
assign(input,'spfa.txt');reset(input);
readln(x,s,e);
for i:=1 to x do begin
for j:=1 to x do read(g[i,j]);
readln;
end;
for i:=1 to 1000 do dis[i]:=maxl;
fillchar(b,sizeof(b),false);
end;
procedure spfa;
var
head,tail:longint;
procedure relax(i:longint);
begin
if dis[i]>dis[h[head]]+g[h[head],i] then begin
if i=s then begin writeln('NO WAY');halt;end;
dis[i]:=dis[h[head]]+g[h[head],i];
if not b[i] then begin
inc(tail);
h[tail]:=i;
b[i]:=true;
end;
end;
end;
begin
head:=1;tail:=1;
h[1]:=s;
dis[s]:=0;
b[s]:=true;
repeat
for i:=1 to x do
if g[h[head],i]<>100 then relax(i);
b[h[head]]:=false;
inc(head);
until head>tail;
end;
begin
inp;
spfa;
writeln(dis[e]);
end.
？
const
maxp=10000; {最大结点数}
var {变量定义}
p,c,s,t:longint; {p,结点数;c,边数;s:起点;t:终点}
a,b:array[1..maxp,0..maxp] of longint; {a[x,y]存x,y之间边的权;b[x,c]存与x相连的第c个边的另一个结点y}
d:array[1..maxp] of integer; {队列}
v:array[1..maxp] of boolean; {是否入队的标记}
dist:array[1..maxp] of longint; {到起点的最短路}
head,tail:longint; {队首/队尾指针}
procedure init;
var i,x,y,z:longint;
begin
read(p,c);
for i := 1 to c do
begin
readln(x,y,z); {x,y:一条边的两个结点;z:这条边的权值}
inc(b[x,0]); b[x,b[x,0]] := y; a[x,y] := z; {b[x,0]：以x为一个结点的边的条数}
inc(b[y,0]); b[y,b[y,0]] := x; a[y,x] := z;
end;
readln(s,t); {读入起点与终点}
end;
procedure spfa(s:longint); {SPFA}
var i,j,now,sum:longint;
begin
fillchar(d,sizeof(d),0);
fillchar(v,sizeof(v),false);
for j := 1 to p do dist[j]:=maxlongint;
dist[s]:=0; v[s]:=true;d[1]:=s;{队列的初始状态,s为起点}
head:=1;tail:= 1;
while head<=tail do {队列不空}
begin
now:=d[head]; {取队首元素}
for i:=1 to b[now,0] do
if dist[b[now,i]]>dist[now]+a[now,b[now,i]] then
begin
dist[b[now,i]]:= dist[now]+a[now,b[now,i]]; {修改最短路}
if not v[b[now,i]] then {扩展结点入队}
begin
inc(tail);
d[tail] := b[now,i];
v[b[now,i]] := true;
end;
end;
v[now] := false; {释放结点}
inc(head); {出队}
end;
end;
procedure print;
begin
writeln(dist[t]);
end;
begin
init;
spfa(s);
print;
end.
如果从起点到点i的距离dist[i]从来没有被更新过，那么dist[i]就没有更新相连点的价值。
反过来说，只有Dist[i]被更新过，它才可能有更新其他点的价值，只要有可能，就更新试试。
看上去是一个很暴力的方法，但复杂度居然可以达到O(V+E)……其实我完全不知道复杂度为何这样低……
程序核心：
flag[st]=1;dist[st]=0; st代表单源最短路的源，就是起点
while (l<=r) do 当队列不为空
{
更新每一条与d[l]相连的边edge[i] for (i=……) relax(i);
d[l]已经更新完了，离开队伍 flag[d[l]]=0;l=l+1;
}
子程序：
procedure relax(k:longint);
{
注：第k条边的信息保存在s[k]（第k条边的起点），length[k]（长度），e[k]（终点）里。
if (dist[s[k]]+length[k]>=dist[e[k]]) then exit; 如果这条边没有更新价值，就离开
dist[s[k]]+length[k]:=dist[e[k]]; 更新边
if (flag[e[k]]=false) then { r=r+1; d[r]=e[k]; flag[e[k]]=true; } 如果被更新的点不在队列中，也就是说我们并没打算更新点e[k]（但是显然，经过这次relax操作之后，我们突然发现e[k]有了被更新的价值），那就把e[k]加入队列。
}
慕钩克托： SPFA——Shortest Path Faster Algorithm,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边.SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单: 设Dist[I]代表...
颍东区15858832296： 欧拉回路,SPFA算法PASCAL参考程序？
慕钩克托： 不是说女人贪钱!生下来时候是不贪的!当花惯了!没钱的日子就过不下去时候就会贪了!有钱的日子 才舒服!男人女人一样的!
颍东区15858832296： 求SPFA的Pascal代码 - ？
慕钩克托： SPFA 算法Var Q:array[1..10000] of longint; V:array[1..10000] of Boolean; Dist:array[1..10000] of longint; Cost:array[1..10000,1..10000] of longint; n,m,x,I,j,a,b,c,k,h,t:longint;Begin fillchar(q,sizeof(q),0); h:=0; t:=0; //队列 fillchar(v,sizeof(v),false); //v[i]...
颍东区15858832296： SPFA算法的PASCAL代码是什么?？
慕钩克托： spfa只是bellmanford的一种优化 话说你要是整noip的话ms用不到spfa,dijkstra和floyed就行了 spfa具体内容就是枚举每个入队的节点然后松弛操作 每个节点可重复入队,但是不能超过总节点个数,否则有负环 队列用循环队列实现代码自己看思路应该能写出来写不出来我再贴行不?
颍东区15858832296： spfa pascal程序 - ？
慕钩克托： //spfa(单元最短路径o(2e))const maxn=1000; maxm=100000; type point=^node; node=record next:point; data,value:longint; ...
颍东区15858832296： 求spfa算法+前向星优化的Pascal标程 - ？
慕钩克托： 上次回答的没有改成一维的实在不好意思,只要把权值也一起存在一个一维的数组中就可以啦 var first,next,en,w:array[1..10000] of longint;//前向星存储 dis:array[1..1000] of longint; h:array[1..1000] of longint; bo:array[1..1000] of boolean; x,y,z:...
颍东区15858832296： Pascal 语言是什么 - ？
慕钩克托： Pascal语言概述与预备知识 1 关于Turbo PascalPascal是一种计算机通用的高级程序设计语言.它由瑞士Niklaus Wirth教授于六十年代末设计并创立.以法国数学家命名的Pascal语言现已成为使用最广泛的基于DOS的语言之一,其主要特点有...
颍东区15858832296： 用spfa求最长路的pascal代码 - ？
慕钩克托： 例:Summer的兵力分布在各个星球上,现在需要把他们全部转移到某个星球上. Summer一共拥有N个星球(1~N),你要把这N个星球上的兵力转到第M个星球上.本来每个星球之间都有星际轨道...
颍东区15858832296： Pascal语言是什么 - ？
慕钩克托： Pascal是一种计算机通用的高级程序设计语言.Pascal的取名是为了纪念十七世纪法国著名哲学家和数学家Blaise Pascal.它由瑞士Niklaus Wirth教授于六十年代末设计并创立.Pascal语言语法严谨,层次分明,程序易写,具有很强的可读性,是第一个结构化的编程语言.
颍东区15858832296： 帕斯卡语言 是什么? - ？
慕钩克托： Pascal具有简洁的语法,结构化的程序结构.它是结构化编程语言,于70年代在ALGO今,在许多学校的计算机语言课上,的都是Pascal语言. Pascal是最早出现的结构化编程语言,具有丰富的数据类型和简洁灵活的操作语句,适于描述数值和非数值的问题. 正因为上述特点,Pascal语言可以被方便地用于描述各种算法与数据结构.尤其是对于程序设计的初学者,Pascal语言有益于培养良好的程序设计风格和习惯.IOI(国际奥林匹克信息学竞赛)把Pascal语言作为三种程序设计语言之一, NOI(全国奥林匹克信息学竞赛)把Pascal语言定为唯一提倡的程序设计语言,在大学中Pascal语言也常常被用作学习数据结构与算法的教学语言.
