最短路径vs Dijkstra算法
我从Cormen的第3版参考文献“算法简介”中找到的伪代码实现了Dijkstra算法，用于单源最短路径问题。
我的实现是在python上使用链表来表示邻接列表表示中的图。 这意味着节点列表是一个链表，每个节点都有一个链表来表示每个节点的边界。 此外，我没有为算法需要的最小优先级队列实现或使用任何二进制堆或斐波那契堆，因此我在节点链接列表中搜索O（V）时间内的每个节点，以便在过程需要提取下一个与源距离最小的节点。
另一方面，该参考文献还为DAG（我已经实现）提供了一种算法，在对所有边应用松弛程序之前，使用拓扑排序算法。
在所有这些背景下，我有一个复杂度为Dijkstra的算法
ø（V ^ 2）
以及一个复杂度为DAG的DAG最短路径算法
O（V + E）
通过使用timeit.default_timer()函数来计算算法的运行时间，我发现Dijkstra算法在DAG算法应用于具有正边权重和不同图密度的DAG时速度更快，全部用于100和1000个节点。
对于DAG，DAG最短路径算法不应该比Dijkstra更快吗？
链接地址: http://www.djcxy.com/p/35189.html