Java中的图形：Dijkstra的算法

ゞ浴缸里的玫瑰 2023-10-04 08:53 40阅读 0赞

### **Java中的图形：Dijkstra的算法** ###

*通过奥利维拉·波波维奇（OliveraPopović） • [0评论][0]*

#### **介绍** ####

图形是存储某些类型的数据的便捷方法。该概念是从数学移植而来的，适合于计算机科学的需求。

由于许多事物可以用图形表示，因此图形遍历已成为一项常见的任务，尤其是在数据科学和机器学习中。

*  [Java中的图][Java]
    
     *  [用代码表示图][Link 1]
     *  [深度优先搜索（DFS）][DFS]
     *  [广度优先搜索（BFS）][BFS]
     *  **Dijkstra的算法**

#### **Dijkstra的算法如何工作？** ####

Dijkstra的算法在起始节点和目标节点之间的加权图中找到最便宜的路径（如果存在）。

在算法的最后，当我们到达目标节点时，可以通过从目标节点到起始节点的回溯来打印成本最低的路径。在本文的后面，我们将通过跟踪到达每个节点的方式来了解如何做到这一点。

由于这次我们将使用加权图，因此我们必须创建一个新`GraphWeighted`类，该类具有处理它们的必要方法。

Dijkstra的算法如下：

*  我们有一个`G`带有一组顶点（节点）`V`和一组边的加权图`E`
 *  我们也有一个叫做起始节点`s`，我们设置之间的距离`s`，并`s`以0
 *  将`s`节点与其他节点之间的距离标记为无穷大，即开始算法，就好像没有节点可从节点到达`s`
 *  将所有节点（除外`s`）标记为未访问，`s`如果所有其他节点都已标记为未访问，则标记为已访问（这是我们将使用的方法）
 *  只要有一个未访问的节点，请执行以下操作：
    
     *  查找`n`距起始节点距离最短的节点`s`
     *  标记`n`为已访问
     *  对于`n`和之间的每条边`m`，其中`m`未访问的地方：
        
         *  如果`cheapestPath(s,n)`\+ `cheapestPath(n,m)`< `cheapestPath(s,m)`，则更新`s`和之间的最便宜路径`m`等于`cheapestPath(s,n)`\+`cheapestPath(n,m)`

这可能看起来很复杂，但让我们来看一个使它更加直观的示例：

![c408d250e86c9033417d03d90a60fed6.png][]

我们正在寻找从节点0到节点6权重最小的路径。我们将使用矩阵/表格更好地表示算法中发生的事情。

最初，我们拥有的所有数据都是0与其相邻节点之间的距离。

![5dc98131b62a278227173f0406ffabc7.png][]

其余距离表示为正无穷大，即，从到目前为止我们处理过的任何节点（我们仅处理过0）都无法达到。

下一步是找到尚未访问过的最近节点，我们实际上可以从已处理的节点之一到达该节点。在我们的例子中，这是节点1。

现在，如有必要，我们将更新最短路径值。例如，现在可以从节点1到达节点3。

我们还将1标记为已访问。

**注意：**我们必须考虑到节点1的“成本”是多少。由于我们的起始位置为0，从0到1花费了8个单位，所以我们必须将“ 8”加到“从1移动到另一个节点。这就是为什么我们在表中加上8（从0到1的距离）+ 3（从1到3的距离）= 11而不是3的原因。

我们看到，从节点1可以到达节点2、3和4。

*  假设从0到1的最短路径花费8个单位，则节点2->从1到2的花费为7个单位，因此8 + 7大于11（0和2之间的最短路径）。这意味着我们找不到通过节点1的从0到2的更好路径，因此我们不做任何更改。
 *  节点3->从1到3的获取花费3个单位，并且由于3以前是不可达的，所以8 + 3绝对比正无穷大，因此我们在该单元格中更新表
 *  节点4->与节点3相同，以前无法访问，因此我们也更新了节点4的表

![210c7749070e31e7bce98564f82fb750.png][]

深橙色阴影有助于我们跟踪已访问的节点，我们将在后面讨论为什么添加较浅的橙色阴影。

现在，我们可以在节点2和节点3之间进行选择，因为两者都与节点0接近。

来自节点3的未访问的可达节点是节点4和5：

*  节点4->从节点3到节点4花费5个单位，而11 + 5并不比我们发现的先前的16个单位值好，因此无需更新
 *  节点5->从节点3到节点5花费2个单位，并且11 + 2优于正无穷大，因此我们更新表
 *  我们将3标记为已访问。

![ac16a96e53ba1db7f0d085c3d9cee64c.png][]

下一个要考虑的节点是节点2，但是从节点2可以到达的唯一节点是节点4，我们得到的值（11 + 9 = 20）并不比我们找到的上一个值（16）好，因此我们不做任何处理更改表，将节点2标记为已访问。

![2cc45c75883ad6a0d08b56590d8bcf5a.png][]

下一个最接近的可达节点是5，而5的未访问邻居是4和6。

*  节点4-> 13 +1优于16，因此值被更新
 *  节点6-> 13 + 8优于正无穷大，因此更新了该值
 *  将5标记为已访问。

![fb8b922a721fdff59cd237cce500535e.png][]

即使我们可以到达末端节点，也不是最接近的节点（4是），所以我们需要访问4来检查它是否有通向节点6的更好路径。

事实证明确实如此。6是从节点4可以访问的唯一未访问节点，而14 + 6小于21。因此，我们上一次更新了表。

![5bafb494a5090d6991f27e98d01c203b.png][]

由于下一个最近的，可达的，未访问的节点是我们的末端节点-算法结束并且得到了结果-0和6之间的最短路径的值为20。

但是，这并不能为我们提供0到6之间“什么是最便宜的路径”的答案，而只能告诉我们它的价值。这是浅橙色阴影出现的地方。

> 我们需要弄清楚如何到达6，然后通过检查“最短路径到6的值最后一次何时改变？”来做到这一点。

查看表，我们可以看到当我们查看节点4时该值从21变为20。我们可以通过查看当值变为20时所在的行名来看到该值，或者查看淡橙色单元格的值。值更改之前的列名称。

现在我们知道我们已经从节点4到达节点6，但是如何到达节点4？遵循相同的原理-当我们查看节点5时，我们看到4的值是最后一次更改。

将相同的原理应用于节点5->我们从节点3到达；我们从节点1到达节点3，并从我们的起始节点0到达节点1。

这为我们提供了路径0-> 1-> 3-> 5-> 4-> 6，路径的最小值从0到6。该路径有时不是唯一的，**可以**有多个具有相同路径的路径价值。

如果您希望在进入代码之前在另一个图形上练习该算法，这是另一个示例和解决方案-尝试首先自己找到解决方案。我们将寻找8到6之间的最短路径：

![fc93b1f53b4f29b3f2559581c7c0c0a1.png][]

![dccc5011cc2d38d2e240c2af3bdd68e4.png][]

**注意：** Dijkstra的算法不适用于所有类型的图。您可能已经注意到，在示例中我们没有在边缘使用任何负权重-这是由于Dijkstra不能在具有任何负权重的图形上工作的简单原因。

![ef31d9ef5b3c29a17f06bf607146a482.png][]

如果我们运行该算法，寻找0到1之间最便宜的路径，即使那是不正确的，算法也会返回0-> 2-> 1（最不昂贵的是0-> 3-> 1）。

![7e2f43c30eafb6ab972e7ce7e972c09e.png][]

Dijkstra的算法发现下一个最近的节点为1，因此它不会检查其余未访问的节点。这只是表明Dijkstra不适用于包含负边的图。

现在转到有趣的部分-实际代码。有多种方法可以为该算法设计类，但是我们选择将`EdgeWeighted`对象列表保留在`NodeWeighted`该类中，因此可以轻松访问特定节点的所有边缘。

而且，每个`EdgeWeighted`对象都包含源`NodeWeighted`对象和目标`NodeWeighted`对象，以防万一我们将来想尝试以不同的方式实现该算法。

**注意：**我们的实现在真正意义上依赖于对象相等，并且我们所有的方法都共享完全相同的`NodeWeighted`对象，因此对该对象的任何更改都会反映在整个图形上。这可能*不是*您在代码中想要的东西，但是依靠它可以使我们的代码更具可读性，并且更易于教学，因此，我们选择了这种方法。

#### **实施加权图** ####

让我们从我们将使用的最简单的类开始`EdgeWeighted`：

public class EdgeWeighted implements Comparable<EdgeWeighted> {
    
        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;
        }
    
        // ...
    }

这些`NodeWeighted`对象表示加权图中的实际节点。我们将在边缘不久之后实现该类。

现在，`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<EdgeWeighted> 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;
        }
    }

这`NodeWeighted`是一个非常简单的类，类似于我们之前使用的常规节点。这次，`Graph`该类不是保存有关节点之间边缘信息的类，而是每个节点都包含自己的邻居列表。

**订阅我们的新闻**

在收件箱中获取偶尔的教程，指南和作业。从来没有垃圾邮件。随时退订。

通讯注册

最后，让我们实现`GraphWeighted`该类，该类将利用前面的两个类来表示一个图：

public class GraphWeighted {
        private Set<NodeWeighted> 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()`方法与`addEdgeHelper()`为方便和易读而使用的方法一起：

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));
    }

至此，我们的主要逻辑`GraphWeighted`已经完成。我们只需要一些方法来打印边缘，检查两个节点之间是否存在边缘，然后重置所有访问的节点。

让我们从打印边缘开始：

public void printEdges() {
        for (NodeWeighted node : nodes) {
            LinkedList<EdgeWeighted> 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<EdgeWeighted> 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();
        }
    }

#### **实现Dijkstra算法** ####

完成加权图和节点的处理后，我们终于可以专注于Dijkstra的Algorithm本身。评论中的许多解释将花费一些时间，请耐心等待一下：

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<NodeWeighted, NodeWeighted> changedAt = new HashMap<>();
        changedAt.put(start, null);
    
        // Keeps track of the shortest path we've found so far for every node
        HashMap<NodeWeighted, Double> 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);
                }
            }
        }
    }

最后，让我们定义`closestReachableUnvisited()`一种方法，该方法评估哪个是我们可以到达但之前从未访问过的最近节点：

private NodeWeighted closestReachableUnvisited(HashMap<NodeWeighted, Double> 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;
    }

现在我们已经拥有了一切-让我们在上面的[第一个示例中][Link 2]测试我们的算法：

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

这正是我们通过手动执行算法得到的结果。

在上面的[第二个示例中][Link 3]使用它可以得到以下输出：

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

此外，在使用Dijkstra搜索两个节点之间的最便宜路径时，我们很可能在图中的起始节点和其他节点之间找到了多个其他最便宜的路径。实际上-我们找到了每个访问节点从源到节点的最便宜路径。请稍等一下，我们将在[后面的部分中][Link 4]对此进行证明。

但是，如果我们想知道起始节点与所有其他节点之间的最短路径，则需要在尚未访问的所有节点上继续运行该算法。在最坏的情况下，我们需要运行算法*numberOfNodes-1*次。

**注意：** Dijkstra的算法是*贪婪*算法的一个示例。这意味着在每一步中，该算法都会执行该步中看起来最好的操作，并且访问节点的次数不会超过一次。这样的步骤是局部最优的，但最终不一定是最优的。

这就是为什么Dijkstra的负负边缘失败的原因，它不重新访问那些通过负负边缘可能具有较便宜路径的节点，因为该节点已被访问过。但是-在没有负加权边缘的情况下，Dijkstra是全局最佳的（即，它可以工作）。

#### **迪克斯特拉的复杂性** ####

让我们考虑一下[该算法][Link 5]的[复杂性][Link 5]，看看为什么我们在类中提到`PriorityQueue`并添加了一个`compareTo()`方法`EdgeWeighted`。

Dijkstra算法的瓶颈是找到下一个最接近的，未访问的节点/顶点。使用`LinkedList`这种方法的复杂度为*O（numberOfEdges）*，因为在最坏的情况下，我们需要遍历节点的所有边缘以找到权重最小的边缘。

为了使它更好，我们可以使用Java的堆数据结构- `PriorityQueue`。使用`PriorityQueue`保证可以确保下一个最近的，未访问的节点（如果有）将是的第一个元素`PriorityQueue`。

所以-现在查找下一个最近的节点是在恒定（*O（1）*）时间中完成的，但是，保持`PriorityQueue`排序（删除使用的边并添加新的边）需要*O（log（numberOfEdges））*时间。这仍然比*O（numberOfEdges）*好得多。

此外，我们有*O（numberOfNodes）*次迭代，因此从`PriorityQueue`（需要*O（log（numberOfEdges））*时间）中删除了同样多的内容，添加所有边也需要*O（log（numberOfEdges））*时间。

使用时，总共给我们*O（（numberOfEdges + numberOfNodes）\* log（numberOfEdges））*复杂度`PriorityQueue`。

如果我们不使用`PriorityQueue`（就像我们不使用），那么复杂度将为*O（（numberOfEdges + numberOfNodes）\* numberOfEdges）*。

#### **Dijkstra算法的正确性** ####

到目前为止，我们一直在使用Dijkstra的算法，但并未真正证明它确实有效。该算法“直观”足以让我们认为这一事实是理所当然的，但让我们证明事实确实如此。

我们将使用*数学归纳法*来证明[该算法][Link 6]的[正确性][Link 6]。

> 在我们的案例中，“正确性”是什么意思？

好吧-我们想证明在算法结束时，我们找到的所有路径（我们访问过的所有节点）实际上都是从源到该节点的最便宜的路径，包括到达目标节点时的最便宜路径。它。

我们通过在开始时（对于开始节点）证明它是正确的，并在算法的每个步骤中都证明它是正确的，从而证明了这一点。

让我们为证明中需要的东西定义一些速记名称：

*  `CPF(x)`：**Ç** heapest **P** ATH **˚F**从起始节点到节点ound *X*
 *  `ACP(x)`：**甲**ctual **Ç** heapest **P** ATH从起始节点到节点*X*
 *  `d(x,y)`：节点*y*和*x*之间的边的距离/权重
 *  `V`：到目前为止访问的所有节点

好吧，所以我们想证明算法的每个步骤以及最后`x ∈ V, CPF(x) = ACP(x)`，即对于我们访问过的每个节点，我们找到的最便宜的路径实际上是该节点的最便宜的路径。

**基本情况：（**在开始时）我们在中只有一个节点`V`，这是起始节点。因此，由于`V = {start}`和`ACP(start) = 0 = CPF(start)`，我们的算法是正确的。

**归纳假设：**将一个节点添加`n`到`V`（访问该节点）后，对于每个`x ∈ V => CPF(x) = ACP(x)`

**归纳步骤：**我们知道对于`V`没有`n`我们的算法来说是正确的。我们需要证明添加新节点后它仍然正确`n`。让我们说`V'`是`V ∪ {n}`（换句话说，`V'`就是我们访问节点后获得`n`）。

因此，我们知道`V`我们算法中的每个节点都是正确的，即每个节点都是正确的`x ∈ V, CPF(x) => ACP(x)`，因此要使其成立，`V'`我们需要证明`CPF(n) = ACP(n)`。

我们将通过*矛盾来*证明这一点，也就是说，我们将假定这一点`CPF(n) ≠ ACP(n)`并证明这是不可能的。

假设`ACP(n) < CPF(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) <= ACP(n)`（因为至少有作为起点之间和许多节点`y`作为和有开始之间`n`，因为我们知道的最便宜的路径`n`经过`y`）

我们的归纳假设说，`CPF(x) = ACP(x)`这让我们将（2）更改为`CPF(x) + d(x,y) <= ACP(x)`。

由于*y*与相邻`x`，因此算法必须更新了观察`y`时的值`x`（因为`x`in `V`），因此我们知道`CPF(y) <= CPF(x) + d(x,y)`。

同样，由于该节点`n`是由算法选择的，因此我们知道该`n`节点必须是所有未访问的节点中最接近的节点（提醒：`y`也是未访问的，并且应该位于的最短路径上`n`），这意味着`CPF(n) <= CPF(y)`。

如果我们将所有这些不平等结合起来，我们将看到那`CPF(n) < ACP(n)`给我们带来了*矛盾，*即我们的假设`ACP(n) < CPF(n)`是不正确的。

