廖家龙的博客网站
最短路径
廖家龙 用心听，不照做
  2019-03-15 23:10:00   2024-07-18 23:46:51    122 字  1 分钟

最短路径：两个顶点之间带权路径长度最短的路径为最短路径

在带权图当中，把从一个顶点v到另一个顶点u所经历的边的权值之和称为路径的带权路径长度

Dijkstra算法：带权图单源最短路径

时间复杂度：O(|V|^2)

Dijkstra算法并不适用于含有负权边的图

Floyd算法：各顶点之间的最短路径

时间复杂度：O(|V|^3)