最短路的求解

实验类型：◆验证性实验  ◇综合性实验  ◇设计性实验

实验目的：学会使用Matlab求解最短路。

实验内容：1.熟练运用Floyd算法；2. 熟练运用Dijkstra算法；3.利用Matlab编程实现最短路的计算。

例1：已知无向图G如下所示，试利用Floyd算法求任意两点间的最短路。

例2：试利用Dijkstra算法求下面有向图G中从点v1到v9的最短路。

实验原理：

Floyd算法：

1.使用范围

①求任意两结点的最短路径；

②有向图、无向图、混合图。

2.基本思想

直接在网络图的权矩阵W WW中用插入顶点的方法依次递推地构造出n nn个矩阵D ( 1 ) ， D ( 2 ) ， … ， D ( n ) D(1)，D(2)，…，D(n)D(1)，D(2)，…，D(n)，D ( n ) D(n)D(n)是网络图的最短距离矩阵，同时引入一个路由矩阵记录任意两点之间的最短路径。

3.算法步骤

设D i j 为结点v i 到v j的距离；P i j为结点v i到v j路径上v i 的后继点；

W为权矩阵。

第1步：∀i，j，D ij=W ij,P ij=j，k=1；(赋初值)

第2步：∀i，j，若D i k + D k j < D i j，则D i j = D i k + D k j，P i j = P i k，k = k+1(更新D，PD，PD，P)

第3步：重复第2步，直到k=n+1。

Dijkstra算法：

算法特点：

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

算法的思路：

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点。

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

实验步骤：

1. 上机实验前先编写出程序代码

2. 录入、编辑程序

3. 调适程序至正确运行

4. 记录运行时的输入和输出

5. 对程序做进一步完善

程序代码：

例1：

d=[0 3 5 Inf Inf Inf

   3 0 1 2 2 Inf

   5 1 0 Inf 4 Inf

   Inf 2 Inf 0 2 4

   Inf 2 4 2 0 2

   Inf Inf Inf 4 2 0];

n=length(d);

U=d;

S=zeros(n,n);

for i=1:n

    for j=1:n

        S(i,j)=j;

    end

end

for i=1:n

    for j=1:n

        for m=1:n

            if U(i,j)>U(i,m)+U(m,j)

                U(i,j)=U(i,m)+U(m,j);

                S(i,j)=S(i,m);

            end

        end

    end

end

S

U

例2：

W=input('此程序有关MST，请输入权矩阵：');

 [i,j,s] = find(W);

ss = [i';j';s'];

dg = sparse(ss(1,:),ss(2,:),ss(3,:));

dg(9,9)=0;

h=view(biograph(dg,[],'ShowWeights','on'));

[dist,path,~]=graphshortestpath(dg,1,9,'Directed','true')

set(h.Nodes(path),'Color',[1 0.4 0.4]);

edges=getedgesbynodeid(h,get(h.Nodes(path),'ID'));

set(edges,'LineColor',[1 0 0]);

set(edges,'LineWidth',2);

实验运行结果界面：

实验总结：

本次实验通过Floyd算法和Dijkstra算法求解了最短路径问题，掌握了它们的基本原理和实现方法。Floyd算法适用于求解任意两点间的最短路径，而Dijkstra算法适用于求解从指定起点到指定终点的最短路径。

在适用范围上：

Floyd算法适用于求解任意两点间的最短路径，可以处理带负权边的图，但不能处理带负权回路的图。Dijkstra算法适用于求解从指定起点到其他所有点的最短路径，不能处理带负权边的图。

在稳定性上：

Floyd算法是一种动态规划算法，可以保证找到全局最优解。但是Dijkstra算法是一种贪心算法，每次选择当前最短路径的顶点，不能保证全局最优解，但对于非负权图可以保证最短路径是最优的。

在实现难度上：

Floyd算法相对简单，只需使用三重循环更新距离矩阵即可。Dijkstra算法在实现时需要使用优先队列等数据结构，相对复杂一些。

学到很多新的东西，路漫漫其修远兮，吾将上下而求索。加油！