《单源最短路径算法(Dijkstra算法)(000001).pdf》由会员分享，可在线阅读，更多相关《单源最短路径算法(Dijkstra算法)(000001).pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、设图 G=(V,E)是一个有向图,它的每一条边(U,V)都有一个非负权W(U,V)，在 G中指定一个结点V0，要求从V0 到 G的每一个结点Vj 的最短路径找出来（或指出不存在）。由于源结点V0 是给定的，所谓称为单源最短路径。【Dijkstra算法思想】把所有结点分为两组。第一组：包含已确定最短路径的结点。第二组：包含尚未确定最短路径的结点。按最短路径长度递增的顺序把第二组的结点加到第一组中去，直到 V0 可达的所有结点都包含于第一组中。在这个过程中，总保持从V0 到第一组各结点的最短路径长度都不大于从V0 到第二组任何结点的路径长度。【单源最短路径算法实例】现有一张县城的城镇地图，图中的顶
2、点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的城镇为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 【输出
3、样例】原图从第 1 点出发的最短路径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);assig
4、n(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只是一个较大的数的意思，实际应用于应该根据题目中给出的取值范围赋予一个充文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2
5、A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z
6、2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2
7、Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y
8、2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4
9、Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW
10、4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:C
11、W4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2分大的数 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 begi
12、n 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;文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6
13、U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N
14、6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10
15、N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z1
16、0N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z
17、10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9
18、Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW
19、9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2 if u0 then begin wu,u:=1;for i:=1 to v do 重新计算其他结点的距离值 if(wi,i=0)and(disti.lengthdistu.length+wu,i)then
20、 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.文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8
21、C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R
22、8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7
23、R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W
24、7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1
25、W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E
26、1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2文档编码:CW4Y2Z2A5Q5 HW9Z10N6U10I1 ZU10E1W7R8C2