java实现Dijkstra算法,并用unit测试代码
时间: 2023-11-12 12:58:34 浏览: 111
可以回答这个问题。下面是一个Java实现Dijkstra算法的代码示例:
```java
import java.util.*;
public class DijkstraAlgorithm {
public static int[] dijkstra(int[][] graph, int source) {
int n = graph.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
for (int i = 0; i < n - 1; i++) {
int u = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
visited[u] = true;
for (int v = 0; v < n; v++) {
if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
}
public static void main(String[] args) {
int[][] graph = {
{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}
};
int[] dist = dijkstra(graph, 0);
System.out.println(Arrays.toString(dist));
// Output: [0, 4, 12, 19, 21, 11, 9, 8, 14]
}
}
```
你可以使用JUnit编写单元测试代码。
阅读全文