dijkstra java
时间: 2023-09-03 14:12:54 浏览: 36
Dijkstra算法是一种用于寻找带权图中单源最短路径的贪心算法。以下是Java代码实现:
```java
import java.util.*;
public class DijkstraAlgorithm {
private static final int NO_PARENT = -1;
// Dijkstra算法实现函数
public static void dijkstra(int[][] adjacencyMatrix, int startVertex) {
int nVertices = adjacencyMatrix[0].length;
int[] shortestDistances = new int[nVertices];
boolean[] visited = new boolean[nVertices];
// 初始化 shortestDistances数组
for (int i = 0; i < nVertices; i++) {
shortestDistances[i] = Integer.MAX_VALUE;
visited[i] = 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 j = 0; j < nVertices; j++) {
if (!visited[j] && shortestDistances[j] < shortestDistance) {
nearestVertex = j;
shortestDistance = shortestDistances[j];
}
}
visited[nearestVertex] = true;
for (int k = 0; k < nVertices; k++) {
int edgeDistance = adjacencyMatrix[nearestVertex][k];
if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[k])) {
parents[k] = nearestVertex;
shortestDistances[k] = shortestDistance + edgeDistance;
}
}
}
// 打印结果
printSolution(startVertex, shortestDistances, parents);
}
// 打印结果函数
public static void printSolution(int startVertex, int[] distances, int[] parents) {
int nVertices = distances.length;
System.out.print("顶点\t 最短距离\t 路径");
for (int i = 0; i < nVertices; i++) {
if (i != startVertex) {
System.out.print("\n" + startVertex + " -> " + i + " \t " + distances[i] + "\t\t");
printPath(i, parents);
}
}
}
// 递归打印路径函数
public 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, 6, 0, 0, 0, 0, 0, 9, 0 },
{ 6, 0, 9, 0, 0, 0, 0, 11, 0 },
{ 0, 9, 0, 5, 0, 6, 0, 0, 2 },
{ 0, 0, 5, 0, 9, 16, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 6, 0, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 16, 0, 2, 0, 1, 6 },
{ 9, 11, 0, 0, 0, 0, 1, 0, 5 },
{ 0, 0, 2, 0, 0, 0, 6, 5, 0 }
};
dijkstra(adjacencyMatrix, 0);
}
}
```
在此示例中,我们使用邻接矩阵来表示图。可以看到,我们首先将源顶点的距离设置为0,并将其标记为已访问。 然后,我们遍历所有未访问的顶点,找到距离源顶点最近的顶点,并计算从源顶点到该顶点的距离。如果新计算的距离比当前记录的最短距离更短,则更新最短距离并设置该顶点的父节点为最近的顶点。 最后,我们打印出每个顶点的最短路径和距离。