在 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 的图的最短路径。
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布，任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站。本站所有源码与软件均为原作者提供，仅供学习和研究使用。如您对本站的相关版权有任何异议，或者认为侵犯了您的合法权益，请及时通知我们处理。
