图论实验三个案例单源最短路径问题 Dijkstra 算法Dijkstra 算法是解单源最短路径问题的一个贪心算法。

其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。

一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。

设v 是图中的一个顶点，记()l v 为顶点v 到源点v 1的最短距离，,i j v v V∀∈，若(,)i j v v E∉，记i v到j v 的权ij w =∞。

Dijkstra 算法：① 1{}S v =,1()0l v =；1{}v V v ∀∉-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③()min{(),(,)}j l v l v d v v =，j v S∈，v S ∀∈；④ 存在1i v +，使1()min{()}i l v l v +=，v S ∈；⑤1{}i S S v +=U ，1{}i S S v +=-，1i i =+，转②；实际上，Dijkstra 算法也是最优化原理的应用：如果121n nv v v v -L 是从1v 到nv 的最短路径，则121n v v v -L 也必然是从1v 到1n v -的最优路径。

在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元素表示顶点i v 到j v 的权ij w ，若i v到j v 无边，则realmax ij w =，其中realmax 是MATLAB常量，表示最大的实数+308)。

function re=Dijkstra(ma)%用Dijkstra 算法求单源最短路径 %输入参量ma 是距离矩阵%输出参量是一个三行n 列矩阵，每列表示顶点号及顶点到源的最短距离和前顶点n=size(ma,1);%得到距离矩阵的维数s=ones(1,n);s(1)=0;%标记集合S 和S 的补r=zeros(3,n);r(1,:)=1:n;r(2,2:end)=realmax;%初始化 for i=2:n;%控制循环次数 mm=realmax;for j=find(s==0);%集合S 中的顶点for k=find(s==1);%集合S 补中的顶点if(r(2,j)+ma(j,k)<r(2,k))r(2,k)=r(2,j)+ma(j,k);r(3,k)=j; endif(mm>r(2,k)) mm=r(2,k);t=k; end end ends(1,t)=0;%找到最小的顶点加入集合S end re=r;动态规划求解最短路径动态规划是美国数学家Richard Bellman 在1951年提出来的分析一类多阶段决策过程的最优化方法，在工程技术、工业生产、经济管理、军事及现代化控制工程等方面均有着广泛的应用。

动态规划应用了最佳原理：假设为了解决某一优化问题，需要依次作出n 个决策12,,,nD D D L ，如若这个决策是最优的，对于任何一个整数k ，1<k <n ，不论前面k 个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即12,,,k k nD D D ++L 也是最优的。

