1. 概述
本文的重点是最短路径问题（SPP），这是图论中已知的基本理论问题之一，以及如何使用Dijkstra算法来解决它。
该算法的基本目标是确定起始节点与图形其余部分之间的最短路径。
2. Dijkstra的最短路径问题
给定一个正加权图和一个起始节点 （A），Dijkstra 确定从源到图中所有目的地的最短路径和距离：
Dijkstra算法的核心思想是不断消除起始节点和所有可能目的地之间的较长路径。
为了跟踪流程，我们需要有两组不同的节点，已结算和未定居。
定居节点是与源具有已知最小距离的节点。未解决节点集收集我们可以从源到达的节点，但我们不知道与起始节点的最小距离。
以下是使用 Dijkstra 解决 SPP 要遵循的步骤列表：
将到开始节点的距离设置为零。
将所有其他距离设置为无限值。
我们将startNode添加到未解决的节点集中。
当未解决的节点集不为空时，我们：
从未解决的节点集中选择一个评估节点，评估节点应该是与源距离最小的节点。
通过在每次评估中保持最低距离来计算到直接邻居的新距离。
将尚未结算的邻居添加到未结算的节点集中。
这些步骤可以聚合为两个阶段：初始化和评估。让我们看看这如何应用于我们的示例图：
2.1. 初始化
在我们开始探索图中的所有路径之前，我们首先需要初始化所有具有无限距离和未知前置节点的节点，除了源。
作为初始化过程的一部分，我们需要将值 0 分配给节点 A（我们知道从节点 A 到节点 A 的距离显然是 0）
因此，图形其余部分中的每个节点都将用前置节点和距离进行区分：
要完成初始化过程，我们需要将节点 A 添加到未解决的节点中，将其设置为在评估步骤中首先选择。请记住，已结算的节点集仍然是空的。
2.2. 评估
现在我们已经初始化了图，我们选择与未解决集距离最小的节点，然后我们评估所有不在已解决节点中的相邻节点：
这个想法是将边权重添加到评估节点距离，然后将其与目标的距离进行比较。例如，对于节点 B，0+10 小于无穷大，因此节点 B 的新距离为 10，新的前身是 A，这同样适用于节点 C。
然后，节点 A 从未解决的节点集移动到已解决的节点。
节点 B 和 C 被添加到未解决的节点中，因为它们可以访问，但需要对其进行评估。
现在我们在未解决的集合中有两个节点，我们选择距离最小的一个（节点 B），然后我们重复直到我们解决图中的所有节点：
下表汇总了在评估步骤中执行的迭代：
例如，符号 B-22 表示节点 B 是前身，与节点 A 的总距离为 22。
最后，我们可以计算出节点 A 的最短路径如下：
节点 B：A –> B（总距离 = 10）
节点 C：A –> C（总距离 = 15）
节点 D ： A –> B –> D（总距离 = 22）
节点 E ： A –> B –> D –> E（总距离 = 24）
节点 F ： A –> B –> D –> F（总距离 = 23）
3. Java实现
在这个简单的实现中，我们将一个图表示为一组节点：
public class Graph {
private Set
public void addNode(Node nodeA) {
nodes.add(nodeA);
}
// getters and setters
}
节点可以用名称、引用最短路径的LinkedList、与源的距离以及名为adjacentNodes 的邻接列表来描述：
public class Node {
private String name;
private List
private Integer distance = Integer.MAX_VALUE;
Map
public void addDestination(Node destination, int distance) {
adjacentNodes.put(destination, distance);
}
public Node(String name) {
this.name = name;
}
// getters and setters
}
相邻节点属性用于将直接邻居与边长度相关联。这是邻接列表的简化实现，比邻接矩阵更适合 Dijkstra 算法。
至于shortestPath属性，它是一个节点列表，描述了从起始节点计算的最短路径。
默认情况下，所有节点距离都使用Integer.MAX_VALUE进行初始化，以模拟初始化步骤中所述的无限距离。
现在，让我们实现 Dijkstra 算法：
public static Graph calculateShortestPathFromSource(Graph graph, Node source) {
source.setDistance(0);
Set
Set
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;
}
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
shortestPath.add(sourceNode);
evaluationNode.setShortestPath(shortestPath);
}
}
现在所有必要的部分都已就绪，让我们在本文主题的示例图上应用 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);
计算后，为图形中的每个节点设置最短路径和距离属性，我们可以遍历它们以验证结果是否与上一节中找到的结果完全匹配。
相关链接
发表评论