浅谈数据结构之图的面试真题-Dijkstra最短路径算法（四）

旧城等待， 2023-06-19 11:21 81阅读 0赞

[上一篇][Link 1]

### 浅谈数据结构之图的面试真题-Dijkstra最短路径算法（四） ###

*   *  算法描述
     *  操作步骤
     *  图解
     *   *   *  1.!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20191206141210191.png?x-oss-process=image/watermark,type\_ZmFuZ3poZW5naGVpdGk,shadow\_10,text\_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size\_16,color\_FFFFFF,t\_70)
             *  2.
             *  3.
             *  4.
             *  5.
             *  6.
             *  7.
             *  8.

## 算法描述 ##

通过Dijkstra计算图G中的最短路径时，需要指定起点vs(即从顶点vs开始计算)。  
此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点，而U则是记录还未求出最短路径的顶点(以及该顶点到起点vs的距离)。

## 操作步骤 ##

1.  初始时，S只包含起点vs；U包含除vs外的其他顶点，且U中顶点的距离为"起点vs到该顶点的距离"\[例如，U中顶点v的距离为(vs,v)的长度，然后vs和v不相邻，则v的距离为∞\]。
2.  从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
3.  更新U中各个顶点到起点vs的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(vs,v)的距离可能大于(vs,k)+(k,v)的距离。
4.  重复步骤(2)和(3)，直到遍历完所有顶点。

## 图解 ##

#### 1.![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70] ####

#### 2. ####

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

#### 3. ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 2]

#### 4. ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 3]

#### 5. ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 4]

#### 6. ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 5]

#### 7. ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 6]

#### 8. ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 7]

[Link 1]: https://blog.csdn.net/cuixhao110/article/details/103404039
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191206141210191.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191206141259777.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191206141325205.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191206141346349.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191206141405514.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191206141426400.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2019120614144623.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2019120614153932.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70