Car*_*son 5 algorithm dijkstra bucket data-structures
我正在阅读有关最短路径算法实现的一些内容,并且已经反复尝试使用Double-Bucket数据结构实现Dijkstra算法是一个很好的实现.
但是我似乎无法找到双桶实现的实际含义,维基百科上的文章有点模糊.从我所看到的它类似于哈希表/地图.我之前从未在数据结构或算法类中听说过这个.
我正在阅读的特定论文是这样的,
Cherkassky,BV,Goldberg,AV,&Radzik,T.(1996).最短路径算法:理论和实验评估.数学规划,73(2),129-174.
桶数据结构是将键值作为桶的索引，将相同键值的项存储在对应的桶中的数据结构。自然地，使用带有整数键值的桶数据结构是最有意义的。
假设B是一个bucket数据结构，bucketB[x]存储键值为 的所有项目x。
以最短路径问题为例，如果您有 3 个节点u，v并且w在 Frontier 集中，其中当前已知的最短距离分别为 3、3 和 7，则B[3] = {u, v}和B[7] = {w}。
与最短路径问题相关的bucket数据结构的时间分析：
O(1)O(1)O(1)O(c)，其中c是最大键值。因此，如果 Dijkstra 的算法是用桶数据结构实现的，那么O(m + nc)你的总时间复杂度m是边n数，是节点数。
双桶数据结构，在大多数情况下，是指每个桶包含一个桶数据结构的桶数据结构。