最短路径算法
关于最短路径算法的Java实现,这里简述一下几种常用的算法及其基本原理,并给出一个Dijkstra算法的基本实现框架。
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算法(适用于存在负权边的图)
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算法能够解决所有顶点对间的最短路径问题,它通过动态规划的方式遍历所有可能的中间节点,从而计算出任意两点间的最短路径。
以下是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 优科学习网最短路径算法
-
MD5(Message-DigestAlgorithm5)是一种广泛使用的散列函数(哈希函数),由美国密码学家罗纳德·李维斯特(RonaldL.Rivest)在1991年设计。MD5的作用是对任意长度的信息生成一个固定长度(128位,即32个十六进制字符)的“指纹”或“消息摘要”,并且几乎不可能找到
-
循环冗余校验(CyclicRedundancyCheck,CRC)是一种用于检测数据传输和存储过程中发生错误的技术,属于一种基于数学原理的错误检测编码(ErrorDetectionCoding)方法。它通过在原始数据上附加一个固定长度的校验码,使得接收端可以通过同样的计算规则对收到的数据进行校验,确
-
AES(AdvancedEncryptionStandard)是一种广泛使用的对称密钥加密算法,它是美国国家标准与技术研究院(NIST)于2001年制定的加密标准,用于替代原有的DES(DataEncryptionStandard)。AES算法以其高效性、安全性和可靠性而著称,在众多应用领域中被广泛
-
RSA(Rivest-Shamir-Adleman)是一种广泛应用的非对称加密算法,由RonRivest、AdiShamir和LenAdleman在1977年提出。其安全性基于数学上的大数因子分解难题,即对于足够大的两个素数p和q而言,已知它们的乘积很容易,但想要从这个乘积中恢复原始的素数则异常困难
-
最小生成树(MinimumSpanningTree,MST)是一种图论算法,用于在一个带权重的无向连通图中找到一棵包括所有顶点且总权重尽可能小的树。常见的最小生成树算法有两种:Prim算法和Kruskal算法。Prim算法原理:Prim算法是一种贪心算法,它从图中的一个顶点开始,逐步增加边,每次都添
-
关于最短路径算法的Java实现,这里简述一下几种常用的算法及其基本原理,并给出一个Dijkstra算法的基本实现框架。Dijkstra算法(适用于无负权边的图)Dijkstra算法用于寻找图中一个顶点到其他所有顶点的最短路径。它维护了一个距离表,用来存储从源点到各个顶点的已知最短距离,并且每次都会选