Дийкстра Монотони c Путь

Question

У меня есть вопрос, связанный с проверкой, является ли кратчайший путь строго монотонным c с использованием Дейкстры. Вот моя функция для проверки следующего непосещенного ближайшего узла:

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, чтобы убедиться, что веса путей строго увеличиваются или уменьшаются?

Спасибо!

Answer 1

Найти строго монотонный c кратчайший путь можно путем ослабления ребер в порядке их веса.

Допустим, мы хотим найти кратчайший восходящий путь. Мы бы расположили края в порядке возрастания, а затем расслабили бы их в этом порядке. «Расслабление» просто означает обновление веса узла в конечной точке ребра, чтобы он был равен весу ребра плюс вес его узла начальной точки, если эта сумма меньше текущего значения. Это то же самое, что расслабление остроты у Дейкстры. Это всегда будет давать кратчайший путь по возрастанию (и его можно сделать строго по возрастанию, если мы одновременно обновим веса узлов для всех одинаково оцененных ребер).

Мы также можем найти кратчайший путь по убыванию путем упорядочивания ребер в порядке убывания. Один из этих двух путей будет кратчайшим monotoni c путем.

Я думаю, вам повезет больше, если вы будете использовать этот подход с перебором отсортированных краев (за время n logn), чем пытаться l oop по узлам, как в вышеупомянутом методе - если вам нужно решить проблему, обновив только метод, который вы нам показали, это становится гораздо более сложной проблемой.