【数学建模】图论模型-Floyd算法（最优化）

矫情吗；* 2023-03-04 08:18 181阅读 0赞

### 文章目录 ###

*  一、算法介绍
 *  二、适用问题
 *  三、算法总结
 *   *  1. 步骤
 *  四、应用场景举例
 *  五、MATLAB代码
 *  六、实际案例
 *  七、论文案例片段（待完善）

> Floyd算法主要针对数学建模问题中的一些小的子问题进行求解，如果想直接使用请跳转至——**四**、**五**  
> [视频回顾][Link 1]

# 一、算法介绍 #

![Dijkstra算法能求-一个顶点到另一-顶点最短路径。它是由Di jkstra于1959年提出的。实际它能出始点到其它所有顶点的最短路径Dijkstra算法是一种标号法:给赋权图的每一一个顶点记一个数，称为顶点的标号(临时标号，称T标号，或者固定标号，称为P标号)。T标号表示从始顶点到该标点的最短路长的上界; P标号则是从始顶点到该顶点的最短路长。][Dijkstra_-_-_Di jkstra_1959_Dijkstra_T_P_T_ P]

# 二、适用问题 #

*  **图的最短路径问题，多源最短路径问题求解**
 *  **例如：**

1.  从A地到B、C、D、E的最短路径

# 三、算法总结 #

## 1. 步骤 ##

# 四、应用场景举例 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 1]

# 五、MATLAB代码 #

function [D,path,min1,path1]=floyd(a,start,terminal)
    D=a;n=size(D,1);path=zeros(n,n);
    for i=1:n
       for j=1:n
          if D(i,j)~=inf
             path(i,j)=j;
          end, 
       end,
    end
    for k=1:n
       for i=1:n
          for j=1:n
             if D(i,k)+D(k,j)<D(i,j)
                D(i,j)=D(i,k)+D(k,j);
                path(i,j)=path(i,k);
             end, 
          end, 
       end,
    end
    if nargin==3
       min1=D(start,terminal);
       m(1)=start;
       i=1;
       path1=[ ];   
       while   path(m(i),terminal)~=terminal
          k=i+1;                                
          m(k)=path(m(i),terminal);
          i=i+1;
       end
       m(i+1)=terminal;
       path1=m;
    end

# 六、实际案例 #

a= [ 0,50,inf,40,25,10;
         50,0,15,20,inf,25;
         inf,15,0,10,20,inf;
         40,20,10,0,10,25;
         25,inf,20,10,0,55;
         10,25,inf,25,55,0];
    [D, path]=floyd(a)

# 七、论文案例片段（待完善） #

[Link 1]: https://www.bilibili.com/video/BV12W411X7aE?p=6
[Dijkstra_-_-_Di jkstra_1959_Dijkstra_T_P_T_ P]: /images/20230208/e1ae96d505254194b69840e7d13a4bbb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70]: /images/20230208/92425a56dc9a4b6ba430c368ebdbb57e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 1]: /images/20230208/db12ea6e60e0484f8e6d82b2782740c1.png