完善程序(free pascal):单源点最短路径:给定带权有向图G=(v,e),源点v1在v中,求 v1到v中其余各结点的最短路径.数据结构说明:cost[I,j]:表示带权有向图的邻接矩阵 d[j]:表示从v1到vj的最短路径长
来源:学生作业帮助网 编辑:作业帮 时间:2024/09/01 00:34:19
完善程序(free pascal):单源点最短路径:给定带权有向图G=(v,e),源点v1在v中,求 v1到v中其余各结点的最短路径.数据结构说明:cost[I,j]:表示带权有向图的邻接矩阵 d[j]:表示从v1到vj的最短路径长
完善程序(free pascal):
单源点最短路径:给定带权有向图G=(v,e),源点v1在v中,求 v1到v中其余各结点的最短路径.
数据结构说明:cost[I,j]:表示带权有向图的邻接矩阵 d[j]:表示从v1到vj的最短路径长度 path[j]:表示从v1到vj的最短路径
程序如下:
const n=5; maxnum=1e10;
type
gr=array[1..n,1..n] of real;
dt=array[1..n] of real;
jh=set of 1..n;
pt=array[1..n] of jh;
var
s:jh;
cost:gr;
d:dt;
path:pt;
i,j,k:integer;
mm:real;
begin
for i:=1 to n do
for j:=1 to n do read(cost[i,j]);
s:=[1];
for i:=2 to n do
begin
d[i]:=cost[1,i];
if d[i] < maxnum then path[i]:=[1]+[i]
else ___(1)___
end;
for i:=1 to n-1 do
begin
mm:=maxnum;
for j:=2 to n do
if ___(2)___ then
begin mm:=d[j];k:=j; end;
s:=s+[k];
for j:=2 to n do
if not(j in s) and (cost[k,j] < maxnum) then
if ___(3)___ then
begin
d[j]:=d[k]+cost[k,j];
path[j]:=___(4)___
end;
end;
writeln;
for i:=2 to n do
begin
writeln('v1->','v',i,':',d[i]);
write('v1');
for j:=2 to n do
if j in path[i] then write('->','v',j);
writeln;
end;
end.
因为没学,
完善程序(free pascal):单源点最短路径:给定带权有向图G=(v,e),源点v1在v中,求 v1到v中其余各结点的最短路径.数据结构说明:cost[I,j]:表示带权有向图的邻接矩阵 d[j]:表示从v1到vj的最短路径长
[]表示集合啊