图论算法及matlab程序的三个案例.docVIP

图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置 一个顶点集合 S 并不断地作贪心选择来扩充这个集合。 一个顶点属于集合 S 当且 仅当从源到该顶点的最短路径长度已知。设 v 是图中的一个顶点，记 l (v) 为顶点 v 到源点 v1 的最短距离， vi , vj V ，若 ( vi ,v j )E ，记 vi 到 v j 的权 wij 。 Dijkstra 算法： ① S {v1} , l (v1) 0 ； v V { v1} , l ( v) , i 1 , S V { v1} ； ② S ，停止，否则转 ③ ； ③ l (v) min{ l ( v), d (v j ,v)} ， v j S ， v S ； ④ 存在 vi 1 ，使 l (vi 1 ) min{ l (v)} ， v S ； ⑤ S i 1 } ， S S { vi 1} ， i i 1，转②； S U { v 实际上， Dijkstra 算法也是最优化原理的应用：如果 v1v2 L vn 1vn 是从 v1 到 vn 的最 短路径，则 v1v2 L vn 1 也必然是从 v1 到 vn 1 的最优路径。 在下面的 MATLAB实现代码中，我们用到了距离矩阵，矩阵第 i 行第 j 行元素表 示顶点 vi 到 v j 的权 wij ，若 vi 到 vj 无边，则 wij realmax ，其中 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; end if(mmr(2,k)) mm=r(2,k);t=k; end end end s(1,t)=0;%找到最小的顶点加入集合 S end re=r; 动态规划求解最短路径 动态规划是美国数学家 Richard Bellman在 1951 年提出来的分析一类多阶段决策过程的最优化方法，在工程技术、工业生产、经济管理、军事及现代化控制工程等方面均有着广泛的应用。 动态规划应用了最佳原理： 假设为了解决某一优化问 题，需要依次作出 n 个决策 D1 , D 2 ,L , D n ，如若这个决策是最优的，对于任何一 个整数 k， 1kn，不论前面 k 个决策是怎样的，以后的最优决策只取决于由前 面决策所确定的当前状态，即 Dk 1 , D k 2 ,L , D n 也是最优的。 如图 1，从 A1 点要铺设一条管道到 16 点，中间必须要经过 5 个中间站，第一站 可以在 { A2， 3 A 4， A } { A A5， A6，A7}，{ A8，A4A9，A10}，{ A11， A12， A13}，{ A14，A15}。连接两地管道的距离 8 2 A A 3 8 11 A2 3 A A14 A5 3 2 5 5 5 6 5 4 1 A 1 8 3 A9 A12 2 A16 3 6 2 7 A 3 6 3 A3 3 8 6 A15 6 4 A 3 A 13 A 10 7 图 1 可选择的管道图 16 有 条路径，只须比较 次，就可得到 解决此问题可以用穷举法， 从 A1 到 48 47 A 。 最短路径为： A1→ 2→ 5→ 8 → 12→ 15→ 16，最短距离为 A A A A A A 18 也可以使用 Dijkstra 算法。这里，我们动态规划解决此问题。注意到最短路径有 这样一个特性，即如果最短路径的第 k 站通过 Pk，则这一最短路径在由 k 出发 Pk P 到达终点的那一部分路径，对于始点为 到终点的所有可能的路径来说，必定 也是距离最短的。 根据最短路径这一特性， 启发我们计算时从最后一段开始， 从后向前逐步递推的方法，求出各点到 A16 的最短路径。 在算法中，我们用数组六元数组 ss表示中间车站的个数 (A1 也作为中间车站 )，用距离矩阵 pa