Dijkstra算法的Java 代码
时间: 2024-03-21 20:36:49 浏览: 18
Dijkstra算法是一种用于解决单源最短路径问题的经典算法。下面是一个简单的Java代码示例:
```java
import java.util.*;
public class DijkstraAlgorithm {
private static final int INF = Integer.MAX_VALUE;
public static void dijkstra(int[][] graph, int start) {
int n = graph.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, INF);
dist[start] = 0;
for (int i = 0; i < n - 1; i++) {
int minDist = INF;
int minIndex = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
minIndex = j;
}
}
if (minIndex == -1) {
break;
}
visited[minIndex] = true;
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[minIndex][j] != INF && dist[minIndex] + graph[minIndex][j] < dist[j]) {
dist[j] = dist[minIndex] + graph[minIndex][j];
}
}
}
// 打印最短路径
System.out.println("节点\t最短距离");
for (int i = 0; i < n; i++) {
System.out.println(i + "\t" + dist[i]);
}
}
public static void main(String[] args) {
int[][] graph = {
{0, 4, INF, INF, INF, INF, INF, 8, INF},
{4, 0, 8, INF, INF, INF, INF, 11, INF},
{INF, 8, 0, 7, INF, 4, INF, INF, 2},
{INF, INF, 7, 0, 9, 14, INF, INF, INF},
{INF, INF, INF, 9, 0, 10, INF, INF, INF},
{INF, INF, 4, 14, 10, 0, 2, INF, INF},
{INF, INF, INF, INF, INF, 2, 0, 1, 6},
{8, 11, INF, INF, INF, INF, 1, 0, 7},
{INF, INF, 2, INF, INF, INF, 6, 7, 0}
};
dijkstra(graph, 0);
}
}
```