图论最短路径求解

你的名字 2023-09-28 15:12 115阅读 0赞

来源：数学建模清风学习内容

--------------------

*  **处理无向图用迪杰斯特拉，有向图用弗洛伊德算法**

--------------------

### 文章目录 ###

*  图论
 *   *  01 图是什么
     *  02 如何画图
     *  03 权重邻接矩阵
 *  迪杰斯特拉算法
 *   *  01步骤演示
     *  02 迪杰斯特拉的局限性
 *  matlab计算
 *  弗洛伊德算法
 *   *  01 算法讲解与伪代码
     *  02 matlab代码实现
     *  03 示例

--------------------

# 图论 #

--------------------

## 01 图是什么 ##

![在这里插入图片描述][6bed46bdd1b840d28a0e294bc58cb3a4.png]

## 02 如何画图 ##

*  在线网站作图，如何节点较少，作图效果较好
 *  [https://csacademy.com/app/graph\_editor/][https_csacademy.com_app_graph_editor]  
    ![在这里插入图片描述][6d404c3738ae460985bacdf63855193b.png]
 *  matlab作图，适合节点较多，但作图效果一般

![在这里插入图片描述][f688ca7d86a14c73abb0cd2896b730d3.png]

%% Matlab作无向图
    
    % （1）无权重（每条边的权重默认为1）
    % 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并生成一个图
    % s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组。
    s1 = [1,2,3,4];
    t1 = [2,3,1,1];
    G1 = graph(s1, t1);
    plot(G1)
    % 注意哦，编号最好是从1开始连续编号，不要自己随便定义编号
    s1 = [1,2,3,4];
    t1 = [2,3,1,1];
    G1 = graph(s1, t1);
    plot(G1)
    
    % 注意字符串元胞数组是用大括号包起来的哦
    s2 = {'学校','电影院','网吧','酒店'};
    t2 = {'电影院','酒店','酒店','KTV'};
    G2 = graph(s2, t2);
    plot(G2, 'linewidth', 2)  % 设置线的宽度
    % 下面的命令是在画图后不显示坐标
    set( gca, 'XTick', [], 'YTick', [] );  
    
    % （2）有权重
    % 函数graph(s,t,w)：可在 s 和 t 中的对应节点之间以w的权重创建边，并生成一个图
    s = [1,2,3,4];
    t = [2,3,1,1];
    w = [3,8,9,2];
    G = graph(s, t, w);
    plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) 
    set( gca, 'XTick', [], 'YTick', [] );  
    
    %% Matlab作有向图
    
    % 无权图 digraph(s,t)
    s = [1,2,3,4,1];
    t = [2,3,1,1,4];
    G = digraph(s, t);
    plot(G)
    set( gca, 'XTick', [], 'YTick', [] );  
    
    % 有权图 digraph(s,t,w)
    s = [1,2,3,4];
    t = [2,3,1,1];
    w = [3,8,9,2];
    G = digraph(s, t, w);
    plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) 
    set( gca, 'XTick', [], 'YTick', [] );  
    
    % % 注意：代码文件仅供参考，一定不要直接用于自己的数模论文中
    % % 国赛对于论文的查重要求非常严格，代码雷同也算作抄袭

## 03 权重邻接矩阵 ##

![在这里插入图片描述][c0b375681c0a4136a113056ba10aabc0.png]  
![在这里插入图片描述][7d50f9396182420ebd808a38410d72c0.png]

--------------------

# 迪杰斯特拉算法 #

*  不断走最小路程的路径，不断重复直至终点。----> [视频演示][Link 1]

--------------------

## 01步骤演示 ##

*  Visited：节点是否被访问；
 *  Distance：路径长度（距离）；
 *  Parent：来自于哪个节点；

> 先更新所连节点的距离Distance和来源节点Parent，比较Distance，选最小的路径走，然后更新节点被访问Visited，最后不断重复直至终点。

![在这里插入图片描述][312ce5f1137d4cb4921056e770ceac1c.png]

