Dijkstra 算法的 Java 实现329

概述

Dijkstra 算法是一种解决加权有向图中单源最短路径问题的贪心算法。对于图中给定的源节点，它计算从源节点到其他所有节点的最短路径。

算法步骤

Dijkstra 算法的步骤如下：1. 初始化：将源节点的距离设为 0，其他所有节点的距离设为无穷大。
2. 选择：从剩余节点中选择距离最小的节点。
3. 松弛：对于该节点的所有相邻节点，更新它们的距离，如果通过该节点找到更短的路径。
4. 重复：重复步骤 2 和 3，直到所有节点的距离都确定。

Java 实现```java
import .*;
public class Dijkstra {
private static class Node implements Comparable {
int vertex;
int distance;
public Node(int vertex, int distance) {
= vertex;
= distance;
}
@Override
public int compareTo(Node other) {
return (, );
}
}
public static Map calculateDistances(Graph graph, int source) {
Map distances = new HashMap();
PriorityQueue pq = new PriorityQueue();
// Initialize distances and add source to priority queue
for (int vertex : ()) {
(vertex, Integer.MAX_VALUE);
}
(source, 0);
(new Node(source, 0));
// While there are nodes in the priority queue
while (!()) {
// Get the node with the smallest distance
Node current = ();
// Visit all neighbors of the current node
for (Edge edge : ()) {
int neighbor = ();
int newDistance = + ();
// If new distance is shorter, update distance and add to priority queue
if (newDistance < (neighbor)) {
(neighbor, newDistance);
(new Node(neighbor, newDistance));
}
}
}
// Return the distances
return distances;
}
// Sample usage
public static void main(String[] args) {
Graph graph = new Graph();
(0, 1, 4);
(0, 2, 2);
(1, 2, 3);
(1, 3, 2);
(2, 3, 3);
Map distances = calculateDistances(graph, 0);
("Distances from source node 0: " + distances);
}
}
```