*  `CPF(n) <= CPF(y)`并`CPF(y) <= CPF(x) + d(x,y)`给我们- >`CPF(n) <= CPF(x) + d(x,y)`
 *  `CPF(x) + d(x,y) <= ACP(x)`并`ACP(x) + d(x,y) <= ACP(n)`给我们- >`CPF(n) <= ACP(x)`然后给我们`CPF(n) < ACP(n)`

因此，我们的算法可以完成预期的工作。

**注意：**这也证明了到算法期间我们访问过的所有节点的路径也是到这些节点的最便宜的路径，而不仅仅是我们为目标节点找到的路径。

#### **结论** ####

图形是存储某些类型的数据的便捷方法。该概念是从数学移植而来的，适合于计算机科学的需求。由于许多事物可以用图形表示，因此图形遍历已成为一项常见的任务，尤其是在数据科学和机器学习中。

Dijkstra的算法在起始节点和目标节点之间的加权图中找到最便宜的路径（如果存在）。它始于目标节点，然后沿“最便宜”路径的加权边回溯到根节点。

[0]: https://stackabuse.com/graphs-in-java-dijkstras-algorithm/#disqus_thread
[Java]: https://stackabuse.com/graphs-in-java
[Link 1]: https://stackabuse.com/graphs-in-java-representing-graphs-in-code/
[DFS]: https://stackabuse.com/graphs-in-java-depth-first-search-dfs/
[BFS]: https://stackabuse.com/graphs-in-java-breadth-first-search-bfs/
[c408d250e86c9033417d03d90a60fed6.png]: https://img-blog.csdnimg.cn/img_convert/c408d250e86c9033417d03d90a60fed6.png
[5dc98131b62a278227173f0406ffabc7.png]: https://img-blog.csdnimg.cn/img_convert/5dc98131b62a278227173f0406ffabc7.png
[210c7749070e31e7bce98564f82fb750.png]: https://img-blog.csdnimg.cn/img_convert/210c7749070e31e7bce98564f82fb750.png
[ac16a96e53ba1db7f0d085c3d9cee64c.png]: https://img-blog.csdnimg.cn/img_convert/ac16a96e53ba1db7f0d085c3d9cee64c.png
[2cc45c75883ad6a0d08b56590d8bcf5a.png]: https://img-blog.csdnimg.cn/img_convert/2cc45c75883ad6a0d08b56590d8bcf5a.png
[fb8b922a721fdff59cd237cce500535e.png]: https://img-blog.csdnimg.cn/img_convert/fb8b922a721fdff59cd237cce500535e.png
[5bafb494a5090d6991f27e98d01c203b.png]: https://img-blog.csdnimg.cn/img_convert/5bafb494a5090d6991f27e98d01c203b.png
[fc93b1f53b4f29b3f2559581c7c0c0a1.png]: https://img-blog.csdnimg.cn/img_convert/fc93b1f53b4f29b3f2559581c7c0c0a1.png
[dccc5011cc2d38d2e240c2af3bdd68e4.png]: https://img-blog.csdnimg.cn/img_convert/dccc5011cc2d38d2e240c2af3bdd68e4.png
[ef31d9ef5b3c29a17f06bf607146a482.png]: https://img-blog.csdnimg.cn/img_convert/ef31d9ef5b3c29a17f06bf607146a482.png
[7e2f43c30eafb6ab972e7ce7e972c09e.png]: https://img-blog.csdnimg.cn/img_convert/7e2f43c30eafb6ab972e7ce7e972c09e.png
[Link 2]: https://stackabuse.com/graphs-in-java-dijkstras-algorithm/#first-example
[Link 3]: https://stackabuse.com/graphs-in-java-dijkstras-algorithm/#second-example
[Link 4]: https://stackabuse.com/graphs-in-java-dijkstras-algorithm/#correctnessofdijkstrasalgorithm
[Link 5]: https://stackabuse.com/big-o-notation-and-algorithm-analysis-with-python-examples/
[Link 6]: https://stackabuse.com/mathematical-proof-of-algorithm-correctness-and-efficiency/