*  0为起点，先更新距离Distance为0，Parent没有填0，然后更新节点被访问Visited为1  
    ![在这里插入图片描述][fc754d691b3d42e79ae5928844d2f2e7.png]
 *  与0相连的节点只有1和7，所以先更新1和7节点的距离Distance（0到1为4，0到7为8），然后更新母节点Parent都来自于0

![在这里插入图片描述][3ce69b22e95148e8bfddf912f3056111.png]

*  比较0到1和7的距离，相比较之下，选择距离最小的1节点，所以1节点被访问Visited为1

![在这里插入图片描述][254a4125b8924d5ebe3591b6bab15ee1.png]

*  然后继续以1 为起点来看，与相连的节点有2和7，所以先更新1到2和7的距离Distance，再更新母节点Parent来源为1  
    ![在这里插入图片描述][32848024f4aa49fe93c00b29eb6f8223.png]
 *  比较1到2和7的距离，选择距离Distance最短的节点7进行访问，7的Visited更新为1  
    ![在这里插入图片描述][390f452f01884c9b929bb75af689305c.png]
 *  再看与7节点相连的6和8，先更新距离Distance，再更新母节点Parent![在这里插入图片描述][bed29d6c74984408afcf76f00ef8e799.png]
 *  比较7到6和8的距离，选择最小距离的节点访问，即8节点，Visited更新为1
 *  ![在这里插入图片描述][e0c3e0ab236a43249a9770480d3f57a7.png]
 *  再看与8节点相连的2和6节点，先更新距离，这里发现8到6的距离为15>原来的13，所以6节点不更新，只更新2节点的距离Distance和母节点Parent来源为8

![在这里插入图片描述][0bd13c3ebfdd4313a96d1e422f9512e5.png]

*  比较与8节点相连的2和6的距离Distance,发现2的距离Distance更小，所以选择2节点来访问Visited为1  
    ![在这里插入图片描述][1e0230c7cf9f473b93c7290306db811f.png]
 *  看与2节点相连的3和5，先更新距离，再更新母节点，最后比较距离，选择最小距离节点访问，不断重复，直到终点  
    ![在这里插入图片描述][b0d45ba2005540488143dc5370a5d57e.png]

![在这里插入图片描述][e16d29a5711048a8b448daf53a22a30a.png]  
![在这里插入图片描述][424ff7e67dca410c8e887cb9295994b6.png]  
![在这里插入图片描述][07f10f2a44a0483e8b18cf8ec32818fd.png]  
![在这里插入图片描述][796138102408429b8c1c21f6548a80a9.png]  
![在这里插入图片描述][1f569b63d0f7441081654e81aca263cc.png]

*  走到终点以后，一步步根据母节点溯源回起点，即为最短路径！  
    ![在这里插入图片描述][21faa48d1bd5442db91e4fd70a7b0dc6.png]

## 02 迪杰斯特拉的局限性 ##

![在这里插入图片描述][a17ad111417a4554951e2a0724081dc8.png]  
![在这里插入图片描述][e1b2d184230d423f9b36fb291cdeebe9.png]

![在这里插入图片描述][ebcd0db302204b0d91ca350dc6ae1666.png]

# matlab计算 #

![在这里插入图片描述][579bbf3735b04e2a91e83a00aa2caa04.png]

![在这里插入图片描述][aeb1482750fc4488b9fbc00cfb173a55.png]

![在这里插入图片描述][c96ec25d0930483bb898eaaad78b48fc.png]  
![在这里插入图片描述][f4ce2429c39540989538def478a57421.png]

![在这里插入图片描述][fc11f02f25ae4677ad08c56eb18653d6.png]

