java - Dijkstra 单调路径

Question

我确实有一个与使用 Dijkstra 检查最短路径是否严格单调有关的问题。这是我检查下一个未访问的最近节点的功能：

private static Node nearestUnvisitedNode(HashMap<Node, Integer> shortestPathMap) {
    int shortestDistance = Integer.MAX_VALUE;
    Node nearest = null;

    for (Node node : Graph.nodes) {
        if (node.isVisited()) {
            continue;
        }

        int currentDistance = shortestPathMap.get(node);

        if (currentDistance == Integer.MAX_VALUE) {
            continue;
        }

        if (currentDistance < shortestDistance) {
            shortestDistance = currentDistance;
            nearest = node;
        }
    }

    return nearest;
}

连接到每个节点的边被排序并存储在LinkedList<Edge> edges; 一个shortestPathMap实用程序中，用于存储从起始节点到结束节点的整个路径。

我应该对该方法进行哪些更改nearestUnvisitedNode以确保路径权重严格增加或减少？

谢谢！

标签： javaalgorithmdata-structurescomputer-sciencedijkstra

Answer 1

可以通过根据权重按顺序放松边缘来找到严格单调的最短路径。

假设我们想找到最短的上升路径。我们将按升序对边进行排序，然后按该顺序放松它们。“放松”只是意味着如果总和小于当前值，则将边缘端点处节点的权重更新为边缘的权重加上其起点节点的权重。这与在 Dijkstra 中放松优势相同。这将始终产生最短的上升路径（如果我们同时更新所有等值边的节点权重，它可以严格上升）。

我们还可以通过按降序排列边来找到最短的下降路径。这两条路径之一将是最短的单调路径。

我认为使用这种在排序边上循环的方法（在 n logn 时间内）比尝试在上述方法中循环节点更幸运——如果您只需要通过更新您拥有的方法来解决问题向我们展示，它变成了一个更难的问题。