Графики на Java: алгоритм Дейкстры

Автор оригинала: Olivera Popović.

Вступление

Графики-это удобный способ хранения определенных типов данных. Концепция была перенесена из математики и приспособлена для нужд информатики.

В связи с тем, что многие вещи могут быть представлены в виде графиков, обход графиков стал обычной задачей, особенно используемой в науке о данных и машинном обучении.

• Графики на Java
  • Представление графиков в коде
  • Поиск по глубине (DFS)
  • Поиск по ширине (BFS)
  • Алгоритм Дейкстры

Как работает Алгоритм Дейкстры?

Алгоритм Дейкстры находит наименее дорогой путь в взвешенном графике между нашим начальным узлом и конечным узлом, если такой путь существует.

В конце алгоритма, когда мы прибудем на конечный узел, мы сможем напечатать путь с наименьшей стоимостью, вернувшись от конечного узла к исходному узлу. Позже в этой статье мы увидим, как мы можем это сделать, отслеживая, как мы прибыли на каждый узел.

Поскольку на этот раз мы будем использовать взвешенные графики, нам придется создать новый класс Graph Weighted , в котором есть методы, необходимые для их обработки.

Алгоритм Дейкстры работает следующим образом:

• У нас есть взвешенный граф G с набором вершин (узлов) V и набором ребер E
• У нас также есть начальный узел под названием s , и мы устанавливаем расстояние между s и s равным 0
• Отметьте расстояние между s и каждым другим узлом как бесконечное, т. Е. Запустите алгоритм так, как если бы ни один узел не был доступен из узла s
• Отметьте все узлы (кроме s ) как не посещенные или отметьте s как посещенные, если все остальные узлы уже помечены как не посещенные (именно такой подход мы будем использовать)
• Пока есть не посещенный узел, выполните следующие действия:
  • Найдите узел n , который имеет наименьшее расстояние от начального узла s
  • Отметьте n как посещенный

  • Для каждого ребра между n и m , где m не посещается:

    • Если самый дешевый путь(s,n) + самый дешевый путь(n,m) < самый дешевый путь(s,m) , обновите самый дешевый путь между s и m равным самый дешевый путь(s,n) + Самый дешевый путь(n,m)

Это может показаться сложным, но давайте рассмотрим пример, который делает это немного более интуитивным:

Мы ищем путь с наименьшим весом от узла 0 до узла 6. Мы будем использовать матрицу/таблицу, чтобы лучше представить, что происходит в алгоритме.

В начале все данные, которые у нас есть, – это расстояние между 0 и его соседними узлами.

Остальные расстояния обозначаются как положительная бесконечность, т. Е. Они недоступны ни с одного из узлов, которые мы обработали до сих пор (мы обработали только 0).

Следующий шаг-найти ближайший узел, который еще не был посещен, до которого мы действительно можем добраться с одного из обработанных узлов. В нашем случае это узел 1.

Теперь мы обновим значения кратчайшего пути, если это необходимо. Например, узел 3 теперь доступен из узла 1.

Мы также пометим 1 как посещенный.

