迪杰斯特拉求单源最短路径Java
时间: 2023-10-17 07:06:53 浏览: 101
迪杰斯特拉算法用于求解有权图的单源最短路径问题,下面是Java代码实现:
```java
import java.util.Arrays;
public class Dijkstra {
private static final int INF = Integer.MAX_VALUE; // 无穷大
public void dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int[n]; // 存储最短距离
boolean[] visited = new boolean[n]; // 标记节点是否已访问
Arrays.fill(dist, INF); // 初始化为无穷大
dist[src] = 0; // 设置源节点到自己的距离为0
for (int i = 0; i < n - 1; i++) {
// 选择距离最短的节点
int u = minDistance(dist, visited);
visited[u] = true;
// 更新相邻节点的最短距离
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// 输出最短距离
for (int i = 0; i < n; i++) {
System.out.println("源节点到 " + i + " 的最短距离为:" + dist[i]);
}
}
private int minDistance(int[] dist, boolean[] visited) {
int min = INF, minIndex = -1;
for (int i = 0; i < dist.length; i++) {
if (!visited[i] && dist[i] <= min) {
min = dist[i];
minIndex = i;
}
}
return minIndex;
}
public static void main(String[] args) {
int[][] graph = {{0, 3, 2, 0, 0},
{3, 0, 0, 5, 0},
{2, 0, 0, 1, 6},
{0, 5, 1, 0, 4},
{0, 0, 6, 4, 0}};
Dijkstra obj = new Dijkstra();
obj.dijkstra(graph, 0);
}
}
```
阅读全文
相关推荐


















