c++ - 用邻接表 C++ 实现 Dijkstra

Question

我正在尝试为具有用户定义对象的邻接表编写 Dijkstra 算法。

这个项目是我工作的一部分，所以我必须保持通用。

我正在使用邻接表和 STL 优先级队列

这是我比较不同节点的方式

class priorityQueueCompareNodes
{
    public:
    bool operator() ( const Node& leftSideNode, 
                  const Node& rightSideNode  )
    {
        return leftSideNode.cost > rightSideNode.cost;
    }
};

这就是我弹出和插入优先级队列的方式。

//get the node with the lowest cost from the priority queue
Node closestNode = priorityQueue.top();

//pop this node from the queue
priorityQueue.pop();

当我放宽边并更改不同节点的成本时，我更改了邻接列表，而不是优先级队列。

我的问题是如何更改优先级队列中的值，以便每次放宽边权重和更改距离/ parent 时我都有一个更新的优先级队列。

谢谢大家

Answer 1

使用任何类型的指针来访问 std::priority_queue 的内部工作机制以更新其中的元素是有问题的。例如，在最小优先级队列中，数据结构保证节点的值小于其子节点的值。如果您选择更新优先级队列中的值，则必须手动执行冒泡操作以保持该保证的完整性。手动进行向上/向下冒泡操作有点胜过使用像 std::priority_queue 这样的集合。

使用 std::set 提供了一个可行的替代方案。要检索最小值和最大值，您可以简单地使用集合的 begin 和 rbegin 指针。除了集合之外，您还应该为节点保留一个最小距离 M 的数组/vector (即随机访问集合)。每当您的松弛产生到节点 v 的较短路径时，您可以删除 v 的旧集合条目，更新 M[v]，并且将 v 的条目插入到具有新 M[v] 值的集合中。更新 M[v] 是在恒定时间内完成的，而设置操作需要 O(log|V|) 时间。因此，尽管它具有比优先级队列更大的常数因子，但使用集合具有相同的渐近复杂度。

下面是一个说明用法的伪代码。由于您的代码不完整，我求助于使用标准数据类型。图的顶点是 0 索引的，对于 v_i，邻接列表 adjList 在 adjList[i] 中保留一个出边 vector .对于每条边，分别保留目标顶点的索引和该边的权重。

void dijkstra(vector< vector< pair<int, long long> > >& adjList, int source) {
    set< pair<long long, int> > priorityQueue;
    vector< long long > minCosts(adjList.size(), INFINITY);
    minCosts[source] = 0LL;
    priorityQueue.insert( make_pair(minCosts[source], source) );

    while(!priorityQueue.empty()) {
        set< pair<long long, int> >::iterator it = priorityQueue.begin();
        int u = it->second;
        long long costU = it->first;

        for(int i=0; i < adjList[u].size(); ++i) {
            int v = adjList[u][i].first;
            long long w = adjList[u][i].second;
            if (costU + w < minCosts[v]) {
                if(minCosts[v] < INFINITY) {
                    priorityQueue.erase( make_pair(minCosts[v], v) );
                }
                minCosts[v] = costU + w;
                priorityQueue.insert( make_pair(minCosts[v], v) );
            }
        }
    }

    // minCosts[] now keeps the minimal distance of all nodes from source
}

显然，边缘成本和相关邻接表条目的检索在您的代码库中可能有所不同，但由于您没有提供这些细节，我试图提供一个更通用的代码示例，它可以最低限度地强调这一点。基本上，该集合可能只分别保留一对成本和节点索引，并且您已经准备就绪。

或者，您可以为 vehicleNode 类型定义一个比较运算符，并将其保留在集合中，而不是一对成本 & 节点。但这只是一个特定于实现的决定，而不是您问题的重点。