陈越《数据结构》第七讲 图(中)二

最短路径问题


定义: 在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径。这条路径就是两点之间的 (Shortest Path)。
- 第一个顶点 (Source );
- 最后一个顶点 (Destination)。

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

  1. 最短路径问题:从某固定源点出发,求其到所有其他顶点的最短路径。
    • (有向)
    • (有向)
  2. 最短路径问题:求任意两顶点间的最短路径。

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


有权图的单源最短路径算法(Dijkstra算法)


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

相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院