什么是最有效的最短路径算法在一个图形上执行，该图形不是指向的，只有这五种算法中的正边缘？
BFS
DAG
Dijkstra
Floyd-Warshall
贝尔曼 - 福特
所以我知道Dijkstra不能用于负边缘并且运行时间为O（E * logV），其中E是边数，V是顶点数，所以这是我最好的猜测 . 它是否正确？
如果你需要在 unweighted 图中找到最短路径，那么BFS将是最好的选择，但是如果边上有权重，你只需找到 single source 和一个或多个其他节点之间的最佳路径，Dijkstra就会是最好的选择 . 如果你需要找到任意两对节点之间的最短路径（即有 multiple sources ），最好的选择是Floyd-Warshall .
1 回答
如果你需要在 unweighted 图中找到最短路径，那么BFS将是最好的选择，但是如果边上有权重，你只需找到 single source 和一个或多个其他节点之间的最佳路径，Dijkstra就会是最好的选择 . 如果你需要找到任意两对节点之间的最短路径（即有 multiple sources ），最好的选择是Floyd-Warshall .