狄杰特斯拉算法java
时间: 2023-10-26 11:11:36 浏览: 67
狄杰斯特拉算法(Dijkstra's Algorithm)是一种用于求解单源最短路径问题的算法。在Java中,你可以使用以下代码实现狄杰斯特拉算法:
```java
import java.util.*;
public class DijkstraAlgorithm {
private static final int MAX_VALUE = Integer.MAX_VALUE;
public void dijkstra(int[][] graph, int source) {
int numNodes = graph.length;
boolean[] visited = new boolean[numNodes];
int[] distance = new int[numNodes];
Arrays.fill(distance, MAX_VALUE);
distance[source] = 0;
for (int i = 0; i < numNodes - 1; i++) {
int minDistNode = findMinDistanceNode(distance, visited);
visited[minDistNode] = true;
for (int j = 0; j < numNodes; j++) {
if (!visited[j] && graph[minDistNode][j] != 0 && distance[minDistNode] != MAX_VALUE
&& distance[minDistNode] + graph[minDistNode][j] < distance[j]) {
distance[j] = distance[minDistNode] + graph[minDistNode][j];
}
}
}
printSolution(distance);
}
private int findMinDistanceNode(int[] distance, boolean[] visited) {
int minDistance = MAX_VALUE;
int minDistanceNode = -1;
for (int i = 0; i < distance.length; i++) {
if (!visited[i] && distance[i] < minDistance) {
minDistance = distance[i];
minDistanceNode = i;
}
}
return minDistanceNode;
}
private void printSolution(int[] distance) {
System.out.println("Vertex \t Distance from Source");
for (int i = 0; i < distance.length; i++) {
System.out.println(i + " \t\t " + distance[i]);
}
}
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 }
};
DijkstraAlgorithm algorithm = new DijkstraAlgorithm();
algorithm.dijkstra(graph, 0);
}
}
```
这是一个简单的使用邻接矩阵表示图的示例。你可以根据自己的需求修改图的结构和源节点来运行算法,然后输出最短路径信息。希望对你有帮助!
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)