最有效的最短路径算法非负边缘图

-1

什么是图形进行最有效的最短路径算法，不针对，只提供了这五个算法正面的边缘？最有效的最短路径算法非负边缘图

所以我知道Dijkstra的不能负边缘被使用，且运行时间的O（E * logV）其中，E是边和V的数量是顶点的数目，所以这将是我最好的猜测。它是否正确？

2015-10-16 martin

'DAG'是不是一个真正的算法（它是一类图），其余也不同他们做了什么：Dijkstra算法（在其原来的形式）的单一来源单一目标，贝尔曼 - 福特是单一来源所有顶点和Floyd-Warshall为您提供任意两个顶点之间的最短路径。 – biziclop

如果你能提供一个很好的启发式方法，'A *'可能是最有效的。 – piotrekg2

@ piotrekg2 ......这是Dijkstra算法的知情版本。 – biziclop

如果你需要找到一个加权图的最短路径，BFS将是最好的选择，但是如果有在边缘上的权重，而你只需要找到一个单一来源之间的最佳路线和一个或许多其他节点，迪杰斯特拉将是最好的选择。如果你需要找到两个对节点之间的最短路径（即具有多个来源），最好的选择是弗洛伊德，沃肖尔。

2015-10-16 10:58:23

回答