您的位置:

当前热文:dijkstra算法代码_dijkstra算法

时间:2023-05-02 17:00:43

1、[问题分析] 对于一个含有n个顶点和e条边的图来说,从某一个顶点Vi到其余任一顶点Vj的最短路径,可能是它们之间的边(Vi,Vj),也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。

2、下面给出解决这个问题的Dijkstra算法思想。


(资料图片)

3、 设图G用邻接矩阵的方式存储在GA中,GA[i,j]=maxint表示Vi,Vj是不关联的,否则为权值(大于0的实数)。

4、设集合S用来保存已求得最短路径的终点序号,初始时S=[Vi]表示只有源点,以后每求出一个终点Vj,就把它加入到集合中并作为新考虑的中间顶点。

5、设数组dist[1..n]用来存储当前求得的最短路径,初始时Vi,Vj如果是关联的,则dist[j]等于权值,否则等于maxint,以后随着新考虑的中间顶点越来越多,dist[j]可能越来越小。

6、再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边,初始时为Vi到Vj的边,如果不存在边则为空。

7、 执行时,先从S以外的顶点(即待求出最短路径的终点)所对应的dist数组元素中,找出其值最小的元素(假设为dist[m]),该元素值就是从源点Vi到终点Vm的最短路径长度,对应的path[m]中的顶点或边的序列即为最短路径。

8、接着把Vm并入集合S中,然后以Vm作为新考虑的中间顶点,对S以外的每个顶点Vj,比较dist[m]+GA[m,j]的dist[j]的大小,若前者小,表明加入了新的中间顶点后可以得到更好的方案,即可求得更短的路径,则用它代替dist[j],同时把Vj或边(Vm,Vj)并入到path[j]中。

9、重复以上过程n-2次,即可在dist数组中得到从源点到其余各终点的最段路径长度,对应的path数组中保存着相应的最段路径。

10、 下面给出具体的Dijkstra算法框架(注:为了实现上的方便,用一个一维数组s[1..n]代替集合S,用来保存已求得最短路径的终点集合,即如果s[j]=0表示顶点Vj不在集合中,反之,s[j]=1表示顶点Vj已在集合中)。

11、 Procedure Dijkstra(GA,dist,path,i); {表示求Vi到图G中其余顶点的最短路径,GA为图G的邻接矩阵,dist和path为变量型参数, 其中path的基类型为集合} Begin For j:=1 To n Do Begin {初始化} If j<>i Then s[j]:=0 Else s[j]:=1; dist[j]:=GA[i,j]; If dist[j]i Then s[m]:=1 else exit; {若条件成立,则把Vm加入到S中, 否则退出循环,因为剩余的终点,其最短路径长度均为maxint,无需再计算下去} For j:=1 To n Do {对s[j]=0的更优元素作必要修改} If (s[j]=0) and (dist[m]+GA[m,j]

12、首先来分析Dijkstra的算法思想设图G用邻接矩阵的方式存储在GA中,GA[I,j]=maxint表示vi,vj是不关联的,否则为权值(大于0的实数)。

13、设集合S用来存储保存已求得最短路径的终点序号,初始时S=[vi]表示只有源点,以后每求出一个终点vj,就把它加入到集合中并作为新考虑的中间顶点。

14、设数组dist[1..n]用来存储当前求得的最短路径,初始时vi,vj如果是关联的,则dist[j]等于权值,否则等于maxint,以后随着新考虑的中间顶点越来越多,dist[j]可能越来越小。

15、再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边,初始时vi到vj的边,如果不存在边则为空。

16、执行时,先从S以外的顶点(即待求出最短路径的终点)所对应的dist数组元素中,找出其值最小的元素(假设为dist[m]),该元素值就是从源点vi到终点vm的最短路径长度,对应的path[m]中的顶点或边的序列即为最短路径。

17、接着把vm并入集合S中,然后以vm作为新考虑的中间顶点,对S以外的每个顶点vj,比较dist[m]+GA[i,j]与dist[j]的大小,若前者小,表明加入了新的中间顶点后可以得到更好的方案,即可求得更短的路径,则用它代替dist[j],同时把vj或边(vm,vj)并入到path[j]中。

18、重复以上过程n-2次,即可在dist数组中得到从源点到其余个终点的最短路径长度,对应的path数组中保存着相应的最短路径。

19、为了实现上的方便,用一个一维数组s[1..n]代替集合s,用来保存已求得最短路径的终点集合,即如果s[j]=0表示顶点vj不在集合中,反之,s[j]表示顶点vj已在集合中)。

20、Procedure dijkstra (GA,dist path,I) begin for j:= 1 to n do begin if j<>I then s[j]:=0;{j不在集合中} else s[j]:=1;{j在集合中}; dist[j]:=GA[I,J];IF dist [j]I then s[m]:=1 else exit;{若条件成立,则把Vm加入到s中,否则退出循环,因为剩余的终点,其最短路径长度均为maxint,无需再计算下去} for j:=1 to n do {对s[j]=0的更优元素作必要修改}if (s[j]=0)and (dist[m]+GA[m,j]

本文到此分享完毕,希望对大家有所帮助。

返回顶部