图论实验三个案例 单源最短路径问题 1.1 Dijkstra算法 Dijkstra算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。设v是图中的一个顶点，记( )l v 为顶点v到源点v1的最短距离，,ijv vV，若( ,)ijv vE，记iv 到jv 的权ijw 。 Dijkstra算法： ① 1{ }Sv,1( )0l v；1{ }vVv ,( )l v ,1i ,1{ }SVv； ② S，停止，否则转③； ③ ( )min{ ( ), (, )}jl vl v d v v，jvS，vS ； ④ 存在1iv ，使1()min{ ( )}il vl v，vS； ⑤ 1{}iSSv，1{}iSSv，1ii ，转②； 实际上，Dijkstra算法也是最优化原理的应用：如果1 21nnv vvv是从1v 到nv的最短路径，则1 21nv vv也必然是从1v 到1nv 的最优路径。 在下面的MATLAB实现代码中，我们用到了距离矩阵，矩阵第 i行第 j行元素表示顶点iv 到jv 的权ijw ，若iv 到jv 无边，则realmaxijw，其中realmax是MATLAB常量，表示最大的实数(1.7977e+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)) mm=r(2,k);t=k; end end end s(1,t)=0;%找到最小的顶点加入集合S end re=r; 1.2 动态规划求解最短路径 动态规划是美国数学家Richard Bellman在1951年提出来的分析一类多阶段决策过程的最优化方法，在工程技术、工业生产、经济管理、军事及现代化控制工程等方面均有着广泛的应用。动态规划应用了最佳原理：假设为了解决某一优化问题，需要依次作出n个决策12,,,nD DD，如若这个决策是最优的，对于任何一个整数k，1
