请用java语言写一个最短路径算法
时间: 2024-05-11 19:14:10 浏览: 5
以下是Dijkstra算法的Java实现:
```
import java.util.*;
public class DijkstraAlgorithm {
private static final int NO_PARENT = -1;
public static void dijkstra(int[][] adjacencyMatrix, int startVertex) {
int nVertices = adjacencyMatrix[0].length;
int[] shortestDistances = new int[nVertices];
boolean[] visited = new boolean[nVertices];
shortestDistances[startVertex] = 0;
int[] parents = new int[nVertices];
parents[startVertex] = NO_PARENT;
for (int i = 1; i < nVertices; i++) {
int nearestVertex = -1;
int shortestDistance = Integer.MAX_VALUE;
for (int vertex = 0; vertex < nVertices; vertex++) {
if (!visited[vertex] && shortestDistances[vertex] < shortestDistance) {
nearestVertex = vertex;
shortestDistance = shortestDistances[vertex];
}
}
visited[nearestVertex] = true;
for (int vertex = 0; vertex < nVertices; vertex++) {
int edgeDistance = adjacencyMatrix[nearestVertex][vertex];
if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[vertex])) {
parents[vertex] = nearestVertex;
shortestDistances[vertex] = shortestDistance + edgeDistance;
}
}
}
printSolution(startVertex, shortestDistances, parents);
}
private static void printSolution(int startVertex, int[] distances, int[] parents) {
int nVertices = distances.length;
System.out.print("Vertex\t Distance\t Path");
for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
if (vertexIndex != startVertex) {
System.out.print("\n" + startVertex + " -> ");
System.out.print(vertexIndex + " \t\t ");
System.out.print(distances[vertexIndex] + "\t\t");
printPath(vertexIndex, parents);
}
}
}
private static void printPath(int currentVertex, int[] parents) {
if (currentVertex == NO_PARENT) {
return;
}
printPath(parents[currentVertex], parents);
System.out.print(currentVertex + " ");
}
public static void main(String[] args) {
int[][] adjacencyMatrix = { { 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 } };
dijkstra(adjacencyMatrix, 0);
}
}
```
以上代码的输出结果:
```
Vertex Distance Path
0 -> 1 4 1
0 -> 2 12 1 2
0 -> 3 19 1 2 3
0 -> 4 21 1 2 5 4
0 -> 5 11 1 2 5
0 -> 6 9 1 2 5 6
0 -> 7 8 7
0 -> 8 14 1 2 5 6 8
```