dijkstra算法java
时间: 2023-09-22 22:09:44 浏览: 23
Dijkstra算法是一种经典的单源最短路径算法,可以在带权重的图中找到从源节点到所有其他节点的最短路径。
下面是Dijkstra算法的Java实现:
```java
import java.util.*;
public class DijkstraAlgorithm {
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}};
int[] result = dijkstra(graph, 0);
System.out.println(Arrays.toString(result));
}
public static int[] dijkstra(int[][] graph, int source) {
int n = graph.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
for (int i = 0; i < n - 1; i++) {
int minDist = Integer.MAX_VALUE;
int minIndex = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
minIndex = j;
}
}
visited[minIndex] = true;
for (int k = 0; k < n; k++) {
if (graph[minIndex][k] != 0 && !visited[k] && dist[minIndex] + graph[minIndex][k] < dist[k]) {
dist[k] = dist[minIndex] + graph[minIndex][k];
}
}
}
return dist;
}
}
```
其中,graph是一个二维数组,表示带权重的图,dist记录源节点到各个节点的最短距离,visited记录节点是否已经被访问过。在算法中,我们首先将源节点的距离设置为0,其他节点的距离设置为无穷大,然后依次遍历所有节点,更新距离,直到所有节点都被访问过。
在实现中,我们使用了一个minIndex变量来记录当前距离最小的节点,以及一个visited数组来记录节点是否已经被访问过。我们首先将源节点的距离设置为0,然后在未访问的节点中选择距离最小的节点,并将其标记为已访问。然后遍历所有与该节点相连的节点,更新其距离。重复以上步骤,直到所有节点都被访问过。最后,返回dist数组,即为源节点到各个节点的最短距离。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)