翻译自(https://www.baeldung.com/java-dijkstra)

1. 概览

本文要讨论的是最短路径算法(SPP, shortest path problem),SPP是图论中一个知名的基础理论问题，我们将研究如何使用Dijkstra算法来解决这个问题。

这个算法的基本目的是计算起始节点与图的其余部分之间的最短路径。

2. Dijkstra算法解决最短路径

Dijkstra 算法是一种用于计算带权有向图中单源最短路径（SSSP：Single-Source Shortest Path）的算法，由计算机科学家 Edsger Dijkstra 于 1956 年构思并于 1959 年发表。其解决的问题是：给定图 G 和源顶点 v，找到从 v 至图中所有顶点的最短路径。

An image

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

为了跟踪解决过程，我们需要建立两个不同的节点集，已解决的和未解决的。

已解决节点集合是已知的从起点开始的最小路径节点。未解决的节点集合存放了我们可以从起点到达的节点，但是我们还不知道到起始节点的最小距离。我们列出Dijkstra算法解决SPP问题的步骤

把起始节点的距离设为0
将所有其他距离设为无穷大值
我们将其实节点添加到未解决的节点集合中。
当未解决节点非空时，我们再做如下操作:
- 从未解决节点集合中选择一个评估节点，评估节点应该是与起点的距离最小的节点
- 计算到直接邻居节点的距离，并为每一个评估节点保留最小距离。
- 把还没有解决的邻居节点加入未解决节点点集合.

上面的步骤可以归纳成2个阶段，初始化节点和评估阶段。我们来看一下，如何应用到样图上。

2.1. 初始阶段

在我们开始探索图中的所有路径之前，除了初始节点，我们首先要用无限距离和未知前置节点来初始化所有其他节点。

在初始化过程中，我们把0分给节点A，因为我们清楚的知道节点A到节点A的距离是0

这样，图中的其他节点都使用前置节点和距离来进行识别。X表示未知的前置节点。

An image

为了完成初始化过程，我们需要将节点A添加到未解决的节点集合中，节点A在评估步骤中讲首先被选择。记住，这时候解决节点集仍然是空的。

2.2. 评估

现在图已经初始化完毕了，我们从未解决节点集合中选择最小路径的节点，然后评估所有不在解决节点集中的相邻节点。 An image

其思想是将边缘权值与评估节点距离相加，然后将其与目的地的距离进行比较。例如，对于节点B，0+10小于于无限大，因此节点B的新距离是10，而新的前置是A，同样适用于节点C。

节点A从未解决节点集合中移出，然后放入解决节点集合。

节点B和C被放入未解决节点集合，因为他们是A的相邻节点，可以从A到达，但是需要评估。

现在未解决节点集合中有2个节点，我们选择有最小距离的节点（节点B），然后进行迭代，直到我们解决了图中所有节点。

An image

下表概括了所有的迭代步骤

迭代	未解决集合	已解决集合	评估节点	B	C	D	E	F
1	A	–	A	A-10	A-15	X-∞	X-∞	X-∞
2	B, C	A	B	A-10	A-15	B-22	X-∞	B-25
3	C, F, D	A, B	C	A-10	A-15	B-22	C-25	B-25
4	D, E, F	A, B, C	D	A-10	A-15	B-22	D-24	D-23
5	E, F	A, B, C, D	F	A-10	A-15	B-22	D-24	D-23
6	E	A, B, C, D, F	E	A-10	A-15	B-22	D-24	D-23
Final	–	ALL	NONE	A-10	A-15	B-22	D-24	D-23

3. Java实现

public class Graph {

    private Set<Node> nodes = new HashSet<>();

    public void addNode(Node nodeA) {
        nodes.add(nodeA);
    }

    // getters and setters
}

1
2
3
4
5
6
7
8
9
10

我们使用节点名称、记录最短路径节点的链表、到起点的距离以及相邻节点这几个属性来描述一个节点。 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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

adjacentNodes属性用于把相邻节点的边缘距离关联起来，这是邻接列表的简化实现，它比邻接矩阵更适合Dijkstra算法。

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

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

现在让我们实现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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

现在所有必须的代码都有了，让我们把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);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

在计算完毕后，图中所有节点的最短路径和距离属性都会被设置好了。我们可以对其进行迭代，以验证结果与前一节中表格完全匹配。

4. 总结

在本文中，我们已经研究了Dijkstra算法如何解决SPP，以及如何在Java中实现它。

您可以在GITHUB找到本文的代码实现.

#

# 1. 概览

# 2. Dijkstra算法解决最短路径

# 2.1. 初始阶段

# 2.2. 评估

# 3. Java实现

# 4. 总结

1. 概览

2. Dijkstra算法解决最短路径

2.1. 初始阶段

2.2. 评估

3. Java实现

4. 总结