2022年单源最短路径算法 .pdf
设图 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 点出发的最短路径名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 1 2 2 3 2 4 1 5 1 6 program dijkstra_example; const vmax=100; type path=record 此记录类型用于记录每一个结点与v0 的距离和其父结点 length:integer; pre:0.vmax; end; var w:array1.vmax,1.vmax of integer; dist:array1.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 ij then wi,j:=maxint maxint只是一个较大的数的意思，实际应用于应该根据题目中给出的取值范围赋予一个充名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 分大的数 else wi,j:=0; for i:=1 to e do begin read(x,y); readln(wx,y); wy,x:=wx,y; end; end; procedure dijkstra(v0:integer); var min:integer; begin wv0,v0:=1; v0首先进入第一组 for i:=1 to v do begin disti.length:=wv0,i; 计算每个结点的距离值 if disti.lengthmaxint then disti.pre:=v0 如和 v0 直接有路，则置前驱结点为v0 else disti.pre:=0; end; repeat min:=maxint; u:=0; for i:=1 to v do 找最短距离 if (wi,i=0) and (disti.lengthmin) then begin u:=i; min:=disti.length; end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - if u0 then begin wu,u:=1; for i:=1 to v do 重新计算其他结点的距离值 if (wi,i=0) and (disti.lengthdistu.length+wu,i) then begin disti.length:=distu.length+wu,i; disti.pre:=u; end; end; until u=0; end; begin init; v0:=1; dijkstra(v0); for i:=1 to v do begin if (iv0) and (disti.lengthmaxint) then write(disti.pre, ,i); end; close(input); close(output); end. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -
