java实现dijkstra算法求最短路径
时间: 2023-08-16 07:05:52 浏览: 50
Dijkstra算法是一种用于解决带有非负边权值的单源最短路径问题的算法。下面是Java实现Dijkstra算法求最短路径的代码:
```java
import java.util.*;
public class DijkstraAlgorithm {
private static final int NO_PARENT = -1;
private static void dijkstra(int[][] adjacencyMatrix, int startVertex) {
int nVertices = adjacencyMatrix[0].length;
int[] shortestDistances = new int[nVertices];
boolean[] visited = new boolean[nVertices];
for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
shortestDistances[vertexIndex] = Integer.MAX_VALUE;
visited[vertexIndex] = false;
}
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 vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
if (!visited[vertexIndex] && shortestDistances[vertexIndex] < shortestDistance) {
nearestVertex = vertexIndex;
shortestDistance = shortestDistances[vertexIndex];
}
}
visited[nearestVertex] = true;
for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
int edgeDistance = adjacencyMatrix[nearestVertex][vertexIndex];
if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[vertexIndex])) {
parents[vertexIndex] = nearestVertex;
shortestDistances[vertexIndex] = 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\tPath");
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 = new int[][]{
{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 4
0 -> 2 12 2
0 -> 3 19 2 3
0 -> 4 21 2 3 4
0 -> 5 11 5
0 -> 6 9 6
0 -> 7 8 1 7
0 -> 8 14 2 8
```
以上代码中,`adjacencyMatrix`是一个邻接矩阵,表示图的边权值。在`main`函数中,我们调用`dijkstra`函数,并将起点编号作为参数传入。函数中,首先初始化了一些数组和变量,然后开始执行Dijkstra算法的主体部分。最后,调用`printSolution`函数打印出结果。