%% 注意：以下代码需要较新版本的matlab才能运行（最好是2016版本及以上哦）
    % 如果运行出错请下载新版的matlab代码再运行
    
    % 注意哦，Matlab中的图节点要从1开始编号，所以这里把0全部改为了9
    % 编号最好是从1开始连续编号，不要自己随便定义编号
    s = [9 9 1 1 2 2 2 7 7 6 6  5  5 4];     % 母节点
    t = [1 7 7 2 8 3 5 8 6 8 5  3  4 3];     %子节点
    w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];    % 权重
    G = graph(s,t,w);
    plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) 
    set( gca, 'XTick', [], 'YTick', [] );  
    [P,d] = shortestpath(G, 9, 4)  %注意：该函数matlab2015b之后才有哦
    
    % 在图中高亮我们的最短路径
    myplot = plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2);  %首先将图赋给一个变量
    highlight(myplot, P, 'EdgeColor', 'r')   %对这个变量即我们刚刚绘制的图形进行高亮处理（给边加上r红色）
    
    % 求出任意两点的最短路径矩阵
    D = distances(G)   %注意：该函数matlab2015b之后才有哦
    D(1,2)  % 1 -> 2的最短路径
    D(9,4)  % 9 -> 4的最短路径
    
    % 找出给定范围内的所有点  nearest(G,s,d)
    % 返回图形 G 中与节点 s 的距离在 d 之内的所有节点
    [nodeIDs,dist] = nearest(G, 2, 10)   %注意：该函数matlab2016a之后才有哦
    
    
    % % 注意：代码文件仅供参考，一定不要直接用于自己的数模论文中
    % % 国赛对于论文的查重要求非常严格，代码雷同也算作抄袭

--------------------

# 弗洛伊德算法 #

--------------------

## 01 算法讲解与伪代码 ##

![在这里插入图片描述][82116fca446e40b1bb383b1d122b24c8.png]  
![在这里插入图片描述][19d748da4eba41c8b6b212599ecec115.png]  
![在这里插入图片描述][82e1ada561064427a7bc3adaee1b75bc.png]

![在这里插入图片描述][836fa61fdba64ca6bfa427edf247e24b.png]

![在这里插入图片描述][498586fd8c744e88828e99025fa310a2.png]

--------------------

## 02 matlab代码实现 ##

![在这里插入图片描述][e492926f36834404af2799e8894d382f.png]

function [dist,path] = Floyd_algorithm(D)
    
    %% 该函数用于求解一个权重邻接矩阵任意两个节点之间的最短路径
    
    % 输入：
    %        D是权重邻接矩阵
    % 输出：
    %        dist是最短距离矩阵，其元素dist_ij表示表示i,j两个节点的最短距离
    %        path是路径矩阵，其元素path_ij表示起点为i，终点为j的两个节点之间的最短路径要经过的节点
    
    n = size(D,1);  % 计算节点的个数
    
    % 初始化dist矩阵
    dist = D;
    
    % 下面我们来初始化path矩阵
    path = zeros(n);
    for j = 1:n
        path(:,j) = j;   % 将第j列的元素变为j
    end
    for i = 1:n
        path(i,i) = -1;  % 将主对角线元素变为-1
    end
    
    % 下面开始三个循环
    for k=1:n    % 中间节点k从1- n 循环
       for i=1:n     % 起始节点i从1- n 循环
          for j=1:n    % 终点节点j从1-n 循环
              if dist(i,j)>dist(i,k)+dist(k,j)  % 如果i,j两个节点间的最短距离大于i和k的最短距离+k和j的最短距离
                 dist(i,j)=dist(i,k)+dist(k,j);  % 那么我们就令这两个较短的距离之和取代i,j两点之间的最短距离
                 path(i,j)=path(i,k);   % 起点为i，终点为j的两个节点之间的最短路径要经过的节点更新为path(i,k)
                 % 注意，上面一行语句不能写成path(i,j) = k; 
              end
          end
       end
    end
    
    end

![在这里插入图片描述][935ac65dbf5747e99fba2682f0d158be.png]

%% 首先将图转换为权重邻接矩阵D
    n = 5;  %一共五个节点
    D = ones(n) ./ zeros(n);  % 全部元素初始化为Inf
    for i = 1:n
        D(i,i) = 0;  % 主对角线元素为0
    end
    D(1,2) = 3;
    D(1,3) = 8;
    D(1,5) = -4;
    D(2,5) = 7;
    D(2,4) = 1;
    D(3,2) = 4;
    D(4,3) = -5;
    D(5,4) = 6;
    D(4,1) = 2;
    
    %% 调用Floyd_algorithm函数求解
    [dist,path] = Floyd_algorithm(D)
    
    print_path(path,dist,1,5)
    print_path(path,dist,1,4)
    print_path(path,dist,3,1)
    
    clc
    disp('下面我们打印任意两点之间的最短距离：')
    print_all_path(D)

