搜索
【题25】计算单源最短路问题（Dijkstra算法）设G=（V，E）是一个有向图，它的每一条边（U，V）∈Ｅ都有一个权W（U，V），在G中指定一个结点V0，要求把从V0到G的每一个结点Vj(VＪ∈Ｖ)的最短有向路找出来（或者指出不存在从V0到Vj的有向路，即V0不可达Vj）。输入顶点数nn*n的带权矩阵输出有n行，每行为顶点序号i和V0到Vi的最短路长题解１.算法的基本思路解决单源最短路径的基本思想是把图中所有结点分为两组第一组：包括已确定最短路径的结点；第二组：包括尚未确定最短路径的结点；我们按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。另外，每一个结点对应一个距离值。第一组结点对应的距离值就是由v0到此结点的最短路径长度；第二组结点对应的距离值就是v0经由第一组结点（中间结点）至此结点的最短路径长度。具体作法是：初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点）EvvEvvwdistiiii),(),(000然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）：若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值vm的距离值+Wmi），则要修改vi的距离（vi的距离值←vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，…。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。下面，我们来证明这个算法：显然，初始时对两个组的划分及各结点距离值的确定符合上述基本思想。因此要证明算法正确性，关键是证明每次往第一组加入结点vm后，其两个组的划分及结点距离值仍然符合要求。也就是要证明第二组中距离值最小的结点vm，其距离值为v0到vm的最短路径长度，且vm就是第二组中路径长度最小的结点。我们来证明这两点：⑴若vm的距离值不是从v0到vm的最短路径长度，另有一条v0经由第二组某些结点（其中第一个结点设为vs）到达vm的路径，其长度比vm的距离值更小，即vs的距离值v0经由vs到vm的最短路径长度vm的距离值与vm是第二组中距离值最小的结点矛盾。所以vm的距离值就是从v0到vm的最短路径长度。⑵设vx是第二组中除vm外的任何其它结点。若v0至vx的最短路径上的中间结点为第一组的结点，由距离值的定义可知，其路径长度势必大于等于v0至vm的最短路径长度；若v0至vx的最短路径不仅包含第一组的结点为中间结点。设路径上第一个在第二组的中间结点为vy，则v0至vy的路径长度就是vy的距离值，已大于等于v0至vm的最短路径长度，那么v0到vx的最短路径长度当然也不会小于v0到vm的最短路径长度了，所以vm是第二组中最短路径为最小的结点。２.变量说明下面给出算法中的变量说明设n—图的结点数；adj—有向图的相邻矩阵。其中dist—最短路径集合。其中dist[i]．pre—在v0至vi的最短路径上，vi的前趋结点序号；dist[i]．length—v0至vI的最短路径长度，即vi的距离值；（1≤i≤n）Constn=图的结点数；Typepath=record{路径集合的结点类型}length：real；{距离值}pre：0‥n；{前趋结点序号}end；varadj：array[1‥n，1‥n]ofreal{相邻矩阵}dist：array[1‥n]ofpath；{路径集合}３.算法流程计算单源最短路径的过程如下：fillchar(adj，sizeof(adj)，0)；{建立相邻矩阵adj}fori：=1tondoforj：=1tondoif（i，j）∈Ethenadj[i，j]←wijelseadj[i，j]←∞；fori：=1tondo{路径集合初始化}begindist[i]．length←adj[v0，i]；ifdist[i]．length∞thendist[i]．pre←v0elsedist[i]．pre←0；end；{for}adj[v0，v0]←1；{源结点v0进入第一组}repeatmin←∞；u←0；fori：=1tondo{从第二组中找距离值最小的结点u}if(adj[i，i]=0)and(dist[i]．lengthmin)thenbeginu←i；min←dist[i]．length；end；{then}ifu0{第二组中存在一个距离值最小的结点}thenbeginadj[u，u]←1；{结点u进入第一组}fori：=1tondo{修正第二组中u可达的结点距离值}if(adj[i，i]=0)and(dist[i]．lengthdist[u]．length+adj[u，i])thenbegindist[i]．length←dist[u]．length+adj[u，i]；dist[i]．pre←u；end；{then}end；{then}untilu=0；{直至n个结点全部加入第一组为止}算法结束时，沿着结点vi的pre指针回溯，便可确定v0至vi的最短路径：procedureprint(i：integer)；beginifi=v0then输出结点v0elsebeginprint(dist[i]．pre)；输出结点i和v0至vi的最短路径长度dist[i]．length；end；{else}end；{print}显然递归调用print[1]，…，print[n]后，可得知v0至所有结点的最短路径。