java最短路径算法
时间: 2023-11-08 11:05:59 浏览: 84
Java中最短路径算法有多种实现方式,其中比较常用的是Dijkstra算法和Floyd算法。
Dijkstra算法是一种贪心算法,用于解决带权重的有向图或无向图的单源最短路径问题。该算法的时间复杂度为O(n^2),其中n为节点数。
Floyd算法是一种动态规划算法,用于解决带权重的有向图或无向图的多源最短路径问题。该算法的时间复杂度为O(n^3),其中n为节点数。
以下是Dijkstra算法的Java实现示例:
```java
import java.util.*;
public class DijkstraAlgorithm {
public static void main(String[] args) {
int[][] graph = {{0, 2, 4, 0, 0},
{2, 0, 1, 4, 2},
{4, 1, 0, 3, 0},
{0, 4, 3, 0, 1},
{0, 2, 0, 1, 0}};
int[] dist = dijkstra(graph, 0);
System.out.println(Arrays.toString(dist));
}
public static int[] dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i < n - 1; i++) {
int u = findMinDist(dist, visited);
visited[u] = true;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
}
public static int findMinDist(int[] dist, boolean[] visited) {
int minDist = Integer.MAX_VALUE;
int minIndex = -1;
for (int i = 0; i < dist.length; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
minIndex = i;
}
}
return minIndex;
}
}
```
阅读全文