发布网友 发布时间:2022-04-24 23:25
共1个回答
热心网友 时间:2023-10-14 11:18
SPFA实际上是Bellman-Ford基础上的队列优化
一种伪代码 Procere SPFA; Begin 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(Q,v); end; end;End;一种更容易读懂的伪代码: ProcereSPFA;Begin 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(Q,v); end; end;End;