Примечание: Мы должны учитывать, сколько “стоит” добраться до узла 1. Поскольку наша начальная позиция равна 0, а переход от 0 к 1 стоит 8 единиц, мы должны добавить эти 8 к общей стоимости “перемещения” с 1 на другой узел. Вот почему мы добавляем 8 (расстояние от 0 до 1) + 3 (расстояние от 1 до нашей таблицы, а не просто 3.

Мы видим, что из узла 1 мы можем добраться до узлов 2, 3 и 4.

• Узел 2 -> для получения от 1 до 2 стоит 7 единиц, учитывая, что кратчайший путь от 0 до 1 стоит 8 единиц, 8 + 7 больше 11 (кратчайший путь от 0 до 2). Это означает, что мы не нашли лучшего пути от 0 до 2 через узел 1, поэтому мы ничего не меняем.
• Узел 3 -> для получения от 1 до 3 стоит 3 единицы, а поскольку 3 ранее было недоступно, 8 + 3 определенно лучше, чем положительная бесконечность, поэтому мы обновляем таблицу в этой ячейке
• Узел 4 -> то же самое, что и с узлом 3, ранее недоступным, поэтому мы также обновляем таблицу для узла 4

Темно-оранжевое затенение помогает нам отслеживать узлы, которые мы посетили, мы обсудим, почему более светлый оранжевый оттенок был добавлен позже.

Теперь мы можем выбирать между узлом 2 и узлом 3, поскольку оба они “близки” к узлу 0. Давайте перейдем к узлу 3.

Не посещенные, доступные узлы из узла 3-это узлы 4 и 5:

• Узел 4 -> путь от узла 3 до узла 4 стоит 5 единиц, и 11 + 5 не лучше, чем предыдущее значение 16 единиц, которое мы нашли, поэтому нет необходимости обновлять
• Узел 5 -> добраться от узла 3 до узла 5 стоит 2 единицы, а 11 + 2 лучше, чем положительная бесконечность, поэтому мы обновляем таблицу
• Мы отмечаем 3 как посещенные.

Следующим узлом, который следует рассмотреть, является узел 2, однако единственным узлом, доступным из узла 2, является узел 4, и полученное нами значение (11 +) не лучше, чем предыдущее значение, которое мы нашли (16), поэтому мы не вносим изменений в нашу таблицу, кроме пометки узла 2 как посещенного.

Следующий ближайший доступный узел-5, а незваные соседи 5-4 и 6.

• Узел 4 -> 13 + 1 лучше, чем 16, поэтому значение обновляется
• Узел 6 -> 13 + 8 лучше, чем положительная бесконечность, поэтому значение обновляется
• Отметка 5 по мере посещения.

Несмотря на то, что мы можем добраться до конечного узла, это не ближайший доступный узел (4), поэтому нам нужно посетить 4, чтобы проверить, есть ли у него лучший путь к узлу 6.

Оказывается, так оно и есть. 6-единственный не посещенный узел, доступный с узла 4, а 14 + 6 меньше 21. Поэтому мы обновляем нашу таблицу в последний раз.

Поскольку следующий ближайший, доступный, не посещаемый узел является нашим конечным узлом – алгоритм завершен, и мы получили наш результат – значение кратчайшего пути между 0 и 6 равно 20.

Это, однако, не дает нам ответа на вопрос “КАКОЙ самый дешевый путь” между 0 и 6, он говорит нам только о его значении. Вот тут-то и появляется светло-оранжевое затенение.

Нам нужно выяснить, как мы добрались до 6, и мы делаем это, проверяя “когда в последний раз менялось значение кратчайшего пути до 6?”.

Взглянув на нашу таблицу, мы видим, что значение изменилось с 21 на 20, когда мы смотрели на узел 4. Мы можем либо увидеть это, посмотрев на имя строки, в которой мы находились, когда значение стало 20, либо на имя столбца светло-оранжевой ячейки прямо перед изменением значения.

Теперь мы знаем, что прибыли в узел 6 из узла 4, но как мы попали в узел 4? Следуя тому же принципу – мы видим, что значение 4 изменилось в последний раз, когда мы смотрели на узел 5.

Применяя тот же принцип к узлу 5 -> мы прибыли из узла 3; мы прибыли в узел 3 из узла 1, а в узел 1 из нашего начального узла, узла 0.

Это дает нам путь 0 -> 1 -> 3 -> 5 -> 4 -> 6 как путь с наименьшим значением от 0 до 6. Этот путь иногда не уникален, может быть несколько путей, имеющих одинаковое значение.

Если вы хотите попрактиковаться в алгоритме на другом графике, прежде чем мы перейдем к коду, вот еще один пример и решение – сначала попробуйте найти решение самостоятельно. Мы будем искать кратчайший путь между 8 и 6:

Примечание: Алгоритм Дейкстры работает не на всех типах графиков. Возможно, вы заметили, что мы не использовали никаких отрицательных весов на наших ребрах в наших примерах – это по той простой причине, что Дейкстра не работает на графах с отрицательными весами.

Если бы мы запустили алгоритм, ища наименее дорогой путь между 0 и 1, алгоритм вернул бы 0 -> 2 -> 1, даже если это неверно (наименее дорогой-0 – > 3 – > 1).

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

Теперь перейдем к самой интересной части – собственно коду. Существует несколько способов создания классов для этого алгоритма, но мы решили сохранить список Взвешенных по краям объектов в классе NodeWeighted , чтобы у нас был легкий доступ ко всем ребрам из определенного узла.

Кроме того, каждый Взвешенный по краю объект содержит исходный Взвешенный по узлу объект и конечный Взвешенный по узлу объект, на всякий случай, если мы захотим попробовать реализовать алгоритм по-другому в будущем.

Примечание: Наша реализация основана на равенстве объектов в истинном смысле, и все наши методы используют один и тот же объект с узловым весом , поэтому любое изменение этого объекта отражается на всем графике. Это может быть не тем, что вам нужно в вашем коде, однако, опираясь на это, наш код становится намного более читабельным и лучше подходит для образовательных целей, поэтому мы выбрали этот подход.

Реализация взвешенного графика

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

Давайте начнем с самого простого класса из всех, которые мы будем использовать, класса Взвешенный по краю :

public class EdgeWeighted implements Comparable {

    NodeWeighted source;
    NodeWeighted destination;
    double weight;

    EdgeWeighted(NodeWeighted s, NodeWeighted d, double w) {
        // Note that we are choosing to use the (exact) same objects in the Edge class
        // and in the GraphShow and GraphWeighted classes on purpose - this MIGHT NOT
        // be something you want to do in your own code, but for sake of readability
        // we've decided to go with this option
        source = s;
        destination = d;
        weight = w;
    }

    // ...
}

Объекты Взвешенные по узлам представляют фактические узлы в нашем взвешенном графике. Мы реализуем этот класс вскоре после краев.

Теперь давайте просто реализуем метод toString() для печати объектов и метод compareTo() :

public String toString() {
    return String.format("(%s -> %s, %f)", source.name, destination.name, weight);
}

// We need this method if we want to use PriorityQueues instead of LinkedLists
// to store our edges, the benefits are discussed later, we'll be using LinkedLists
// to make things as simple as possible
public int compareTo(EdgeWeighted otherEdge) {

    // We can't simply use return (int)(this.weight - otherEdge.weight) because
    // this sometimes gives false results
    if (this.weight > otherEdge.weight) {
        return 1;
    }
    else return -1;
}

Убрав наши взвешенные ребра с пути, давайте реализуем наши взвешенные узлы:

public class NodeWeighted {
    // The int n and String name are just arbitrary attributes
    // we've chosen for our nodes these attributes can of course
    // be whatever you need
    int n;
    String name;
    private boolean visited;
    LinkedList edges;

    NodeWeighted(int n, String name) {
        this.n = n;
        this.name = name;
        visited = false;
        edges = new LinkedList<>();
    }

    boolean isVisited() {
        return visited;
    }

    void visit() {
        visited = true;
    }

    void unvisit() {
        visited = false;
    }
}

Взвешенный узел |/- это довольно простой класс, напоминающий обычные узлы, которые мы использовали раньше. На этот раз класс Graph не содержит информацию о ребрах между узлами, а, скорее, каждый узел содержит список своих собственных соседей.

Наконец, давайте реализуем класс Graph Weighted , который будет использовать оба предыдущих класса для представления графика:

public class GraphWeighted {
    private Set nodes;
    private boolean directed;

    GraphWeighted(boolean directed) {
        this.directed = directed;
        nodes = new HashSet<>();
    }

    // ...
}

Чтобы сохранить наши узлы в графике, мы будем использовать Set . Они удобны для нас, так как не допускают дублирования объектов и, как правило, просты в работе.

Теперь, как обычно, давайте определим основные методы, которые мы будем использовать для построения нашего графика, начиная с метода AddNode() :

// Doesn't need to be called for any node that has an edge to another node
// since addEdge makes sure that both nodes are in the nodes Set
public void addNode(NodeWeighted... n) {
    // We're using a var arg method so we don't have to call
    // addNode repeatedly
    nodes.addAll(Arrays.asList(n));
}

И вместе с ним метод addEdge() наряду с методом added Helper () , используемым для удобства и удобства чтения:

public void addEdge(NodeWeighted source, NodeWeighted destination, double weight) {
    // Since we're using a Set, it will only add the nodes
    // if they don't already exist in our graph
    nodes.add(source);
    nodes.add(destination);

    // We're using addEdgeHelper to make sure we don't have duplicate edges
    addEdgeHelper(source, destination, weight);

    if (!directed && source != destination) {
        addEdgeHelper(destination, source, weight);
    }
}

private void addEdgeHelper(NodeWeighted a, NodeWeighted b, double weight) {
    // Go through all the edges and see whether that edge has
    // already been added
    for (EdgeWeighted edge : a.edges) {
        if (edge.source == a && edge.destination == b) {
            // Update the value in case it's a different one now
            edge.weight = weight;
            return;
        }
    }
    // If it hasn't been added already (we haven't returned
    // from the for loop), add the edge
    a.edges.add(new EdgeWeighted(a, b, weight));
}

На этом этапе наша основная логика для Взвешенного графика выполнена. Нам просто нужен какой-то метод для печати ребер, проверки наличия ребра между двумя узлами и сброса всех посещенных узлов.

Давайте начнем с краев печати:

public void printEdges() {
    for (NodeWeighted node : nodes) {
        LinkedList edges = node.edges;

        if (edges.isEmpty()) {
            System.out.println("Node " + node.name + " has no edges.");
            continue;
        }
        System.out.print("Node " + node.name + " has edges to: ");

        for (EdgeWeighted edge : edges) {
            System.out.print(edge.destination.name + "(" + edge.weight + ") ");
        }
        System.out.println();
    }
}

Теперь просто проверьте, есть ли между двумя узлами ребро:

public boolean hasEdge(NodeWeighted source, NodeWeighted destination) {
    LinkedList edges = source.edges;
    for (EdgeWeighted edge : edges) {
        // Again relying on the fact that all classes share the
        // exact same NodeWeighted object
        if (edge.destination == destination) {
            return true;
        }
    }
    return false;
}

И, наконец, метод, который сбрасывает все посещенные узлы, чтобы мы могли практически сбросить алгоритм:

// Necessary call if we want to run the algorithm multiple times
public void resetNodesVisited() {
    for (NodeWeighted node : nodes) {
        node.unvisit();
    }
}

Реализация алгоритма Дейкстры

С нашим взвешенным графиком и узлами все готово, мы можем, наконец, сосредоточиться на самом алгоритме Дейкстры. Это будет немного длинновато со многими объяснениями в комментариях, так что потерпите немного:

public void DijkstraShortestPath(NodeWeighted start, NodeWeighted end) {
    // We keep track of which path gives us the shortest path for each node
    // by keeping track how we arrived at a particular node, we effectively
    // keep a "pointer" to the parent node of each node, and we follow that
    // path to the start
    HashMap changedAt = new HashMap<>();
    changedAt.put(start, null);

    // Keeps track of the shortest path we've found so far for every node
    HashMap shortestPathMap = new HashMap<>();

    // Setting every node's shortest path weight to positive infinity to start
    // except the starting node, whose shortest path weight is 0
    for (NodeWeighted node : nodes) {
        if (node == start)
            shortestPathMap.put(start, 0.0);
        else shortestPathMap.put(node, Double.POSITIVE_INFINITY);
    }

    // Now we go through all the nodes we can go to from the starting node
    // (this keeps the loop a bit simpler)
    for (EdgeWeighted edge : start.edges) {
        shortestPathMap.put(edge.destination, edge.weight);
        changedAt.put(edge.destination, start);
    }

    start.visit();

    // This loop runs as long as there is an unvisited node that we can
    // reach from any of the nodes we could till then
    while (true) {
        NodeWeighted currentNode = closestReachableUnvisited(shortestPathMap);
        // If we haven't reached the end node yet, and there isn't another
        // reachable node the path between start and end doesn't exist
        // (they aren't connected)
        if (currentNode == null) {
            System.out.println("There isn't a path between " + start.name + " and " + end.name);
            return;
        }

        // If the closest non-visited node is our destination, we want to print the path
        if (currentNode == end) {
            System.out.println("The path with the smallest weight between "
                                   + start.name + " and " + end.name + " is:");

            NodeWeighted child = end;

            // It makes no sense to use StringBuilder, since
            // repeatedly adding to the beginning of the string
            // defeats the purpose of using StringBuilder
            String path = end.name;
            while (true) {
                NodeWeighted parent = changedAt.get(child);
                if (parent == null) {
                    break;
                }

                // Since our changedAt map keeps track of child -> parent relations
                // in order to print the path we need to add the parent before the child and
                // it's descendants
                path = parent.name + " " + path;
                child = parent;
            }
            System.out.println(path);
            System.out.println("The path costs: " + shortestPathMap.get(end));
            return;
        }
        currentNode.visit();

        // Now we go through all the unvisited nodes our current node has an edge to
        // and check whether its shortest path value is better when going through our
        // current node than whatever we had before
        for (EdgeWeighted edge : currentNode.edges) {
            if (edge.destination.isVisited())
                continue;

            if (shortestPathMap.get(currentNode)
               + edge.weight
               < shortestPathMap.get(edge.destination)) {
                shortestPathMap.put(edge.destination,
                                   shortestPathMap.get(currentNode) + edge.weight);
                changedAt.put(edge.destination, currentNode);
            }
        }
    }
}

И, наконец, давайте определим ближайший доступный незваный() метод, который оценивает, какой из ближайших узлов мы можем достичь и не посещали раньше:

private NodeWeighted closestReachableUnvisited(HashMap shortestPathMap) {

    double shortestDistance = Double.POSITIVE_INFINITY;
    NodeWeighted closestReachableNode = null;
    for (NodeWeighted node : nodes) {
        if (node.isVisited())
            continue;

        double currentDistance = shortestPathMap.get(node);
        if (currentDistance == Double.POSITIVE_INFINITY)
            continue;

        if (currentDistance < shortestDistance) {
            shortestDistance = currentDistance;
            closestReachableNode = node;
        }
    }
    return closestReachableNode;
}

Теперь, когда у нас все это есть – давайте протестируем наш алгоритм на первом примере сверху:

public class GraphShow {
    public static void main(String[] args) {
        GraphWeighted graphWeighted = new GraphWeighted(true);
        NodeWeighted zero = new NodeWeighted(0, "0");
        NodeWeighted one = new NodeWeighted(1, "1");
        NodeWeighted two = new NodeWeighted(2, "2");
        NodeWeighted three = new NodeWeighted(3, "3");
        NodeWeighted four = new NodeWeighted(4, "4");
        NodeWeighted five = new NodeWeighted(5, "5");
        NodeWeighted six = new NodeWeighted(6, "6");

        // Our addEdge method automatically adds Nodes as well.
        // The addNode method is only there for unconnected Nodes,
        // if we wish to add any
        graphWeighted.addEdge(zero, one, 8);
        graphWeighted.addEdge(zero, two, 11);
        graphWeighted.addEdge(one, three, 3);
        graphWeighted.addEdge(one, four, 8);
        graphWeighted.addEdge(one, two, 7);
        graphWeighted.addEdge(two, four, 9);
        graphWeighted.addEdge(three, four, 5);
        graphWeighted.addEdge(three, five, 2);
        graphWeighted.addEdge(four, six, 6);
        graphWeighted.addEdge(five, four, 1);
        graphWeighted.addEdge(five, six, 8);

        graphWeighted.DijkstraShortestPath(zero, six);
    }
}

Мы получаем следующий результат:

The path with the smallest weight between 0 and 6 is:
0 1 3 5 4 6
The path costs: 20.0

Именно это мы и получили, выполнив алгоритм вручную.

Использование его во втором примере выше дает нам следующий результат:

The path with the smallest weight between 8 and 6 is:
8 1 4 7 6
The path costs: 12.0

Кроме того, при поиске самого дешевого пути между двумя узлами с помощью Дейкстры мы, скорее всего, нашли несколько других самых дешевых путей между нашим начальным узлом и другими узлами на графике. На самом деле – мы нашли самый дешевый путь от источника к узлу для каждого посещенного узла. Просто посидите на этом минутку, мы докажем это в последнем разделе .

Однако, если бы мы хотели знать кратчайший путь между нашим начальным узлом и всеми другими узлами, нам нужно было бы продолжать запускать алгоритм на всех узлах, которые еще не посещены. В худшем случае нам нужно было бы запустить алгоритм количество узлов – 1 раз.

Примечание: Алгоритм Дейкстры является примером жадного алгоритма. Это означает, что на каждом шаге алгоритм делает то, что кажется лучшим на этом шаге, и не посещает узел более одного раза. Такой шаг является локально оптимальным, но не обязательно оптимальным в конечном итоге.

Вот почему Dijkstra терпит неудачу с отрицательно взвешенными ребрами, он не пересматривает узлы, у которых может быть более дешевый путь через отрицательно взвешенное ребро, потому что узел уже посещен. Однако – без отрицательно взвешенных ребер Дейкстра глобально оптимальна (т. Е. Работает).

Сложность Дейкстры

Давайте рассмотрим сложность этого алгоритма и посмотрим , почему мы упомянули Очередь приоритетов и добавили Метод compareTo() в наш Взвешенный класс.

Узким местом алгоритма Дейкстры является нахождение следующего ближайшего, не посещаемого узла/вершины. Использование Связанного списка это имеет сложность O(количество ребер) , так как в худшем случае нам нужно пройти через все ребра узла, чтобы найти тот, который имеет наименьший вес.

Чтобы сделать это лучше, мы можем использовать структуру данных кучи Java – Очередь приоритетов . Использование приоритетной очереди гарантирует нам, что следующий ближайший, не посещаемый узел (если он есть) будет первым элементом приоритетной очереди .

Итак, теперь поиск следующего ближайшего узла выполняется за постоянное ( O(1) ) время, однако для сохранения Приоритетной очереди сортировки (удаление использованных ребер и добавление новых) требуется O(журнал(количество полей)) время. Это все равно намного лучше, чем O(количество Ребер) .

Кроме того, у нас есть O(количество Узлов) итераций и, следовательно, столько же удалений из Очереди приоритетов (которые занимают O(журнал(количество страниц)) время), и добавление всех наших ребер также занимает O(журнал(количество ребер)) время.

Это дает нам в общей сложности O((количество Ребер + количество Узлов) * журнал(количество Ребер)) сложность при использовании Приоритетной очереди .

Если бы мы не использовали Очередь Приоритетов (как мы этого не делали) – сложность была бы O((количество Ребер + количество Узлов) * количество Ребер) .

Корректность алгоритма Дейкстры

До сих пор мы использовали алгоритм Дейкстры, на самом деле не доказав, что он действительно работает. Алгоритм достаточно “интуитивно понятен”, чтобы мы приняли этот факт как должное, но давайте докажем, что это действительно так.

Мы будем использовать математическую индукцию для доказательства правильности этого алгоритма .

Что означает “правильность” в нашем случае?

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

Мы доказываем это, доказывая, что это верно в начале (для начального узла), и мы доказываем, что это остается верным на каждом шаге алгоритма.

Давайте определим некоторые сокращенные названия для вещей, которые нам понадобятся в этом доказательстве:

• CPF(x) : C heapest P ath F переход от начального узла к узлу x
• ACP(x) : A ctual C heapest Цена ath от начального узла до узла x
• d(x,y) : Расстояние/вес ребра между узлами y и x
• V : Все узлы, которые были посещены до сих пор

Итак, мы хотим доказать, что на каждом шаге алгоритма и в конце x ∈ V,(x) , т. Е. Что для каждого узла, который мы посетили, самый дешевый путь, который мы нашли, на самом деле является самым дешевым путем для этого узла.

Базовый случай: (в начале) у нас есть только один узел в V , и это начальный узел. Итак , поскольку V = {start} и ACP(старт)(старт) , наш алгоритм верен.

Индуктивная гипотеза: После добавления узла n в V (посещение этого узла) для каждого x ∈ V =>(x)

Индуктивный шаг: Мы знаем, что для V без n наш алгоритм верен. Нам нужно доказать, что он остается правильным после добавления нового узла n . Допустим, что V' является V ∪ {n} (другими словами, V' – это то, что мы получаем после посещения узла n ).

