创意题第 34 题这一页 http://algs4.cs.princeton.edu/44sp/.
单调最短路径。给定一个边加权有向图,找到一条从 s 到所有其他顶点的单调最短路径。如果路径上每条边的权重严格递增或严格递减,则路径是单调的。
部分解决方案:按升序放松边并找到最佳路径;然后按降序放松边缘并找到最佳路径。
我的问题:
假设我们按降序松弛边,并且我们可以选择在某个点采用多于 1 条边。我们将在什么基础上选择下一个优势?理想情况下,我们应该选择较小的边,因为它将最小化到该顶点的距离。但是,如果离开该顶点的所有边的权重都大于当前边的权重,则这样做可能会导致不再有来自该顶点的路径。
那么,我们该如何解决这个问题呢?
这个问题可以通过修改Dijkstra算法来解决。要点是放松不应该min
在每个图节点中进行操作(像往常一样),但在优先级队列中。
以下是通常 Dijkstra 算法的修改列表。我只考虑按升序排列的边松弛,这会导致严格减少最短路径(要获得增加的最短路径,请更改第 2 项和第 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;
}
}
也可以看看Ideone 上的工作代码 http://ideone.com/8JQ0tB。以及图形的可视化(通过此代码在 Graphviz 的帮助下生成),其中突出显示了严格递减的最短路径之一:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)