用java语言,使用贪心算法解决单源最短路径问题。
时间: 2024-02-03 13:14:16 浏览: 77
单源最短路径问题可以使用贪心算法解决,其中最经典的算法是Dijkstra算法。下面是使用Java语言实现Dijkstra算法的代码:
```java
import java.util.*;
public class Dijkstra {
private static final int INF = Integer.MAX_VALUE; // 无穷大
public static void main(String[] args) {
int[][] graph = { { 0, 10, 3, INF, INF }, { INF, 0, 1, 2, INF }, { INF, 4, 0, 8, 2 }, { INF, INF, INF, 0, 7 },
{ INF, INF, INF, 9, 0 } }; // 图的邻接矩阵表示
int start = 0; // 起点
int[] dist = dijkstra(graph, start);
System.out.println("起点为" + start + "的最短路径为:");
for (int i = 0; i < dist.length; i++) {
System.out.print(dist[i] + " ");
}
}
/**
* Dijkstra算法求最短路径
*
* @param graph 图的邻接矩阵表示
* @param start 起点
* @return 返回起点到各个顶点的最短距离
*/
public static int[] dijkstra(int[][] graph, int start) {
int n = graph.length; // 顶点数
boolean[] visited = new boolean[n]; // 记录是否访问过
int[] dist = new int[n]; // 记录起点到各个顶点的最短距离
// 初始化
Arrays.fill(dist, INF);
dist[start] = 0;
// 循环n次,每次找到一个最短路径
for (int i = 0; i < n; i++) {
int u = -1; // 选出距离起点最近的未确定点
int minDist = INF;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
u = j;
minDist = dist[j];
}
}
visited[u] = true; // 标记该点已经确定了最短路径
// 用刚选出的点更新其他点的距离
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
}
}
```
上面的代码中,我们使用了邻接矩阵来表示图,其中`graph[i][j]`表示从顶点i到顶点j的边的权值,如果为INF则表示没有边连接。在算法中,我们使用了一个`visited`数组来记录某个顶点是否已经确定了最短路径,使用一个`dist`数组来记录起点到各个顶点的最短距离,其中`dist[i]`表示起点到顶点i的最短距离。在每次循环中,我们选出一个距离起点最近的未确定点,并用它更新其他点的距离。最后返回`dist`数组即可。
阅读全文