*  **path路径矩阵**  
    ![在这里插入图片描述][6c830a7254d84ff89fb2765cbaed32f1.png]

![在这里插入图片描述][3b29c3acaa044f6b87d0030941100d94.png]

function [] = print_path(path,dist,i,j)
    
    %% 该函数的作用是打印从i到j经过的最短路径
    
    % 输入：
    %        path是使用floyd算法求出来的路径矩阵
    %        dist是使用floyd算法求出来的最短距离矩阵
    %        i是起始节点的编号
    %        j是终点节点的编号
    % 输出：无
    
    if i == j
        warning('起点和终点相同，请检查后重新输入')  % 在屏幕中提示警告信息
        return;  % 不运行下面的语句，直接退出函数
    end
    if path(i,j) == j   % 如果path(i,j) = j，则有两种可能：
    % （1）如果dist(i,j) 为 Inf , 则说明从i到j没有路径可以到达
        if dist(i,j) == Inf
            disp(['从',num2str(i),'到',num2str(j),'没有路径可以到达'])
    % （2）如果dist(i,j) 不为 Inf , 则说明从i到j可直接到达，且为最短路径
        else
            disp(['从',num2str(i),'到',num2str(j),'的最短路径为'])
            disp([num2str(i),' ---> ',num2str(j)])
            disp(['最短距离为',num2str(dist(i,j))])
        end
    else  % 如果path(i,j) ~= j，则说明中间经过了其他节点：
        k = path(i,j);
        result = [num2str(i),' ---> '];  % 初始化要打印的这个字符串
        while k ~= j  % 只要k不等于j, 就一直循环下去
            result = [result , num2str(k) , ' ---> ' ];  % i先走到k这个节点处
            k = path(k,j);
        end
        result = [result , num2str(k)];
        disp(['从',num2str(i),'到',num2str(j),'的最短路径为'])
        disp(result)
        disp(['最短距离为',num2str(dist(i,j))])
    end
    
    end

![在这里插入图片描述][e149a32464eb4aaca07672e8b5f649e1.png]

![在这里插入图片描述][a0596a45a7be46ce99c51d826429b74c.png]

![在这里插入图片描述][7b105e691afb4fe2a5a9cfbb36dace27.png]

unction [] = print_all_path(D)
    
    %% 该函数的作用是求解一个权重邻接矩阵任意两个节点之间的最短路径,并打印所有的结果出来
    
    % 输入：
    %        D是权重邻接矩阵
    % 输出：无
    
    [dist,path] = Floyd_algorithm(D);   % 调用之前的Floyd_algorithm函数
    n = size(D,1);
    if n == 1
        warning('请输入至少两阶以上的权重邻接矩阵')   % 在屏幕中提示警告信息
        return;   % 不运行下面的语句，直接退出函数
    end
    
    for i = 1:n
        for j = 1:n
            if i ~= j  % 不等号用~=表示
                print_path(path,dist,i,j);   % 调用之前的print_path函数
                disp('-------------------------------------------')
                disp('  ')
            end
        end
    end
    
    end

## 03 示例 ##

![在这里插入图片描述][2961891510104287b2ae459b1faf17c9.png]

![在这里插入图片描述][d5bb8db31bc5481aa29f80d1f10e9335.png]

