在 Java 中實現 Dijkstra 演算法
Sheeraz Gul
2023年1月30日
2022年4月26日
當找到兩個圖節點之間的最短路徑時，我們可以實現 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 的圖的最短路徑。
Author: 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