Dijkstra最短路径算法优化

Question

首先我想说我的代码按预期工作，而且相当快。然而分析它，大部分时间都花在一个非常具体的部分，这让我问：有没有普遍接受的更好的解决方案？

这是我的实现：

            var cellDistance = new double[cells.Count];
            cellDistance.SetAll(idx => idx == startCellIndex ? 0 : double.PositiveInfinity);

            var visitedCells = new HashSet<int>();

            do
            {
                // current cell is the smallest unvisited tentative distance cell 
                var currentCell = cells[cellDistance.Select((d, idx) => (d, idx)).OrderBy(x => x.d).First(x => !visitedCells.Contains(cells[x.idx].Index)).idx];

                foreach (var neighbourCell in currentCell.Neighbours)
                    if (!visitedCells.Contains(neighbourCell.Index))
                    {
                        var distanceThroughCurrentCell = cellDistance[currentCell.Index] + neighbourCell.Value;
                        if (cellDistance[neighbourCell.Index] > distanceThroughCurrentCell)
                        {
                            cellDistance[neighbourCell.Index] = distanceThroughCurrentCell;
                            prevCell[neighbourCell] = currentCell;
                        }
                    }

                visitedCells.Add(currentCell.Index);
            } while (visitedCells.Count != cells.Count && !visitedCells.Contains(endCell.Index));

大部分时间花在这条线上，取部分成本最低的未访问节点：

var currentCell = cells[cellDistance.Select((d, idx) => (d, idx)).OrderBy(x => x.d).First(x => !visitedCells.Contains(cells[x.idx].Index)).idx];

更具体地说，在最后一个 lambda 中，不是排序（这让我感到非常惊讶）：

x => !visitedCells.Contains(cells[x.idx].Index)

由于 visitedCells 已经是 HashSet，仅使用内置数据结构我无法改进太多，所以我的问题是：是否有不同的存储方式使此特定查询（即具有最低部分成本的未访问节点）明显更快的部分成本？

我正在考虑某种排序字典，但我需要一个按值排序的字典，因为如果它按键排序，我就必须将部分成本作为键，这使得更新成本高昂并且然后提出了关于我如何将这个结构映射到我的成本数组的问题，这仍然没有解决我的 visitedCells 查找。

Answer 1

使用标志数组代替 HashSet

HashSet 可以具有 O(1) 的分摊插入时间和预期查询时间。但是，由于您的节点 ID 只是数组的索引，因此它们是连续的并且不会增长太多。此外，您最终将在 HashSet 中拥有所有 ID。在这种情况下，您有比使用“任何”通用哈希 table 更快的 O(1) 选项。您可以使用一个布尔数组来显示是否访问了一个节点，并使用节点 ID 对其进行索引。

简单地分配一个大小等于节点数的布尔数组。用 false 填充它。当你访问一个新节点时，将节点id的值设置为true。

迭代所有节点而不是对它们进行排序以选择下一个节点

您当前的代码必须根据节点的距离对所有节点进行排序，然后一个一个地遍历它们以找到第一个未访问的节点。由于排序，这在大多数情况下需要 θ(nlogn) 时间。（可以对节点进行部分排序进行优化，但如果 compiler/library 可以自己看到这个机会，那将是非常令人惊讶的。）使用这种方法，您的总时间复杂度变为 θ(n^2 * logn) .相反，您可以遍历节点一次，跟踪到目前为止看到的最小距离未访问节点。这适用于 θ(n)。总时间复杂度为 O(n^2)，Dijkstra 应该如此。

通过这两项更改，您的代码将不会剩下太多 Dijkstra 最短路径不需要的内容。

I was considering some kind of sorted dictionary, but that I'd need one that sorts by value, because if it's sorted by key I'd have to make the partial cost the key, which makes updating it costly and then poses the problem as to how I map this structure to my cost array

有一种称为最小堆的数据结构，可用于从集合中提取最小值（连同它的卫星数据）。一个简单的二进制最小堆可以提取最小密钥或减少它在 θ(logn) 最坏情况下持有的一些密钥。

在 Dijkstra 的情况下，您需要有一个稀疏图，这样比遍历所有距离更有效（稀疏图≈边数远小于节点数的平方）。因为算法每次放松边缘时可能需要减少距离。

如果有θ(n^2)条边，则最坏情况总时间复杂度为θ(n^2 * logn)。

如果有 θ(n^2 / logn) 条边，则松弛时间变为 O(n^2)。然后，您需要一个比这个更稀疏的图，因为二叉堆比使用简单数组更有效。

在最坏的情况下，从堆中提取所有最小距离节点需要θ(nlogn)时间，放松所有边需要θ(e * logn)时间，其中e为边数，总时间为θ( (n+e)logn)。正如我所说，只有当 e 渐近地小于 n^2 / logn 时，这才能比 θ(n^2) 更有效。

Dijkstra最短路径算法优化

Dijkstra's shortest path algorithm optimization

dijkstra

data-structures