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

╰半夏微凉° 2023-03-04 08:18 74阅读 0赞

### 文章目录 ###

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

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

# 一、算法介绍 #

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

## 1. 带权邻接矩阵 ##

*  无向  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 1]
 *  有向  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 2]

# 二、适用问题 #

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

1.  从A地到B地的最短路径

# 三、算法总结 #

## 1. 步骤 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 3][]

# 四、应用场景举例（待完善） #

# 五、MATLAB代码 #

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);

# 六、实际案例 #

weight=    [0     2     8     1   Inf   Inf   Inf   Inf   Inf   Inf   Inf;
                2     0     6   Inf     1   Inf   Inf   Inf   Inf   Inf   Inf;
                8     6     0     7     5     1     2   Inf   Inf   Inf   Inf;
                1   Inf     7     0   Inf   Inf     9   Inf   Inf   Inf   Inf;
              Inf     1     5   Inf     0     3   Inf     2     9   Inf   Inf;
              Inf   Inf     1   Inf     3     0     4   Inf     6   Inf   Inf;
              Inf   Inf     2     9   Inf     4     0   Inf     3     1   Inf;
              Inf   Inf   Inf   Inf     2   Inf   Inf     0     7   Inf     9;
              Inf   Inf   Inf   Inf     9     6     3     7     0     1     2;
              Inf   Inf   Inf   Inf   Inf   Inf     1   Inf     1     0     4;
              Inf   Inf   Inf   Inf   Inf   Inf   Inf     9     2     4     0;];
    [dis, path]=dijkstra(weight,1, 11)

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

[Link 1]: https://www.bilibili.com/video/BV12W411X7aE?p=5
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70]: /images/20230208/37e621dcab2d4411a721fdaf00675bb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 1]: /images/20230208/0b521097f2b8417a885d234e588a6736.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 2]: /images/20230208/b4432827072946e9b529b540a2020210.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 3]: /images/20230208/4adbb99074df459b803e3a2cfe0babbc.png