首页 > 代码库 > SPFA算法模板
SPFA算法模板
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.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。