算法高级（35）

2024-07-16 15:07| 来源: 网络整理| 查看: 265

前面我们学习了图算法中的最短路径算法，可以参考我的这篇博文常用的图算法：最短路径(Shortest Path)，解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。简单回顾如下：

Dijkstra最短路径算法是基于递推的思想设计的未达顶点的最短路径一定是由已达顶点的最短路径求出。Floyd最短路径算法只是Dijkstra最短路径算法的加强，其本质还是递推。Dijkstra求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。Floyd求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。Bellman-Ford求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。SPFA是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k

【本文地址】

公司简介

联系我们