HOWTO · Java
在 Java 中實現 Dijkstra 演算法
本教程描述並演示了 Java 中的 Dijkstra 演算法。
當找到兩個圖節點之間的最短路徑時，我們可以實現 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 的圖的最短路徑。