%% 首先将图转换为权重邻接矩阵D
    n = 9;  %一共九个节点
    D = zeros(n);  % 全部元素初始化为0, 等会你们就知道为什么这样设置啦
    % 因为是无向图，所以权重邻接矩阵是一个对称矩阵
    D(1,2) = 4; D(1,8) = 8; 
    D(2,8) = 3; D(2,3) = 8;
    D(8,9) = 1; D(8,7) = 6; 
    D(9,7) = 6; D(9,3) = 2;
    D(7,6) = 2; D(3,4) = 7; 
    D(3,6) = 4; D(6,4) = 14;
    D(4,5) = 9; D(6,5) = 10;
    D = D+D';   % 这个操作可以得到对称矩阵的另一半
    for i = 1:n
        for j = 1:n
            if (i ~= j) && (D(i,j) == 0)  
                D(i,j) = Inf;   % 将非主对角线上的0元素全部变为Inf
            end
        end
    end
    
    %% 调用Floyd_algorithm函数求解
    [dist,path] = Floyd_algorithm(D)
    
    
    % % 注意：代码文件仅供参考，一定不要直接用于自己的数模论文中
    % % 国赛对于论文的查重要求非常严格，代码雷同也算作抄袭

[6bed46bdd1b840d28a0e294bc58cb3a4.png]: https://img-blog.csdnimg.cn/6bed46bdd1b840d28a0e294bc58cb3a4.png
[https_csacademy.com_app_graph_editor]: https://csacademy.com/app/graph_editor/
[6d404c3738ae460985bacdf63855193b.png]: https://img-blog.csdnimg.cn/6d404c3738ae460985bacdf63855193b.png
[f688ca7d86a14c73abb0cd2896b730d3.png]: https://img-blog.csdnimg.cn/f688ca7d86a14c73abb0cd2896b730d3.png
[c0b375681c0a4136a113056ba10aabc0.png]: https://img-blog.csdnimg.cn/c0b375681c0a4136a113056ba10aabc0.png
[7d50f9396182420ebd808a38410d72c0.png]: https://img-blog.csdnimg.cn/7d50f9396182420ebd808a38410d72c0.png
[Link 1]: https://www.bilibili.com/video/av54668527
[312ce5f1137d4cb4921056e770ceac1c.png]: https://img-blog.csdnimg.cn/312ce5f1137d4cb4921056e770ceac1c.png
[fc754d691b3d42e79ae5928844d2f2e7.png]: https://img-blog.csdnimg.cn/fc754d691b3d42e79ae5928844d2f2e7.png
[3ce69b22e95148e8bfddf912f3056111.png]: https://img-blog.csdnimg.cn/3ce69b22e95148e8bfddf912f3056111.png
[254a4125b8924d5ebe3591b6bab15ee1.png]: https://img-blog.csdnimg.cn/254a4125b8924d5ebe3591b6bab15ee1.png
[32848024f4aa49fe93c00b29eb6f8223.png]: https://img-blog.csdnimg.cn/32848024f4aa49fe93c00b29eb6f8223.png
[390f452f01884c9b929bb75af689305c.png]: https://img-blog.csdnimg.cn/390f452f01884c9b929bb75af689305c.png
[bed29d6c74984408afcf76f00ef8e799.png]: https://img-blog.csdnimg.cn/bed29d6c74984408afcf76f00ef8e799.png
[e0c3e0ab236a43249a9770480d3f57a7.png]: https://img-blog.csdnimg.cn/e0c3e0ab236a43249a9770480d3f57a7.png
[0bd13c3ebfdd4313a96d1e422f9512e5.png]: https://img-blog.csdnimg.cn/0bd13c3ebfdd4313a96d1e422f9512e5.png
[1e0230c7cf9f473b93c7290306db811f.png]: https://img-blog.csdnimg.cn/1e0230c7cf9f473b93c7290306db811f.png
[b0d45ba2005540488143dc5370a5d57e.png]: https://img-blog.csdnimg.cn/b0d45ba2005540488143dc5370a5d57e.png
[e16d29a5711048a8b448daf53a22a30a.png]: https://img-blog.csdnimg.cn/e16d29a5711048a8b448daf53a22a30a.png
[424ff7e67dca410c8e887cb9295994b6.png]: https://img-blog.csdnimg.cn/424ff7e67dca410c8e887cb9295994b6.png
[07f10f2a44a0483e8b18cf8ec32818fd.png]: https://img-blog.csdnimg.cn/07f10f2a44a0483e8b18cf8ec32818fd.png
[796138102408429b8c1c21f6548a80a9.png]: https://img-blog.csdnimg.cn/796138102408429b8c1c21f6548a80a9.png
[1f569b63d0f7441081654e81aca263cc.png]: https://img-blog.csdnimg.cn/1f569b63d0f7441081654e81aca263cc.png
[21faa48d1bd5442db91e4fd70a7b0dc6.png]: https://img-blog.csdnimg.cn/21faa48d1bd5442db91e4fd70a7b0dc6.png
[a17ad111417a4554951e2a0724081dc8.png]: https://img-blog.csdnimg.cn/a17ad111417a4554951e2a0724081dc8.png
[e1b2d184230d423f9b36fb291cdeebe9.png]: https://img-blog.csdnimg.cn/e1b2d184230d423f9b36fb291cdeebe9.png
[ebcd0db302204b0d91ca350dc6ae1666.png]: https://img-blog.csdnimg.cn/ebcd0db302204b0d91ca350dc6ae1666.png
[579bbf3735b04e2a91e83a00aa2caa04.png]: https://img-blog.csdnimg.cn/579bbf3735b04e2a91e83a00aa2caa04.png
[aeb1482750fc4488b9fbc00cfb173a55.png]: https://img-blog.csdnimg.cn/aeb1482750fc4488b9fbc00cfb173a55.png
[c96ec25d0930483bb898eaaad78b48fc.png]: https://img-blog.csdnimg.cn/c96ec25d0930483bb898eaaad78b48fc.png
[f4ce2429c39540989538def478a57421.png]: https://img-blog.csdnimg.cn/f4ce2429c39540989538def478a57421.png
[fc11f02f25ae4677ad08c56eb18653d6.png]: https://img-blog.csdnimg.cn/fc11f02f25ae4677ad08c56eb18653d6.png
[82116fca446e40b1bb383b1d122b24c8.png]: https://img-blog.csdnimg.cn/82116fca446e40b1bb383b1d122b24c8.png
[19d748da4eba41c8b6b212599ecec115.png]: https://img-blog.csdnimg.cn/19d748da4eba41c8b6b212599ecec115.png
[82e1ada561064427a7bc3adaee1b75bc.png]: https://img-blog.csdnimg.cn/82e1ada561064427a7bc3adaee1b75bc.png
[836fa61fdba64ca6bfa427edf247e24b.png]: https://img-blog.csdnimg.cn/836fa61fdba64ca6bfa427edf247e24b.png
[498586fd8c744e88828e99025fa310a2.png]: https://img-blog.csdnimg.cn/498586fd8c744e88828e99025fa310a2.png
[e492926f36834404af2799e8894d382f.png]: https://img-blog.csdnimg.cn/e492926f36834404af2799e8894d382f.png
[935ac65dbf5747e99fba2682f0d158be.png]: https://img-blog.csdnimg.cn/935ac65dbf5747e99fba2682f0d158be.png
[6c830a7254d84ff89fb2765cbaed32f1.png]: https://img-blog.csdnimg.cn/6c830a7254d84ff89fb2765cbaed32f1.png
[3b29c3acaa044f6b87d0030941100d94.png]: https://img-blog.csdnimg.cn/3b29c3acaa044f6b87d0030941100d94.png
[e149a32464eb4aaca07672e8b5f649e1.png]: https://img-blog.csdnimg.cn/e149a32464eb4aaca07672e8b5f649e1.png
[a0596a45a7be46ce99c51d826429b74c.png]: https://img-blog.csdnimg.cn/a0596a45a7be46ce99c51d826429b74c.png
[7b105e691afb4fe2a5a9cfbb36dace27.png]: https://img-blog.csdnimg.cn/7b105e691afb4fe2a5a9cfbb36dace27.png
[2961891510104287b2ae459b1faf17c9.png]: https://img-blog.csdnimg.cn/2961891510104287b2ae459b1faf17c9.png
[d5bb8db31bc5481aa29f80d1f10e9335.png]: https://img-blog.csdnimg.cn/d5bb8db31bc5481aa29f80d1f10e9335.png