如图1，从A 1点要铺设一条管道到A 16点，中间必须要经过5个中间站，第一站可以在{ A 2，A 3}中任选一个，第二、三、四、五站可供选择的地点分别是：{ A 4，解决此问题可以用穷举法，从A 1到A 16有48条路径，只须比较47次，就可得到最短路径为：A 1→A 2→A 5→A 8→A 12→A 15→A 16，最短距离为18。

也可以使用Dijkstra 算法。

这里，我们动态规划解决此问题。

注意到最短路径有这样一个特性，即如果最短路径的第k 站通过P k ，则这一最短路径在由P k 出发到达终点的那一部分路径，对于始点为P k 到终点的所有可能的路径来说，必定也是距离最短的。

根据最短路径这一特性，启发我们计算时从最后一段开始，从后向前逐步递推的方法，求出各点到A 16的最短路径。

在算法中，我们用数组六元数组ss 表示中间车站的个数(A 1也作为中间车站)，用距离矩阵path 表示该图。

为简便起见，把该图看作有向图，各边的方向均为从左到右，则path 不是对称矩阵，如path(12,14)=5，而path(14,12)=0(用0表示不通道路)。

用3´16矩阵spath 表示算法结果，第一行表示结点序号，第二行表示图1 可选择的管道图该结点到终点的最短距离，第三行表示该结点到终点的最短路径上的下一结点序号。

下面给出MATLAB 实现算法。

function [scheme] = ShortestPath(path,ss) %利用动态规划求最短路径%path 是距离矩阵,ss 是车站个数 n=size(path,1);%结点个数scheme=zeros(3,n);%构造结果矩阵 scheme(1,:)=1:n;%设置结点序号scheme(2,1:n-1)=realmax;%预设距离值 k=n-1;%记录第一阶段结点最大序号 for i=size(ss,2):-1:1;%控制循环阶段数for j=k:-1:(k-ss(i)+1);%当前阶段结点循环 for t=find(path(j,:)>0);%当前结点邻接结点 if path(j,t)+scheme(2,t)<scheme(2,j) scheme(2,j)=path(j,t)+scheme(2,t); scheme(3,j)=t; end end endk=k-ss(i);移入下一阶段 end先在MATLAB 命令窗口中构造距离矩阵path ，再输入： >> ShortestPath(path,ss) 得到以下结果：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 13 16 13 10 9 12 7 6 8 7 5 9 4 3 0 2 5 6 8 8 9 10 12 12 12 14 15 15 16 16 0 将该结果表示为图，即为图1粗线所示。

棋盘覆盖问题 问题的提出在一个22k k⨯个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊的棋盘。

如图1就是当3k =时的特殊棋2所示4种不同形态的L 形骨牌覆盖一个特殊图1 当k =3时的特殊棋盘(a) (b) (c) (d)问题的分析易知，用到的L 型骨牌个数恰为(41)/3k -。

利用分治策略，我们可以设计出解棋盘覆盖问题的一个简捷的算法。

当k >0时，我们将22k k ⨯棋盘分割为4个1122k k --⨯子棋盘如图3两粗实线所示。

特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。

为了将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L 型骨牌覆盖这3个较小棋盘的会合处，如图4中央L 型骨牌所示，这3个子棋盘上被L 型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。

递归地使用这种分割，直至棋盘简化为11⨯棋盘。

算法的MATLAB 实现首先特殊方格在棋盘中的位置可以用一个12⨯的数组sp 表示；对于图2所示的4种L 型骨牌，可用数字1,2,3,4表示；对于特殊棋盘的骨牌覆盖表示，只须注意到图4所示的关键点，对每个关键点，给定一种L 型骨牌，就能覆盖整个棋盘，所以对于22k k ⨯的特殊棋盘的骨牌覆盖，可用一个(21)(21)k k -⨯-的矩阵表示。

按照这种思想，图4的矩阵表示为：图3 棋盘分割 图4 关键结点1 23k=4，特殊方格位置为：[1,4]，覆盖矩阵为：1040102 0400020 4030203 0003000 1040302 0400030 4030403⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦下面是在MATLAB中的棋盘覆盖实现程序。

function re = chesscover(k,sp)%解决棋盘的覆盖问题%棋盘为2^k*2^k，sp为特殊方格的棋盘位置global covermatrixcovermatrix=zeros(2^k-1,2^k-1);even1=floor(sp(1,1)/2)*2==sp(1,1);%判断水平位置是否是偶数even2=floor(sp(1,2)/2)*2==sp(1,2);%判断竖直位置是否是偶数if even1==1&&even2==0%找出找出特殊方格相对关键结点的位置i=4;elsei=even1+even2+1;endtempfun(1,1,k,[sp(1,1)-even1,sp(1,2)-even2,i]);re=covermatrix;function tempfun(top,left,k,tp)%子函数,tp为转换后特殊方格在棋盘网络的相对位置global covermatrixif k==1switch tp(1,3)case 1covermatrix(tp(1,1),tp(1,2))=3;case 2covermatrix(tp(1,1),tp(1,2))=4;case 3covermatrix(tp(1,1),tp(1,2))=1;case 4covermatrix(tp(1,1),tp(1,2))=2;endelsehalf=2^(k-1);i=top+half-1;j=left+half-1;if tp(1,1)<iif tp(1,2)<j%特殊方格在左上covermatrix(i,j)=3; %添加类型为3的L型骨牌tempfun(top,left,k-1,tp);tempfun(top,left+half,k-1,[i-1,j+1,4]);tempfun(top+half,left+half,k-1,[i+1,j+1,1]);tempfun(top+half,left,k-1,[i+1,j-1,2]);else %特殊方格在右上covermatrix(i,j)=4;%添加类型为4的L型骨牌tempfun(top,left,k-1,[i-1,j-1,3]);tempfun(top,left+half,k-1,tp);tempfun(top+half,left+half,k-1,[i+1,j+1,1]);tempfun(top+half,left,k-1,[i+1,j-1,2]);endelseif tp(1,2)>j%特殊方格在右下covermatrix(i,j)=1;%添加类型为3的L型骨牌tempfun(top,left,k-1,[i-1,j-1,3]);tempfun(top,left+half,k-1,[i-1,j+1,4]);tempfun(top+half,left+half,k-1,tp);tempfun(top+half,left,k-1,[i+1,j-1,2]);else %特殊方格在左下covermatrix(i,j)=2;%添加类型为4的L型骨牌tempfun(top,left,k-1,[i-1,j-1,3]);tempfun(top,left+half,k-1,[i-1,j+1,4]);tempfun(top+half,left+half,k-1,[i+1,j+1,1]);tempfun(top+half,left,k-1,tp);endendend在MATLAB命令窗口中输入指令chesscover(3,[1,4])将会得到如上面矩阵一样的结果。