Таким образом, мы знаем, что для каждого узла в V наш алгоритм верен , т. Е. Что для каждого x ∈ V CPF(x) => ACP(x) , поэтому, чтобы это было верно для V' , нам нужно доказать, что CPF(n)(n) .

Мы докажем это с помощью противоречия , то есть предположим, что CPF(n) ≠ ACP(n) и покажем, что это невозможно.

Предположим, что ACP(n) < CP(n) .

ACP(n) начинается где-то в V и в какой-то момент покидает V , чтобы добраться до n (поскольку n нет в V , он должен покинуть V ). Предположим, что некоторое ребро ( x , y ) является первым ребром, которое оставляет V , т. Е. что x находится в V , но y нет.

Мы знаем две вещи:

1. Путь, по которому мы получили ACP(x) , является подпутью пути, по которому мы получили ACP(n)
2. ACP(x) + d(x,y)(n) (поскольку между началом и y по крайней мере столько же узлов , сколько между началом и n , поскольку мы знаем, что самый дешевый путь к n проходит через y )

Наша индуктивная гипотеза гласит, что CPF(x)(x) , который давайте изменим (2) на CPF(x) + d(x,y)(x) .

Since//у//is adjacent to х , the algorithm must have updated the value of у when looking at х (since х is in V ), so we know that CPF(у) (Х) + d (х,у) .

