打卡第五天—图的最短路径和距离_python菜鸟

一、前言

动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。

二、最短路线

2.1 教程

2.1.1 sparse创建稀疏矩阵

比如我们有这样的无向图：

matlab代码：

%w(起点,终点)=权重值
%博客案例二
clear all
clc
w=zeros(4);
w(1,2)=2;w(1,3)=3;w(1,4)=8; 
w(2,3)=6;w(2,4)=6;
G=sparse(w)

运行得到如下：

或者你也可以这样创建稀疏矩阵：

clear all
clc
%sparse([起点集合],[对应终点集合],[对应权重集合])
G = sparse([1 1 1 2 2],[2 3 4 3 4],[2 3 8 6 6]);
s=sparse(G)

结果一样为：

2.1.2 有向图最短路径（1）

使用函数：graphallshortestpaths，其语法如下：

参数含义：
G:稀疏矩阵
0/false代表无向图 1/true代表有向图。默认为true。

我们要解决如下问题：
首先创建一个有向图：

clear all
clc
G = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],[41 99 51 32 15 45 38 32 36 29 21])
view(biograph(G,[],'ShowWeights','on'))

得到我们更加直观的图：

第二步：找出有向图中每对节点之间的所有最短路径。使用graphallshortestpaths函数，只需要加一行代码即可：

clear all
clc
G = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],[41 99 51 32 15 45 38 32 36 29 21])
view(biograph(G,[],'ShowWeights','on'))
graphallshortestpaths(G)

运行：

返回的结果什么意思呢？
比如说第一行代表的意思就是节点一分别到节点六的距离。为什么第一个值为0？节点一到节点一当然在原位置了，肯定为0咯。第二行类似一样的道理。
因此：从节点一到节点六最短距离为多少呢？最短距离为95可以从返回表中一眼看出来。留个问题：节点二到节点一位111怎么得到的？路径位？
根据结果推路径：

第一行推出：节点一先到节点五，此时距离为21（为么选节点五？因为节点一到节点五最短,每次都选择最短）
然后我们再跳到第五行：节点五要先到节点三，距离为32
于是我们再跳到第四行：节点四要先到节点六，距离为38

此时我们已经完成节点一到节点六距离为：

21+32+38=95。

路径为：1—5—3—6
参考：

下面我在介绍一个新的方法，会更简单！你实在看不懂路径怎么来的，就不必纠结，你只需要掌握它求出最短距离就好了。

2.1.3 有向图最短路径（2）

保存该函数：dijkstra.m（你不需要修改，知道这个函数具体意思，我们调用它就行）

function [min,path]=dijkstra(w,start,terminal)
n=size(w,1); label(start)=0; f(start)=start;
for i=1:n
   if i~=start
       label(i)=inf;
end, end
s(1)=start; u=start;
while length(s)<n
   for i=1:n
      ins=0;
      for j=1:length(s)
         if i==s(j)
            ins=1;
         end
      end
      if ins==0
         v=i;
         if label(v)>(label(u)+w(u,v))
            label(v)=(label(u)+w(u,v)); 
         f(v)=u;
         end 
      end
   end   
v1=0;
   k=inf;
   for i=1:n
         ins=0;
         for j=1:length(s)
            if i==s(j)
               ins=1;
            end
         end
         if ins==0
            v=i;
            if k>label(v)
               k=label(v);  v1=v;
            end
         end
   end
   s(length(s)+1)=v1;  
   u=v1;
end
min=label(terminal); path(1)=terminal;
i=1; 
while path(i)~=start
      path(i+1)=f(path(i));
      i=i+1 ;
end
path(i)=start;
L=length(path);
path=path(L:-1:1);

现在我们再来解决同样上面的问题：

比如我要求一到六节点最短路径：

% 构造邻接矩阵
a = zeros(6);
a = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],[41 99 51 32 15 45 38 32 36 29 21])
a = a + a';
a(a==0) = inf; % 零元素换成inf
a(eye(6,6)==1)=0; % 对角线换成 0 
view(biograph(a,[],'ShowWeights','on'))
[min,path]=dijkstra(a,1,6) % dijkstra模型求解节点一到节点六最短路径

运行如下：

min就是最短路径为82，路径过程为：1 5 3 6

同样是求最短路径，该方法可能更简单，你只需要在这里创建一个矩阵，可以求任意两个节点的最短距离和路径。请领悟一下，在你的博客写好记录。

2.1.4 无向图最短路径（1）

还是求解这个问题：

我们还是使用有向图的第一张方法：

clear all
clc
W = [41 99 51 32 15 45 38 32 36 29 21];
G = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W)
UG = tril(G + G')
view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))

得到创建的稀疏矩阵：

添加一行代码，使用求函数graphallshortestpaths（注意这个函数2021版本被弃用）：

clear all
clc
W = [41 99 51 32 15 45 38 32 36 29 21];
G = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W);
UG = tril(G + G')
view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))
graphallshortestpaths(UG,'directed',false)

得到如下：

我们可以一样就看出节点一到节点六最短距离82.用我上面的讲过的方法，可以看出路径为：1-5-3-6
21+32+29=53+29=82

2.1.5无向图最短路径（2）

其实我们可以使用函数shortestpath求解，更方便：

clc
clear all
% 构造邻接矩阵
G = zeros(6);
G = graph([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],[41 99 51 32 15 45 38 32 36 29 21])

plot(G,'EdgeLabel',G.Edges.Weight)
[P,d] = shortestpath(G,1,6)

运行：

p就是路径，d就是最短距离，更方便了！

三、总结

本篇为最短路径问题，我给的方法可能不一定是最好的，也许你可以使用别的方法来获得相同的答案，这是允许的。
请阅读完本篇博客，写一篇你的学习记录提交任务，认真写好你对本教程的理解，至少让你自己看得懂。