Dijkstra Shortest Path Algorithm in Java – Java中的Dijkstra最短路径算法

1. Overview

1.概述

The emphasis in this article is the shortest path problem (SPP), being one of the fundamental theoretic problems known in graph theory, and how the Dijkstra algorithm can be used to solve it.

本文的重点是最短路径问题（SPP），它是图论中已知的基本理论问题之一，以及如何使用Dijkstra算法来解决它。

The basic goal of the algorithm is to determine the shortest path between a starting node, and the rest of the graph.

该算法的基本目标是确定一个起始节点与图的其他部分之间的最短路径。

2. Shortest Path Problem With Dijkstra

2.使用Dijkstra的最短路径问题

Given a positively weighted graph and a starting node (A), Dijkstra determines the shortest path and distance from the source to all destinations in the graph:

给定一个正加权图和一个起始节点（A），Dijkstra确定从源头到图中所有目的地的最短路径和距离。

The core idea of the Dijkstra algorithm is to continuously eliminate longer paths between the starting node and all possible destinations.

Dijkstra算法的核心思想是不断消除起始节点和所有可能的目的地之间的较长路径。

To keep track of the process, we need to have two distinct sets of nodes, settled and unsettled.

为了跟踪这一过程，我们需要有两组不同的节点，即已解决和未解决的节点。

Settled nodes are the ones with a known minimum distance from the source. The unsettled nodes set gathers nodes that we can reach from the source, but we don’t know the minimum distance from the starting node.

已解决的节点是那些与源头有已知最小距离的节点。未解决的节点集聚集了我们从源头可以到达的节点，但我们不知道与起始节点的最小距离。

Here’s a list of steps to follow in order to solve the SPP with Dijkstra:

下面是用Dijkstra解决SPP的步骤列表。

• Set distance to startNode to zero.
• Set all other distances to an infinite value.
• We add the startNode to the unsettled nodes set.
• While the unsettled nodes set is not empty we:
  • Choose an evaluation node from the unsettled nodes set, the evaluation node should be the one with the lowest distance from the source.
  • Calculate new distances to direct neighbors by keeping the lowest distance at each evaluation.
  • Add neighbors that are not yet settled to the unsettled nodes set.

These steps can be aggregated into two stages, Initialization and Evaluation. Let’s see how does that apply to our sample graph:

这些步骤可以归纳为两个阶段，即初始化和评估。让我们看看这如何适用于我们的样本图。

2.1. Initialization

2.1.初始化

Before we start exploring all paths in the graph, we first need to initialize all nodes with an infinite distance and an unknown predecessor, except the source.

在我们开始探索图中的所有路径之前，我们首先需要初始化所有具有无限距离和未知前身的节点，除了源头。

As part of the initialization process, we need to assign the value 0 to node A (we know that the distance from node A to node A is 0 obviously)

作为初始化过程的一部分，我们需要给节点A赋值0（我们知道从节点A到节点A的距离显然是0）。

So, each node in the rest of the graph will be distinguished with a predecessor and a distance:

因此，图的其余部分中的每个节点将以一个前任和一个距离来区分。

To finish the initialization process, we need to add node A to the unsettled nodes set it to get picked first in the evaluation step. Keep in mind, the settled nodes set is still empty.

为了完成初始化过程，我们需要将节点A添加到未解决的节点集中，以便在评估步骤中首先被选中。请记住，定居的节点集仍然是空的。

2.2. Evaluation

2.2.评估

Now that we have our graph initialized, we pick the node with the lowest distance from the unsettled set, then we evaluate all adjacent nodes that are not in settled nodes:

现在我们的图已经初始化了，我们从未解决的集合中挑选出距离最小的节点，然后我们评估所有不在解决节点中的相邻节点。

The idea is to add the edge weight to the evaluation node distance, then compare it to the destination’s distance. e.g. for node B, 0+10 is lower than INFINITY, so the new distance for node B is 10, and the new predecessor is A, the same applies to node C.

这个想法是将边缘权重加到评估节点的距离上，然后与目的地的距离进行比较。例如，对于节点B来说，0+10低于INFINITY，所以节点B的新距离是10，新的前身是A，同样适用于节点C。

Node A is then moved from the unsettled nodes set to the settled nodes.

然后，节点A被从未解决的节点集移到已解决的节点。

Nodes B and C are added to the unsettled nodes because they can be reached, but they need to be evaluated.

节点B和C被添加到未解决的节点中，因为它们可以被到达，但需要被评估。

Now that we have two nodes in the unsettled set, we choose the one with the lowest distance (node B), then we reiterate until we settle all nodes in the graph:

现在，我们在未解决的集合中有两个节点，我们选择距离最小的一个（节点B），然后我们重申，直到我们解决图中的所有节点。

Here’s a table that summarizes the iterations that were performed during evaluation steps:

这里有一个表格，总结了评估步骤中的迭代情况。

The notation B-22, for example, means that node B is the immediate predecessor, with a total distance of 22 from node A.

例如，符号B-22意味着节点B是直接的前身，与节点A的总距离为22。

Finally, we can calculate the shortest paths from node A are as follows:

最后，我们可以计算出从节点A出发的最短路径如下。

• Node B : A –> B (total distance = 10)
• Node C : A –> C (total distance = 15)
• Node D : A –> B –> D (total distance = 22)
• Node E : A –> B –> D –> E (total distance = 24)
• Node F : A –> B –> D –> F (total distance = 23)

