# Java数据结构与算法：最短路径算法

### 最短路径算法简介

1. Dijkstra算法：用于计算图中单个源点到其他所有顶点的最短路径。
2. Bellman-Ford算法：用于计算图中单个源点到其他所有顶点的最短路径，但可以处理带有负权边的图。
3. Floyd-Warshall算法：用于计算图中所有顶点之间的最短路径，适用于有向图或无向图。

### Dijkstra算法的实现

import java.util.*;
class ShortestPath {
private int vertices;
private int[][] graph;
public ShortestPath(int vertices) {
this.vertices = vertices;
this.graph = new int[vertices][vertices];
}
public void addEdge(int source, int destination, int weight) {
graph[source][destination] = weight;
graph[destination][source] = weight;
}
public int[] dijkstra(int source) {
int[] distance = new int[vertices];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[source] = 0;
Set<Integer> visited = new HashSet<>();
PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));
minHeap.offer(new Node(source, 0));
while (!minHeap.isEmpty()) {
Node currentNode = minHeap.poll();
int currentVertex = currentNode.vertex;
if (visited.contains(currentVertex)) {
continue;
}
for (int neighbor = 0; neighbor < vertices; neighbor++) {
int edgeWeight = graph[currentVertex][neighbor];
if (edgeWeight > 0 && !visited.contains(neighbor)) {
int newDistance = distance[currentVertex] + edgeWeight;
if (newDistance < distance[neighbor]) {
distance[neighbor] = newDistance;
minHeap.offer(new Node(neighbor, newDistance));
}
}
}
}
return distance;
}
private static class Node {
int vertex;
int distance;
public Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
}
}
public class DijkstraExample {
public static void main(String[] args) {
ShortestPath graph = new ShortestPath(6);
int[] shortestDistances = graph.dijkstra(0);
System.out.println("Shortest Distances from Source (Vertex 0): " + Arrays.toString(shortestDistances));
}
}

### 总结

|
3天前
|

AI入门必读：Java实现常见AI算法及实际应用，有两下子！

53 2
|
2天前
|

LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题：矩阵中省份数量经典题目+三角形最大周长java多种解法详解
13 6
|
2天前
|

LeetCode经典算法题：打家劫舍java详解
LeetCode经典算法题：打家劫舍java详解
12 2
|
2天前
|

LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
11 1
|
2天前
|

LeetCode经典算法题：预测赢家+香槟塔java解法
LeetCode经典算法题：预测赢家+香槟塔java解法
8 1
|
14天前
|

23 8
|
13天前
|

Java语言实现最短路径算法（Shortest Path）
Java语言实现最短路径算法（Shortest Path）
22 3
|
17天前
|

【数据结构】排序算法——Lesson2
【7月更文挑战第24天】
12 3
|
2天前
|

LeetCode经典算法题：二叉树遍历（递归遍历+迭代遍历+层序遍历）以及线索二叉树java详解
LeetCode经典算法题：二叉树遍历（递归遍历+迭代遍历+层序遍历）以及线索二叉树java详解
5 0
|
2天前
|

LeetCode初级算法题：环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题：环形链表+排列硬币+合并两个有序数组java解法
6 0