图的最短路径java_地铁线路最短路径(JAVA实现)
时间: 2023-12-11 13:03:56 浏览: 30
地铁线路最短路径可以使用Dijkstra算法来解决。以下是Java实现的示例代码:
```java
import java.util.*;
public class Subway {
private static final int INF = Integer.MAX_VALUE; // 代表正无穷
private int[][] graph; // 地铁图的邻接矩阵表示
private int[] dist; // 起点到各个站点的最短距离
private boolean[] visited; // 标记站点是否已经访问过
private int start; // 起点站
public Subway(int[][] graph, int start) {
this.graph = graph;
this.start = start;
this.dist = new int[graph.length];
this.visited = new boolean[graph.length];
}
public void shortestPath() {
Arrays.fill(dist, INF);
dist[start] = 0;
for (int i = 0; i < graph.length; i++) {
// 找到未访问过的距离起点最近的站点
int u = -1;
int minDist = INF;
for (int j = 0; j < graph.length; j++) {
if (!visited[j] && dist[j] < minDist) {
u = j;
minDist = dist[j];
}
}
if (u == -1) break; // 如果找不到未访问过的站点,则退出循环
visited[u] = true;
// 更新与u相邻的站点到起点的最短距离
for (int v = 0; v < graph.length; v++) {
if (!visited[v] && graph[u][v] != INF) {
dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);
}
}
}
}
public int getShortestDist(int end) {
return dist[end];
}
public static void main(String[] args) {
int[][] graph = new int[][]{
{0, 3, 1, 2, INF},
{3, 0, INF, INF, 4},
{1, INF, 0, INF, INF},
{2, INF, INF, 0, 5},
{INF, 4, INF, 5, 0}
};
Subway subway = new Subway(graph, 0);
subway.shortestPath();
System.out.println(subway.getShortestDist(4)); // 输出起点到终点的最短距离
}
}
```
在这个示例代码中,我们用邻接矩阵表示地铁图,用Dijkstra算法求出起点到各个站点的最短距离。可以通过调用`getShortestDist`方法来获取起点到某个站点的最短距离。