最短路径 | 743. 网络延迟时间：Dijkstra算法与Floyd算法

目录

• • 1 基于 Dijkstra 算法
    • • 1.1 代码说明
      • 1.2 完整代码

    • 2 基于 Floyd 算法

    • • 2.1 代码说明
      • 2.2 完整代码

前言 ：在完成「399. 除法求值」这道题目时，我注意到存在一种采用 Floyd 算法进行求解的思路，这让我意识到自己尚未系统地接触过最短路径问题的相关练习。于是，我选取了「743. 网络延迟时间」作为训练题目，其核心目标在于计算从单一起点到其余各节点的最短路径。

1 基于 Dijkstra 算法

若将起点设定为 \mathrm{2}，则人工模拟过程如图中所展示：

编写代码的过程，本质上是对前述手工模拟流程的自动化实现。

1.代码实现与功能说明

为体现两节点间不存在连通路径的情况，我们设定二者间的距离值为无限大：

    const int inf = INT_MAX / 2;
    
    
      
    

说明：此处仅对 $\mathrm