图论相关算法

一、迪杰斯特拉(Dijkstra)算法

• 迪杰斯特拉算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。这是一个贪心算法。
  • 注意：此算法只适用于求有向图或边权值非负的无向图。

1.核心思想

（1）每次选中一个点，这个点满足两个条件：

• 未被选过
• 距离最短

（2）对于这个点的所有邻近点都尝试去松弛

2.算法步骤实现

•  图片转自：这个博主

详细代码实现：图-迪杰斯特拉（Dijkstra）算法详解（含全部代码）_dijkstra算法-CSDN博客