关于最短路径算法的Java实现，这里简述一下几种常用的算法及其基本原理，并给出一个Dijkstra算法的基本实现框架。
Dijkstra算法用于寻找图中一个顶点到其他所有顶点的最短路径。它维护了一个距离表，用来存储从源点到各个顶点的已知最短距离，并且每次都会选择当前未确定最短路径且已知距离最小的顶点进行拓展。
以下是Dijkstra算法在Java中的基础实现结构：
import java.util.*;
class Node implements Comparable<Node> {
int id;
int dist;
Node prev;
Node(int id, int dist) {
this.id = id;
this.dist = dist;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.dist, other.dist);
}
}
public class DijkstraAlgorithm {
public void dijkstra(int[][] graph, int src) {
int V = graph.length; // 图的顶点数量
int[] dist = new int[V]; // 存储从源点到各顶点的距离
boolean[] visited = new boolean[V]; // 记录已经访问过的顶点
PriorityQueue<Node> pq = new PriorityQueue<>(); // 使用优先队列（小根堆）存储待处理节点
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
pq.offer(new Node(src, 0));
while (!pq.isEmpty()) {
Node u = pq.poll();
visited[u.id] = true;
// 更新u的邻居节点的距离
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u.id][v] != 0 && dist[u.id] + graph[u.id][v] < dist[v]) {
dist[v] = dist[u.id] + graph[u.id][v];
pq.offer(new Node(v, dist[v]));
// 可以在此处记录路径，即设置prev指针
}
}
}
// 输出最短路径或者进一步处理dist数组以获取实际路径
}
}Bellman-Ford算法同样可以求解单源最短路径问题，但它允许图中存在负权边，只是要求不存在负权回路。该算法通过迭代松弛所有的边，至少进行V-1轮迭代来确保找到正确的最短路径。
import java.util.*;
public class BellmanFord {
public static void bellmanFord(int[][] graph, int src) {
int V = graph.length; // 图的顶点数
int E = graph[0].length; // 边的数量（假设每行都有E个元素，即每顶点都有E条出边）
// 初始化距离数组，所有顶点到src的距离初始化为无穷大，src到自身的距离为0
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// 进行V-1轮迭代，保证即使经过最长链长度为V-1的负权边也能被检测到
for (int i = 0; i < V - 1; i++) {
for (int j = 0; j < E; j++) {
// 处理每一条边
int u = findVertexOfEdge(j, E); // 获取边的起点（此处findVertexOfEdge是一个假想函数，实际需要根据graph的结构实现）
int v = graph[u][j]; // 获取边的终点
int weight = getEdgeWeight(u, j, E); // 获取边的权重（同样，getEdgeWeight是一个假想函数，需根据实际情况实现）
// 进行松弛操作，如果通过当前边可以缩短距离，则更新dist数组
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
// 检查是否存在负权回路
for (int j = 0; j < E; j++) {
int u = findVertexOfEdge(j, E);
int v = graph[u][j];
int weight = getEdgeWeight(u, j, E);
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle.");
return;
}
}
// 输出或处理最短路径结果
// ...
}
// 假设findVertexOfEdge和getEdgeWeight是你根据实际图数据结构实现的辅助函数
// 实际上这部分取决于你如何存储图的邻接矩阵或邻接表。
// 示例方法：
private static int findVertexOfEdge(int edgeId, int totalEdgesPerVertex) {
// 实现细节取决于你的图结构，这里仅作为占位符
throw new UnsupportedOperationException("This is a placeholder method, implement according to your graph structure.");
}
private static int getEdgeWeight(int vertex, int edgeId, int totalEdgesPerVertex) {
// 实现细节取决于你的图结构，这里仅作为占位符
throw new UnsupportedOperationException("This is a placeholder method, implement according to your graph structure.");
}
}请根据实际的图数据结构自行实现findVertexOfEdge和getEdgeWeight这两个方法。在实际的邻接矩阵中，findVertexOfEdge可能不需要实现，因为可以通过遍历矩阵的行来确定起点。而在邻接表结构中，这两个方法则是必不可少的。同时，请注意，这里的代码假设图是以邻接矩阵的形式存储的，实际使用时需要根据具体存储方式调整代码。
Floyd-Warshall算法能够解决所有顶点对间的最短路径问题，它通过动态规划的方式遍历所有可能的中间节点，从而计算出任意两点间的最短路径。
以下是Floyd-Warshall算法在Java中的实现，用于计算有向图中任意两点间的最短路径：
public class FloydWarshall {
public static void floydWarshall(int[][] graph, int verticesCount) {
// 初始化距离矩阵
int[][] dist = new int[verticesCount][verticesCount];
for (int i = 0; i < verticesCount; i++) {
for (int j = 0; j < verticesCount; j++) {
dist[i][j] = graph[i][j];
}
}
// 主循环，k是中间节点
for (int k = 0; k < verticesCount; k++) {
// 更新距离矩阵
for (int i = 0; i < verticesCount; i++) {
for (int j = 0; j < verticesCount; j++) {
// 如果通过节点k作为中间节点，可以使得从i到j的距离更短，则更新dist[i][j]
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 检查是否有负权回路
for (int k = 0; k < verticesCount; k++) {
if (dist[k][k] < 0) {
System.out.println("Graph contains negative weight cycle.");
return;
}
}
// 输出或处理最短路径结果
// dist[i][j] 现在包含了顶点i到顶点j的最短距离
}
public static void main(String[] args) {
int verticesCount = 4;
int[][] graph = {
{0, 5, 0, 0},
{0, 0, 3, 10},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
floydWarshall(graph, verticesCount);
}
}在上述代码中，graph是一个邻接矩阵，表示图中每一对顶点之间的直接距离。floydWarshall方法接收这个邻接矩阵和顶点数量作为参数，通过迭代更新dist矩阵，最终得到dist[i][j]表示从顶点i到顶点j的最短距离。如果有负权回路，Floyd-Warshall算法将在最后一次迭代结束后发现dist[i][i]为负值。在实际应用中，可能还需要记录路径信息，但这不在上述基本实现中涵盖。
原文链接: https://www.yukx.com/arithmetic/article/details/2478.html 优科学习网最短路径算法
