dijkstra算法求最短路径java
时间: 2023-05-01 12:06:34 浏览: 100
Dijkstra算法是一种求解图中最短路径的经典算法,可以用Java语言来实现。具体实现方法如下:
1. 定义一个长度为n的布尔型数组visited,表示每个节点是否已被访问过,初始化所有值为false;
2. 定义一个长度为n的整型数组distance,表示起点到每个节点的距离,初始化起点的值为0,其余节点的值为无限大(设为Integer.MAX_VALUE);
3. 定义一个长度为n的整形数组predecessor,表示每个节点的前驱节点,初始化所有值为null;
4. 从起点开始,将distance值最小的节点标记为已访问过,然后更新与该节点相邻的节点的distance值和predecessor值;
5. 重复上述步骤,直到所有节点都被标记为已访问或者没有与起点相连的节点可访问;
6. 最后得到起点到终点的最短路径。
代码示例:
```
public class Dijkstra {
public static void dijkstra(int[][] graph, int start) {
int n = graph.length;
boolean[] visited = new boolean[n];
int[] distance = new int[n];
Integer[] predecessor = new Integer[n];
Arrays.fill(visited, false);
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0;
for (int i = 0; i < n - 1; i++) {
int minDistance = Integer.MAX_VALUE;
int minNode = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && distance[j] < minDistance) {
minDistance = distance[j];
minNode = j;
}
}
if (minNode == -1) {
break;
}
visited[minNode] = true;
for (int j = 0; j < n; j++) {
if (graph[minNode][j] > 0 && distance[minNode] + graph[minNode][j] < distance[j]) {
distance[j] = distance[minNode] + graph[minNode][j];
predecessor[j] = minNode;
}
}
}
// print result
for (int i = 0; i < n; i++) {
if (i == start) {
continue;
}
if (distance[i] == Integer.MAX_VALUE) {
System.out.println(String.format("No path from %d to %d", start, i));
} else {
List<Integer> path = new ArrayList<>();
int node = i;
while (node != start) {
path.add(node);
node = predecessor[node];
}
path.add(start);
Collections.reverse(path);
System.out.println(String.format("Shortest path from %d to %d: %s (distance=%d)", start, i, path, distance[i]));
}
}
}
public static void main(String[] args) {
int[][] graph = {{0, 1, 4, 0, 0}, {1, 0, 2, 5, 0}, {4, 2, 0, 1, 3}, {0, 5, 1, 0, 2}, {0, 0, 3, 2, 0}};
dijkstra(graph, 0);
}
}
```
此代码演示了如何用Java语言实现Dijkstra算法求出从节点0到其余节点的最短路径。算法基本思路是:先初始化distance数组,然后从distance值最小的未访问节点开始遍历,更新与该节点相邻的节点的distance值和predecessor值,直到所有节点都被访问或者没有可访问的节点为止。最后,可以根据predecessor数组得到从起点到终点的最短路径。