在 Java 中实现 Dijkstra 算法
Sheeraz Gul
2023年10月12日
当找到两个图节点之间的最短路径时，我们可以实现 Dijkstra 算法，这是一种广泛使用的算法。本教程描述了 Dijkstra 算法的过程，并演示了如何在 Java 中实现它。
Dijkstra 算法
Dijkstra 算法可以找到从源节点到加权图中所有节点的最短路径。最短路径也可以在图中的源顶点中找到。
通过 Dijkstra 算法找到最短路径将生成具有根源顶点的最短路径树 (SPT)。
在 Java 中实现 Dijkstra 算法时，我们维护两个列表或集合。第一个包含最短路径树中的所有顶点，第二个包含评估阶段的顶点以包含在 SPT 中。
我们在每次迭代中从第二个列表中找到一个顶点，它将具有最短路径。下面是 Dijkstra 算法的分步过程：
-
首先，将图中的所有节点标记为未访问。
-
现在，用零初始化起始节点；所有其他无穷大的节点表示最大的数字。
-
使起始节点成为当前节点。
-
这个当前节点现在将用于分析其所有未访问的邻居节点，然后通过添加边的权重来计算距离，这将建立当前节点和邻居节点之间的连接。
-
比较最近计算的距离和分配给邻居节点的距离；这将被视为相邻节点的当前距离。
-
现在，考虑当前节点周围尚未访问的节点，并将当前节点标记为已访问。
-
重复这个过程，直到结束节点被标记为已访问，这意味着 Dijkstra 的算法已经完成了它的任务。如果结束节点还没有被标记为已访问，那么：
-
选择路径最短的未访问节点，它将成为新的当前节点。然后从步骤 4 开始重复该过程。
Dijkstra 算法的伪代码
Method DIJKSTRA(G, SV)
G-> graph;
SV->starting vertex;
begin
for every vertex VX in G //initialization; set the initial path to infinite and current node to 0 or null;
Distance[VX] <- infinite
Current[VX] <- NULL
If V != SV, add VX to Priority Queue // During the first run, this vertex is the source or starting node
Distance[SV] <- 0
while Priority Queue IS NOT EMPTY // where the neighbor ux has not been extracted yet from the priority queue
UX <- Extract MIN Neighbor from Priority Queue
for each unvisited adjacent_node VX of UX
Temporary_Distance <- Distance[UX] + Edge_Weight(UX, VX)
if Temporary_Distance < Distance[VX] // A distance with lesser weight (shorter path) from ux is found
Distance[VX] <- Temporary_Distance
Current[VX] <- UX // update the distance of UX
return Distance[], Current[]
end
在 Java 中使用优先级队列实现 Dijkstra 算法
下面是使用优先级队列的 Dijkstra 算法的 Java 实现：
package delftstack;
import java.util.*;
public class Dijkstra_Algorithm {
public static void main(String arg[]) {
int Vertex = 6;
int source_vertex = 0;
// representation of graph will be the adjacency list
List<List<Node> > Node_list = new ArrayList<List<Node> >();
// For every node in the graph Initialize adjacency list
for (int i = 0; i < Vertex; i++) {
List<Node> item = new ArrayList<Node>();
Node_list.add(item);
}
// The edges of the graph
Node_list.get(0).add(new Node(1, 5));
Node_list.get(0).add(new Node(4, 2));
Node_list.get(0).add(new Node(2, 3));
Node_list.get(1).add(new Node(5, 2));
Node_list.get(1).add(new Node(4, 3));
Node_list.get(2).add(new Node(3, 3));
Node_list.get(2).add(new Node(4, 2));
// Run the Dijkstra_Algorithm on the graph
Graph_priority_queue gpq = new Graph_priority_queue(Vertex);
gpq.Dijkstra_Algo(Node_list, source_vertex);
// Printing the shortest path from source node to all other the nodes
System.out.println("The shortest paths from source nodes to all other nodes:");
System.out.println("Source_Node\t\t"
+ "Other_Node#\t\t"
+ "Path_Distance");
for (int x = 0; x < gpq.distance.length; x++)
System.out.println(source_vertex + " \t\t\t " + x + " \t\t\t " + gpq.distance[x]);
}
}
class Graph_priority_queue {
int distance[];
Set<Integer> visited_Node;
PriorityQueue<Node> Priority_Queue;
int Vertex; // vertices
List<List<Node> > node_list;
// constructor
public Graph_priority_queue(int Vertex) {
this.Vertex = Vertex;
distance = new int[Vertex];
visited_Node = new HashSet<Integer>();
Priority_Queue = new PriorityQueue<Node>(Vertex, new Node());
}
// Dijkstra's Algorithm implementation
public void Dijkstra_Algo(List<List<Node> > node_list, int source_vertex) {
this.node_list = node_list;
for (int x = 0; x < Vertex; x++) {
distance[x] = Integer.MAX_VALUE;
}
// add the source vertex to the Priority Queue
Priority_Queue.add(new Node(source_vertex, 0));
// Distance of the source from source itself is 0
distance[source_vertex] = 0;
while (visited_Node.size() != Vertex) {
// ux is deleted from the Priority Queue which has minimum distance
int ux = Priority_Queue.remove().dj_node;
// add the ux node to finalized list which is visited
visited_Node.add(ux);
Adjacent_Nodes_Graph(ux);
}
}
// process all the neighbors of the just visited node
private void Adjacent_Nodes_Graph(int ux) {
int Edge_Distance = -1;
int New_Distance = -1;
// process all neighboring nodes of ux
for (int x = 0; x < node_list.get(ux).size(); x++) {
Node vx = node_list.get(ux).get(x);
// if current node is not in 'visited'
if (!visited_Node.contains(vx.dj_node)) {
Edge_Distance = vx.dj_cost;
New_Distance = distance[ux] + Edge_Distance;
// compare the distances
if (New_Distance < distance[vx.dj_node])
distance[vx.dj_node] = New_Distance;
// Add the current vertex to the PriorityQueue
Priority_Queue.add(new Node(vx.dj_node, distance[vx.dj_node]));
}
}
}
}
// The Class to handle nodes
class Node implements Comparator<Node> {
public int dj_node;
public int dj_cost;
public Node() {}
public Node(int dj_node, int dj_cost) {
this.dj_node = dj_node;
this.dj_cost = dj_cost;
}
@Override
public int compare(Node dj_node1, Node dj_node2) {
if (dj_node1.dj_cost < dj_node2.dj_cost)
return -1;
if (dj_node1.dj_cost > dj_node2.dj_cost)
return 1;
return 0;
}
}
上面的代码将使用 Java 中的 Dijkstra 算法给出给定图的最短路径。
输出：
The shortest paths from source nodes to all other nodes:
Source_Node Other_Node# Path_Distance
0 0 0
0 1 5
0 2 3
0 3 6
0 4 2
0 5 7
在 Java 中使用邻接矩阵实现 Dijkstra 算法
这是使用邻接矩阵的 Dijkstra 算法的 Java 实现：
package delftstack;
// Dijkstra's Algorithm using Adjacency matrix in Java
public class Dijkstra_Algorithm {
public static void dijkstra_algo(int[][] Input_Graph, int source_node) {
int Node_Count = Input_Graph.length;
boolean[] Vertex_Visited = new boolean[Node_Count];
int[] Node_Distance = new int[Node_Count];
for (int x = 0; x < Node_Count; x++) {
Vertex_Visited[x] = false;
Node_Distance[x] = Integer.MAX_VALUE;
}
// Distance of the source node to itself is zero
Node_Distance[source_node] = 0;
for (int x = 0; x < Node_Count; x++) {
// Updating the distance between the source vertex and neighboring vertex
int ux = findMinDistance(Node_Distance, Vertex_Visited);
Vertex_Visited[ux] = true;
// Updating all the neighboring vertices distances
for (int vx = 0; vx < Node_Count; vx++) {
if (!Vertex_Visited[vx] && Input_Graph[ux][vx] != 0
&& (Node_Distance[ux] + Input_Graph[ux][vx] < Node_Distance[vx])) {
Node_Distance[vx] = Node_Distance[ux] + Input_Graph[ux][vx];
}
}
}
for (int x = 0; x < Node_Distance.length; x++) {
System.out.println(String.format("Distance from the source node %s to the node %s is %s",
source_node, x, Node_Distance[x]));
}
}
// Finding the shortest distance
private static int findMinDistance(int[] Node_Distance, boolean[] Vertex_Visited) {
int Minimum_Distance = Integer.MAX_VALUE;
int Minimum_Distance_Vertex = -1;
for (int x = 0; x < Node_Distance.length; x++) {
if (!Vertex_Visited[x] && Node_Distance[x] < Minimum_Distance) {
Minimum_Distance = Node_Distance[x];
Minimum_Distance_Vertex = x;
}
}
return Minimum_Distance_Vertex;
}
public static void main(String[] args) {
int source_node = 0;
int Input_Graph[][] = new int[][] {{0, 0, 3, 2, 0, 0, 1}, {0, 0, 2, 0, 4, 1, 0},
{1, 0, 0, 3, 3, 0, 0}, {2, 0, 1, 0, 5, 0, 1}, {0, 0, 0, 4, 0, 2, 3}, {0, 3, 0, 1, 2, 0, 1},
{0, 0, 0, 3, 0, 0, 4}};
Dijkstra_Algorithm Demo = new Dijkstra_Algorithm();
Demo.dijkstra_algo(Input_Graph, source_node);
}
}
上面的代码将使用 Java 中的 Dijkstra 算法在邻接矩阵中输出给定图的最短路径。
输出：
Distance from the source node 0 to the node 0 is 0
Distance from the source node 0 to the node 1 is 11
Distance from the source node 0 to the node 2 is 3
Distance from the source node 0 to the node 3 is 2
Distance from the source node 0 to the node 4 is 6
Distance from the source node 0 to the node 5 is 8
Distance from the source node 0 to the node 6 is 1
我们可以使用 Dijkstra 算法的两种方法来计算使用 Java 的图的最短路径。
作者： Sheeraz Gul
Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.
LinkedIn Facebook