飞机航班线路带权有向图java算法代码
时间: 2023-09-13 09:10:51 浏览: 40
以下是使用邻接矩阵表示带权有向图的Java代码:
```java
public class FlightGraph {
private int numVertices;
private int[][] adjacencyMatrix;
public FlightGraph(int numVertices) {
this.numVertices = numVertices;
adjacencyMatrix = new int[numVertices][numVertices];
}
public void addEdge(int source, int destination, int weight) {
adjacencyMatrix[source][destination] = weight;
}
public List<Integer> shortestPath(int source, int destination) {
int[] distance = new int[numVertices];
boolean[] visited = new boolean[numVertices];
int[] predecessor = new int[numVertices];
for (int i = 0; i < numVertices; i++) {
distance[i] = Integer.MAX_VALUE;
}
distance[source] = 0;
for (int i = 0; i < numVertices - 1; i++) {
int minDistance = Integer.MAX_VALUE;
int minVertex = -1;
for (int j = 0; j < numVertices; j++) {
if (!visited[j] && distance[j] < minDistance) {
minDistance = distance[j];
minVertex = j;
}
}
visited[minVertex] = true;
for (int k = 0; k < numVertices; k++) {
int edgeWeight = adjacencyMatrix[minVertex][k];
if (edgeWeight > 0 && !visited[k] && distance[minVertex] + edgeWeight < distance[k]) {
distance[k] = distance[minVertex] + edgeWeight;
predecessor[k] = minVertex;
}
}
}
List<Integer> path = new ArrayList<>();
int currentVertex = destination;
while (currentVertex != source) {
path.add(currentVertex);
currentVertex = predecessor[currentVertex];
}
path.add(source);
Collections.reverse(path);
return path;
}
}
```
使用示例:
```java
FlightGraph flightGraph = new FlightGraph(4);
flightGraph.addEdge(0, 1, 10);
flightGraph.addEdge(0, 2, 15);
flightGraph.addEdge(1, 2, 5);
flightGraph.addEdge(2, 3, 20);
flightGraph.addEdge(1, 3, 25);
List<Integer> shortestPath = flightGraph.shortestPath(0, 3);
System.out.println("Shortest path from 0 to 3: " + shortestPath);
```
输出结果:
```
Shortest path from 0 to 3: [0, 1, 2, 3]
```