UC知道Dijkstra算法求单源最短路径
来源：百度知道 编辑：UC知道 时间：2024/06/30 03:26:31
d[u]:s到u的距离 p[u]:记录前一节点信息
Init-single-source(G,s)
for each vertex v∈V[G]
do { 1 p[v]=NIL}
d[s]=0
Relax(u,v,w)
if d[v]>d[u]+w(u,v)
then { 2
p[v]=u
}
dijkstra(G,w,s)
1. Init-single-source(G,s)
2. S=Φ
3. Q=V[G]
4.while Q<> Φ
do u=min(Q)
S=S∪{u}
for each vertex v∈adj[u]
do 3
Init-single-source(G,s)
for each vertex v∈V[G]
do { 1 p[v]=NIL}
d[s]=0
Relax(u,v,w)
if d[v]>d[u]+w(u,v)
then { 2
p[v]=u
}
dijkstra(G,w,s)
1. Init-single-source(G,s)
2. S=Φ
3. Q=V[G]
4.while Q<> Φ
do u=min(Q)
S=S∪{u}
for each vertex v∈adj[u]
do 3
program dijkstra;
const
inf = '';
outf = '';
maxn = 100;
var
n, s, t: longint;
judge: array[1..maxn] of boolean;
dis: array[1..maxn] of longint;
a: array[1..maxn, 1..maxn] of longint;
procedure assignfile;
begin
assign(input, inf); reset(input);
assign(output, outf); rewrite(output);
end;
procedure closefile;
begin
close(input); close(output);
end;
procedure init;
var
i, j: longint;
begin
readln(n);
for i := 1 to n do begin
for j := 1 to n do read(a[i, j]);
readln;
end;
readln(s, t);
end;
procedure process;
var
now, i: longint;
begin
fillchar(dis, sizeof(dis), 255); dis[s] := 0;
fillchar(judge, sizeof(judge), true);
now := s;
repeat
judge[now] := false;
for i := 1 to n do if a[now, i] > 0