单源最短路径贪心算法java
时间: 2023-07-04 11:26:05 浏览: 93
单源最短路径问题可以使用Dijkstra算法或者Bellman-Ford算法来解决。其中,Dijkstra算法是一种贪心算法,可以用于求解非负权重的最短路径问题,它的核心思想是找到当前未访问的最短路径节点,并将其加入到已访问节点集合中。
下面是基于Java语言实现的Dijkstra算法示例代码,假设有n个节点,源节点为s,邻接矩阵为graph,dist数组记录源节点s到各个节点的最短距离(初始时dist[s]=0,其他节点的dist值为无穷大):
```
public static void dijkstra(int[][] graph, int n, int s, int[] dist) {
boolean[] visited = new boolean[n]; // 标记节点是否已被访问
visited[s] = true;
for (int i = 0; i < n; i++) {
dist[i] = graph[s][i]; // 初始化源节点到各个节点的距离
}
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;
}
}
if (minIndex == -1) {
break; // 如果所有节点都已访问,则退出循环
}
visited[minIndex] = true;
// 更新当前节点的邻接节点到源节点的距离
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[minIndex][j] != Integer.MAX_VALUE) {
dist[j] = Math.min(dist[j], dist[minIndex] + graph[minIndex][j]);
}
}
}
}
```
在上述代码中,使用visited数组标记节点是否已被访问,使用dist数组记录源节点s到各个节点的最短距离。在每次迭代中,找到当前未访问节点中距离源节点最近的节点,并将其加入到已访问节点集合中。然后,更新当前节点的邻接节点到源节点的距离,若距离更短则更新dist数组中的值。最终,dist数组中记录的就是源节点到各个节点的最短距离。
阅读全文