Кроме того, поскольку узел n был выбран алгоритмом, мы знаем, что n должен быть ближайшим узлом из всех не посещенных (напоминание: y также не посещался и должен был находиться на кратчайшем пути к n ), что означает, что CPF(n)(y) .

Если мы объединим все эти неравенства, мы увидим, что CPF(n) < ACP(n) , что дает нам противоречие , т. Е. наше предположение о том, что ACP(n) < CPF(n) было неверным.

• CPF(n)(y) и CPF(y)(x) + d(x,y) дайте нам -> CPF(n)(x) + d(x,y)
• CPF(x) + d(x,y)(x) и ACP(x) + d(x,y)(n) дайте нам -> CPF(n)(x) что затем дает нам CPF(n) < ACP(n)

Поэтому наш алгоритм делает то, что должен.

Примечание: Это также доказывает, что пути ко всем узлам, которые мы посетили во время алгоритма, также являются самыми дешевыми путями к этим узлам, а не только путь, который мы нашли для узла назначения.

Вывод

Графики-это удобный способ хранения определенных типов данных. Концепция была перенесена из математики и приспособлена для нужд информатики. В связи с тем, что многие вещи могут быть представлены в виде графиков, обход графиков стал обычной задачей, особенно используемой в науке о данных и машинном обучении.

Алгоритм Дейкстры находит наименее дорогой путь в взвешенном графике между нашим начальным узлом и конечным узлом, если такой путь существует. Он начинается с узла назначения и возвращается обратно к корневому узлу по взвешенным краям “самого дешевого” пути для пересечения.