让我们想象您和您最好的朋友生活得很远，您已经有一段时间没见过他了，您最好的朋友正在他家组织一个聚会，您很高兴能成为其中的一部分。问题是在通勤到朋友家时，您开始意识到有多种路线可以到达目的地，并且每条可能的路线可能都有不同的距离，那么您应该选择哪种路径？在大多数情况下，我们可能会选择最短的路线，并且通信时间很小。在本文中，我们将了解Dijkstra的算法 - 在我们的示例中找到2个顶点之间最短路径的算法，这是您房屋和朋友房屋之间的最短路径。
在进行算法的实际细节之前，我们需要将自己熟悉一些相关的术语，例如图形 - 该术语由顶点集合（节点）组成，任何两个顶点之间的路径称为边缘。在我们的示例中，每个位置表示为节点，并且这两个位置可能存在许多可能的节点和边缘。
Dijkstra算法有许多变体，但是在本文中，我们对传统的算法感兴趣，该算法是找到图表中其他每个节点之间最短路径的算法。例如，该算法不仅找到节点A（您的房子）到节点B（您的朋友的房子）之间的最短路径，而且还从节点A到其他节点，例如C（加油站），D（杂货店）（杂货店）等。让我们转到有关如何在目标节点（节点B）之间找到原点节点（节点A）之间的最短路径的详细步骤：
步骤1：将所有节点标记为未访问的。创建一组未访问的节点，称为
unvistedSet步骤2：分配每个节点的暂定距离值，并将初始顶点的距离值设置为零，并将图中所有其他顶点的无穷大。
步骤3：对于当前节点，请找出所有未访问的邻居，并通过当前节点计算未访问的邻居的暂定距离值，将新计算的新计算的暂定距离与当前分配的值进行比较，然后分配较小的距离。例如，如果电流节点A的距离为5，并且与邻居B连接的边缘的长度为2，则通过A的B距离为7。
步骤4：当我们完成探索当前节点的所有未访问的邻居时，我们将标记当前节点并将其从未
visitedunvisitedSet中删除时，访问的节点将永远不会再次访问。步骤5：然后选择具有最小暂定距离的未访问节点，并将其设置为当前节点，然后返回步骤3。
步骤6：如果目标节点已被标记为访问量，或者在
unvisitedSet的节点之间的最小暂定距离是无穷大的（这意味着初始节点和剩余的未访问节点之间没有连接），则停止，算法已经完成。
现在，我们准备将其编码为编码，首先，我们需要定义节点以及将保持节点和边缘的图数据结构，并且有不同的方法可以标记图形，但是在我们的情况下，我们将使用相邻的列表来呈现节点及其与图中其他节点的连接。
public class Node { public Node ( String label ) { this . label = label ; } private final String label ; private final Map < Node , Integer > adjacentNodes = new HashMap < >() ; private int distance ; private Node prev ; // getters and setters}
然后，我们定义一个将包含一组节点的图形：
public record Graph ( Set < Node > nodes ) { public Graph () { this ( new HashSet < >()) ; } public void addNode ( Node node ) { this . nodes . add ( node ) ; } public void addNode ( List < Node > node ) { this . nodes . addAll ( node ) ; }}
我们现在具有节点和图数据结构，这足以让我们开始实现Dijkstra的算法， calculateShortestPath方法将获取图形和源节点，然后计算出图表中的源节点之间的最短路径之间的最短路径：
public void calculateShortestPath ( Graph graph , Node source ) { Set < Node > unsettledNodes = new HashSet < >() ; Set < Node > settledNodes = new HashSet < >() ; for ( final Node node : graph . nodes ()) { node . setDistance ( Integer . MAX_VALUE ) ; } source . setDistance ( 0 ) ; unsettledNodes . add ( source ) ; while ( ! unsettledNodes . isEmpty ()) { Node node = getNearestNode ( unsettledNodes ) ; unsettledNodes . remove ( node ) ; settledNodes . add ( node ) ; findMinNeighborDistance ( unsettledNodes , settledNodes , node ) ; }}private void findMinNeighborDistance ( Set < Node > unsettledNodes , Set < Node > settledNodes , Node node ){ if ( node == null ) return; Map < Node , Integer > adjacentNodes = node . getAdjacentNodes () ; for ( final Map . Entry < Node , Integer > entry : adjacentNodes . entrySet ()) { Node neighbor = entry . getKey () ; int distance = entry . getValue () ; int sourceDistance = node . getDistance () ; if ( ! settledNodes . contains ( neighbor )) { if ( sourceDistance + distance < neighbor . getDistance ()) { neighbor . setDistance ( sourceDistance + distance ) ; neighbor . setPrev ( node ) ; unsettledNodes . add ( neighbor ) ; } } }}
让我们分解此代码中发生的事情：
我们最初将与图中每个节点的距离设置为无穷大。
从源节点到自身的距离为0，因此我们为其设置了0距离。
我们有2组节点，
unsettleNodes包含邻居没有访问的节点，一旦访问了一个节点的所有邻居，节点将从unsettledNodes移动到settledNodes。虽然
unsettledNodes并非空，但在循环内，我们采用的节点与当前节点的距离最近，在第一次尝试中，节点将是我们的源节点。请注意，在这种情况下，我们还可以为unsettledNodes使用优先级队列。在
findMinNeighborDistance中，我们基本上检查了每个邻居节点的当前节点，并在必要时更新距离值。在我们的情况下，我们首先检查邻居节点尚未解决，然后距源的距离加上与邻居的当前节点之间的距离小于当前邻居的距离，如果有的话，我们将邻居距离的值重新分配给邻居的值，并将邻居添加到未设置的nodes节点的集合中。
最后，我们创建一个测试类，该类将检查我们刚刚创建的代码，并使用一些初始设置填充测试：
public class DijkstraShortestPathTest { static final Dijkstra dijkstra = new Dijkstra () ; static Graph graph ; static List < Node > nodes = new ArrayList < >() ; @ BeforeAll static void setup () { graph = new Graph () ; nodes . add ( new Node ( " A " )) ; nodes . add ( new Node ( " B " )) ; nodes . add ( new Node ( " C " )) ; nodes . add ( new Node ( " D " )) ; nodes . add ( new Node ( " E " )) ; nodes . add ( new Node ( " F " )) ; nodes . add ( new Node ( " G " )) ; nodes . get ( 0 ). addAdjacentNode ( nodes . get ( 1 ), 10 ) ; nodes . get ( 0 ). addAdjacentNode ( nodes . get ( 2 ), 15 ) ; nodes . get ( 1 ). addAdjacentNode ( nodes . get ( 3 ), 12 ) ; nodes . get ( 1 ). addAdjacentNode ( nodes . get ( 5 ), 15 ) ; nodes . get ( 2 ). addAdjacentNode ( nodes . get ( 4 ), 10 ) ; nodes . get ( 3 ). addAdjacentNode ( nodes . get ( 4 ), 2 ) ; nodes . get ( 3 ). addAdjacentNode ( nodes . get ( 5 ), 1 ) ; nodes . get ( 5 ). addAdjacentNode ( nodes . get ( 4 ), 5 ) ; nodes . get ( 5 ). addAdjacentNode ( nodes . get ( 6 ), 3 ) ; graph . addNode ( nodes ) ; }}
这是图表上的外观：
到目前为止，我们的测试应通过：
@ Testvoid testGetShortestPath () { Node nodeA = nodes . get ( 0 ) ; Node nodeE = nodes . get ( 4 ) ; Node nodeF = nodes . get ( 5 ) ; Node nodeG = nodes . get ( 6 ) ; dijkstra . calculateShortestPath ( graph , nodeA ) ; assertEquals ( 24 , dijkstra . getTotalDistance ( nodeE )) ; assertEquals ( 23 , dijkstra . getTotalDistance ( nodeF )) ; assertEquals ( 26 , dijkstra . getTotalDistance ( nodeG )) ;}
代码示例可在此处提供。