最短路径问题

定义： 在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。这条路径就是两点之间的 $color{red}{最短路径}$（Shortest Path）。
- 第一个顶点为 $color{red}{源点}$ （Source ）；
- 最后一个顶点为 $color{red}{终点}$ （Destination）。

根据源点的多少和是有向图还是无向图，可以分为：

1. $color{red}{单源}$最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径。
   
   • （有向） $color{red}{无权图}$；
   • （有向） $color{red}{有权图}$。
2. $color{red}{多源}$最短路径问题：求任意两顶点间的最短路径。

无权图的单源最短路径算法

有权图的单源最短路径算法（Dijkstra算法）

多源最短路算法(Floyd算法)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!