java实现Dijkstra算法
时间: 2023-11-05 19:44:43 浏览: 26
以下是使用 Java 实现 Dijkstra 算法的简单示例:
```java
import java.util.*;
public class DijkstraAlgorithm {
private static final int MAX_VALUE = Integer.MAX_VALUE;
public static void dijkstra(int[][] graph, int start) {
int numVertices = graph.length;
int[] dist = new int[numVertices]; // 存储起始节点到其他节点的最短距离
boolean[] visited = new boolean[numVertices]; // 记录节点是否已访问
// 初始化距离数组
Arrays.fill(dist, MAX_VALUE);
dist[start] = 0;
for (int i = 0; i < numVertices - 1; i++) {
int minDist = findMinDist(dist, visited);
visited[minDist] = true;
for (int j = 0; j < numVertices; j++) {
if (!visited[j] && graph[minDist][j] != 0 && dist[minDist] != MAX_VALUE) {
int newDist = dist[minDist] + graph[minDist][j];
if (newDist < dist[j]) {
dist[j] = newDist;
}
}
}
}
// 打印最短路径
printShortestPaths(dist, start);
}
private static int findMinDist(int[] dist, boolean[] visited) {
int minDist = MAX_VALUE;
int minIndex = -1;
for (int i = 0; i < dist.length; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
minIndex = i;
}
}
return minIndex;
}
private static void printShortestPaths(int[] dist, int start) {
int numVertices = dist.length;
System.out.println("从节点 " + start + " 出发的最短路径:");
for (int i = 0; i < numVertices; i++) {
System.out.println("到节点 " + i + " 的最短距离为 " + dist[i]);
}
}
public static void main(String[] args) {
int[][] graph = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
}
}
```
这个示例中,我们定义了一个 `dijkstra` 方法来执行 Dijkstra 算法。它接受一个邻接矩阵表示的图和一个起始节点作为参数。算法通过迭代选择距离起始节点最近的未访问节点,并更新到其他节点的最短距离。最后,它会打印出从起始节点到每个节点的最短路径。
在 `main` 方法中,我们创建了一个图的邻接矩阵表示,并调用 `dijkstra` 方法来执行算法。你可以根据自己的需要修改邻接矩阵来测试不同的情况。