信息学竞赛图论习题

end; prim(1);

close(input); close(output); end.

设图G=(V,E)是一个有向图,它的每一条边(U,V)都有一个非负权W(U,V)，在G中指定一个结点V0，要求从V0到G的每一个结点Vj的最短路径找出来（或指出不存在）。 由于源结点V0是给定的，所谓称为单源最短路径。 【Dijkstra算法思想】 把所有结点分为两组。

第一组：包含已确定最短路径的结点。 第二组：包含尚未确定最短路径的结点。

按最短路径长度递增的顺序把第二组的结点加到第一组中去，直到V0可达的所有结点都包含于第一组中。在这个过程中，总保持从V0到第一组各结点的最短路径长度都不大于从V0到第二组任何结点的路径长度。 【单源最短路径算法实例】

现有一张县城的城镇地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的城镇为v0。由于该县经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程总造价必须最少。

【输入】 第一行一个整数v，代表城镇数，县城编号为1。 第二行是一个整数e，表示有向边数。 以下e行，每行为两个城镇编号和它们之间的公路造价。

【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路。

【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33

【输出样例】 1 2 2 3 2 4 1 5 1 6

原 图

从第1点出发的最短路径

5

program dijkstra_example; const

vmax=100; type

path=record {此记录类型用于记录每一个结点与v0的距离和其父结点}

length:integer; pre:0..vmax; end; var

w:array[1..vmax,1..vmax] of integer; dist:array[1..vmax] of path; v,e,u,i,j,x,y:integer; procedure init; begin

assign(input,'dijkstra.in'); reset(input);

assign(output,'dijkstra.out'); rewrite(output); readln(v); readln(e);

for i:=1 to v do for j:=1 to v do if i<>j

then w[i,j]:=30000 {30000只是一个较大的数的意思，实际应用于应该根据题目中给出的取值范围赋予一个充分大的数}

else w[i,j]:=0; for i:=1 to e do begin

read(x,y);

readln(w[x,y]); w[y,x]:=w[x,y]; end; end;

procedure dijkstra(v0:integer); var

min:integer; begin

w[v0,v0]:=1; {v0首先进入第一组} for i:=1 to v do begin

dist[i].length:=w[v0,i]; {计算每个结点的距离值} if dist[i].length<>30000

6

then dist[i].pre:=v0 {如和v0直接有路，则置前驱结点为v0} else dist[i].pre:=0; end; repeat

min:=30000; u:=0;

for i:=1 to v do {找最短距离} if (w[i,i]=0) and (dist[i].length

min:=dist[i].length; end; if u<>0

then begin

w[u,u]:=1;

for i:=1 to v do {重新计算其他结点的距离值}

if (w[i,i]=0) and (dist[i].length>dist[u].length+w[u,i]) then begin

dist[i].length:=dist[u].length+w[u,i]; dist[i].pre:=u; end; end; until u=0; end; begin init; v0:=1;

dijkstra(v0); for i:=1 to v do begin

if (i<>v0) and (dist[i].length<>30000) then write(dist[i].pre,' ',i); end;

close(input); close(output); end.

7

设图G=(V,E)是一个有向图,对于每对结点(U,V),找出从U到V的最短路径。 【Floyd算法思想】

利用一个三重循环产生一个存储每个结点最短距离的矩阵. 【Floyd算法实例】

现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最短距离

【输入】 第一行两个数v,e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权。

【输出】 所有可能连接的城市的最短距离。

【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33

【输出样例】 1 2 10 1 3 15 1 4 16 1 5 19 1 6 21 2 3 5 2 4 6 2 5 24 2 6 11 3 4 6 3 5 24 3 6 16 4 5 18 4 6 14 5 6 32

program floyd_example; const

maxn=10; var

n,s,t,i,j:integer;

8