ProcedureSPFA;
Begin
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
whilenotempty(Q)dobegin
u:=dequeue(Q);
foreachv∈adj[u]dobegin
tmp:=d[v];
relax(u,v);
if(tmp<>d[v])and(notvinQ)thenenqueue(Q,v);
end;
end;
End;

#include<iostream>
#include<deque>
#include<stack>
#include<vector>
usingnamespacestd;

constintMAXN=100;
constintINF=0x7FFFFFFF;

structedge
{
intto;
intweight;
};

vector<edge>adjmap[MAXN];//邻接表
boolin_queue[MAXN];//顶点是否在队列中
intin_sum[MAXN];//顶点入队次数
intdist[MAXN];//源点到各点的最短路径
intpath[MAXN];//存储到达i的前一个顶点
intnodesum;//顶点数
intedgesum;//边数

boolSPFA(intsource)
{
deque<int>dq;
inti,j,x,to;
for(i=1;i<=nodesum;i++)
{
in_sum[i]=0;
in_queue[i]=false;
dist[i]=INF;
path[i]=-1;
}
dq.push_back(source);
in_sum[source]++;
dist[source]=0;
in_queue[source]=true;
//初始化完成

while(!dq.empty())
{
x=dq.front();
dq.pop_front();
in_queue[x]=false;
for(i=0;i<adjmap[x].size();i++)
{
to=adjmap[x][i].to;
if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight))
{
dist[to]=dist[x]+adjmap[x][i].weight;
path[to]=x;
if(!in_queue[to])
{
in_queue[to]=true;
in_sum[to]++;
if(in_sum[to]==nodesum)
returnfalse;
if(!dq.empty())
{
if(dist[to]>dist[dq.front()])
dq.push_back(to);
else
dq.push_front(to);
}
else
dq.push_back(to);
}
}
}
}
returntrue;
}

voidPrint_Path(intx)
{
stack<int>s;
intw=x;
while(path[w]!=-1)
{
s.push(w);
w=path[w];
}
cout<<"顶点1到顶点"<<x<<"的最短路径长度为："<<dist[x]<<endl;
cout<<"所经过的路径为：1";
while(!s.empty())
{
cout<<s.top()<<"";
s.pop();
}
cout<<endl;
}

intmain()
{
inti,s,e,w;
edgetemp;
cout<<"输入顶点数和边数：";
cin>>nodesum>>edgesum;
for(i=1;i<=nodesum;i++)
adjmap[i].clear();//清空邻接表
for(i=1;i<=edgesum;i++)
{
cout<<"输入第"<<i<<"条边的起点、终点还有对应的权值：";
cin>>s>>e>>w;
temp.to=e;
temp.weight=w;
adjmap[s].push_back(temp);
}
if(SPFA(1))
{
for(i=2;i<=nodesum;i++)
Print_Path(i);
}
else
cout<<"图中存在负权回路"<<endl;
return0;
}

　const
　maxp=10000;{最大结点数}
　var{变量定义}
　p,c,s,t:longint;{p,结点数;c,边数;s:起点;t:终点}
　a,b:array[1..maxp,0..maxp]oflongint;{a[x,y]存x,y之间边的权;b[x,c]存与x相连的第c个边的另一个结点y}
　d:array[1..maxp]ofinteger;{队列}
　v:array[1..maxp]ofboolean;{是否入队的标记}
　dist:array[1..maxp]oflongint;{到起点的最短路}
　head,tail:longint;{队首/队尾指针}
　procedureinit;
　vari,x,y,z:longint;
　begin
　read(p,c);
　fori:=1tocdo
　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;
　procedurespfa(s:longint);{SPFA}
　vari,j,now,sum:longint;
　begin
　fillchar(d,sizeof(d),0);
　fillchar(v,sizeof(v),false);
　forj:=1topdodist[j]:=maxlongint;
　dist[s]:=0;v[s]:=true;d[1]:=s;{队列的初始状态,s为起点}
　head:=1;tail:=1;
　whilehead<=taildo{队列不空}
　begin
　now:=d[head];{取队首元素}
　fori:=1tob[now,0]do
　ifdist[b[now,i]]>dist[now]+a[now,b[now,i]]then
　begin
　dist[b[now,i]]:=dist[now]+a[now,b[now,i]];{修改最短路}
　ifnotv[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;
　procedureprint;
　begin
　writeln(dist[t]);
　end;
　begin
　init;
　spfa(s);
　print;
　end.