gpt4 book ai didi

algorithm - 在 O(E logV) 的图中找到单调最短路径

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:48:06 25 4
gpt4 key购买 nike

创意题第34题来自this page .

Monotonic shortest path. Given an edge-weighted digraph, find a monotonic shortest path from s to every other vertex. A path is monotonic if the weight of every edge on the path is either strictly increasing or strictly decreasing.

Partial solution: relax edges in ascending order and find a best path; then relax edges in descending order and find a best path.

我的问题:

假设我们按降序放宽边,并且我们可以选择在一个点上使用多于​​ 1 条边。我们将在什么基础上选择下一个优势?理想情况下,我们应该选择较小的边,因为它会最小化到该顶点的距离。但是,如果离开该顶点的所有边的权重都大于当前边的权重,那么这样做可能会导致该顶点没有进一步的路径。

那么,我们该如何解决这个问题呢?

最佳答案

这个问题可以通过修改Dijkstra算法来解决。要点是放松不应在每个图节点(像往常一样)中使用 min 操作,而应在优先级队列中进行。

这是对常用 Dijkstra 算法的修改列表。我只考虑按升序排列的边的松弛,这会导致最短路径严格递减(要获得递增的最短路径,请更改第 2 项和第 4 项):

  1. 通过对每个节点的传出边进行排序(按权重)来预处理图形。
  2. 每个节点都应包含出边列表中的位置(由最亮边的位置初始化)。
  3. 不需要优先级队列来支持“递减”操作(因此可以通过简单的最小堆实现)。每个顶点都被插入到优先队列中,然后在它出现在队列顶部之前永远不会改变(因此每个顶点可能在队列中表示多次)。队列条目由键(通常是路径长度)、顶点和传入边的权重组成。因此我们可以假设优先级队列包含传入边而不是顶点。
  4. 松弛过程:从队列中弹出边(以及该边结束的顶点);对顶点的所有出边按递增顺序,从图节点存储的位置开始,到出边权重大于或等于入边权重时结束,将出边插入优先级队列并推进存储位置。

该算法保证每条边最多被处理一次(如果同时考虑严格递减和严格递增路径,则最多处理两次),因此其复杂度为 O(E log E)。

C++11 实现:

void getDecreasingSP(Vertices& vertices, Edges& edges, int src)
{
for (auto& v: vertices)
sort(begin(v.outEdges), end(v.outEdges),
[&](int from, int to)
{
return edges[from].weight < edges[to].weight;
});

PQ pq;
auto& src_v = vertices[src];
for (auto e: src_v.outEdges)
{
QEntry entry {edges[e].weight, e};
pq.push(entry);
++src_v.pos;
}

while(!pq.empty())
{
QEntry top = pq.top();
pq.pop();
auto& v = vertices[edges[top.inEdge].to];

while (v.pos < int(v.outEdges.size()) &&
edges[v.outEdges[v.pos]].weight < edges[top.inEdge].weight)
{
auto e = v.outEdges[v.pos];
edges[e].backPtr = top.inEdge;
QEntry entry {top.pathWeight + edges[e].weight, e};
pq.push(entry);
++v.pos;
}

if (v.backPtr == -1)
v.backPtr = top.inEdge;
}
}

另见 working code on Ideone .以及图形的可视化(由这段代码在 Graphviz 的帮助下生成),其中突出显示了严格递减的最短路径之一:

enter image description here

关于algorithm - 在 O(E logV) 的图中找到单调最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22876105/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com