3. Java Implementation

3.Java实现

In this simple implementation we will represent a graph as a set of nodes:

在这个简单的实现中，我们将把一个图表示为一组节点。

public class Graph {

    private Set<Node> nodes = new HashSet<>();
    
    public void addNode(Node nodeA) {
        nodes.add(nodeA);
    }

    // getters and setters 
}

A node can be described with a name, a LinkedList in reference to the shortestPath, a distance from the source, and an adjacency list named adjacentNodes:

一个节点可以用名称、参考最短路径的链接列表、与源的距离以及名为相邻节点的相邻列表来描述。

public class Node {
    
    private String name;
    
    private List<Node> shortestPath = new LinkedList<>();
    
    private Integer distance = Integer.MAX_VALUE;
    
    Map<Node, Integer> adjacentNodes = new HashMap<>();

    public void addDestination(Node destination, int distance) {
        adjacentNodes.put(destination, distance);
    }
 
    public Node(String name) {
        this.name = name;
    }
    
    // getters and setters
}

The adjacentNodes attribute is used to associate immediate neighbors with edge length. This is a simplified implementation of an adjacency list, which is more suitable for the Dijkstra algorithm than the adjacency matrix.

adjacentNodes属性被用来将近邻与边长联系起来。这是一个邻接列表的简化实现，比邻接矩阵更适合Dijkstra算法。

As for the shortestPath attribute, it is a list of nodes that describes the shortest path calculated from the starting node.

至于shortestPath属性，它是一个节点列表，描述从起始节点开始计算的最短路径。

By default, all node distances are initialized with Integer.MAX_VALUE to simulate an infinite distance as described in the initialization step.

默认情况下，所有节点的距离都以Integer.MAX_VALUE初始化，以模拟初始化步骤中描述的无限距离。

Now, let’s implement the Dijkstra algorithm:

现在，让我们来实现Dijkstra算法。

public static Graph calculateShortestPathFromSource(Graph graph, Node source) {
    source.setDistance(0);

    Set<Node> settledNodes = new HashSet<>();
    Set<Node> unsettledNodes = new HashSet<>();

    unsettledNodes.add(source);

    while (unsettledNodes.size() != 0) {
        Node currentNode = getLowestDistanceNode(unsettledNodes);
        unsettledNodes.remove(currentNode);
        for (Entry < Node, Integer> adjacencyPair: 
          currentNode.getAdjacentNodes().entrySet()) {
            Node adjacentNode = adjacencyPair.getKey();
            Integer edgeWeight = adjacencyPair.getValue();
            if (!settledNodes.contains(adjacentNode)) {
                calculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
                unsettledNodes.add(adjacentNode);
            }
        }
        settledNodes.add(currentNode);
    }
    return graph;
}

The getLowestDistanceNode() method, returns the node with the lowest distance from the unsettled nodes set, while the calculateMinimumDistance() method compares the actual distance with the newly calculated one while following the newly explored path:

getLowestDistanceNode()方法，返回与未解决的节点集距离最小的节点，而calculateMinimumDistance()方法比较实际距离和新计算的距离，同时沿着新探索的路径。

private static Node getLowestDistanceNode(Set < Node > unsettledNodes) {
    Node lowestDistanceNode = null;
    int lowestDistance = Integer.MAX_VALUE;
    for (Node node: unsettledNodes) {
        int nodeDistance = node.getDistance();
        if (nodeDistance < lowestDistance) {
            lowestDistance = nodeDistance;
            lowestDistanceNode = node;
        }
    }
    return lowestDistanceNode;
}

private static void CalculateMinimumDistance(Node evaluationNode,
  Integer edgeWeigh, Node sourceNode) {
    Integer sourceDistance = sourceNode.getDistance();
    if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) {
        evaluationNode.setDistance(sourceDistance + edgeWeigh);
        LinkedList<Node> shortestPath = new LinkedList<>(sourceNode.getShortestPath());
        shortestPath.add(sourceNode);
        evaluationNode.setShortestPath(shortestPath);
    }
}

Now that all the necessary pieces are in place, let’s apply the Dijkstra algorithm on the sample graph being the subject of the article:

现在所有必要的部分都到位了，让我们在文章的主题样本图上应用Dijkstra算法。

Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D"); 
Node nodeE = new Node("E");
Node nodeF = new Node("F");

nodeA.addDestination(nodeB, 10);
nodeA.addDestination(nodeC, 15);

nodeB.addDestination(nodeD, 12);
nodeB.addDestination(nodeF, 15);

nodeC.addDestination(nodeE, 10);

nodeD.addDestination(nodeE, 2);
nodeD.addDestination(nodeF, 1);

nodeF.addDestination(nodeE, 5);

Graph graph = new Graph();

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);
graph.addNode(nodeE);
graph.addNode(nodeF);

graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA);

After calculation, the shortestPath and distance attributes are set for each node in the graph, we can iterate through them to verify that the results match exactly what was found in the previous section.

经过计算，图中每个节点的shortestPath和distance属性都被设置了，我们可以迭代它们来验证结果是否与上一节中发现的完全一致。

4. Conclusion

4.结论

In this article, we’ve seen how the Dijkstra algorithm solves the SPP, and how to implement it in Java.

在这篇文章中，我们已经看到了Dijkstra算法是如何解决SPP的，以及如何用Java实现它。

The implementation of this simple project can be found in the following GitHub project link.

这个简单项目的实现可以在以下GitHub项目链接中找到。