网页制作与网站开发 实验报告,网站建设工作流程,wordpress图片托管,网站开发 方案概要引言
在图论中#xff0c;Floyd-Warshall算法是一种用于计算任意两点之间最短路径的动态规划算法。它适用于加权有向图和无向图#xff0c;可以处理带有负权重边的图#xff0c;但要求图中不能有负权重环。本文将详细介绍Floyd-Warshall算法的定义、步骤及其实现。
Floyd-…引言
在图论中Floyd-Warshall算法是一种用于计算任意两点之间最短路径的动态规划算法。它适用于加权有向图和无向图可以处理带有负权重边的图但要求图中不能有负权重环。本文将详细介绍Floyd-Warshall算法的定义、步骤及其实现。
Floyd-Warshall算法
定义
Floyd-Warshall算法是一种用于计算图中所有顶点对之间最短路径的算法。该算法利用动态规划的思想通过不断更新顶点对之间的最短路径最终得到所有顶点对的最短路径矩阵。
算法步骤
初始化创建一个距离矩阵dist其中dist[i][j]表示顶点i到顶点j的初始距离。如果i和j之间有边则dist[i][j]为边的权重如果i和j之间没有边且i≠j则dist[i][j]为正无穷大如果ij则dist[i][j]为0。更新距离矩阵对于每一对顶点(i, j)通过中间顶点k更新其最短路径。具体来说如果dist[i][j] dist[i][k] dist[k][j]则更新dist[i][j] dist[i][k] dist[k][j]。重复更新重复上述步骤直到所有顶点对之间的最短路径都被计算出来。
示例
假设我们有一个带权有向图顶点集合为 ({A, B, C, D})边和权重集合为 ({(A, B, 3), (A, C, 8), (A, D, -4), (B, D, 1), (B, C, -2), (C, A, 4), (D, C, 7), (D, B, -5)})。 #mermaid-svg-C1rXYKfcNyYoTquN {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-C1rXYKfcNyYoTquN .error-icon{fill:#552222;}#mermaid-svg-C1rXYKfcNyYoTquN .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-C1rXYKfcNyYoTquN .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-C1rXYKfcNyYoTquN .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-C1rXYKfcNyYoTquN .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-C1rXYKfcNyYoTquN .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-C1rXYKfcNyYoTquN .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-C1rXYKfcNyYoTquN .marker{fill:#333333;stroke:#333333;}#mermaid-svg-C1rXYKfcNyYoTquN .marker.cross{stroke:#333333;}#mermaid-svg-C1rXYKfcNyYoTquN svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-C1rXYKfcNyYoTquN .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-C1rXYKfcNyYoTquN .cluster-label text{fill:#333;}#mermaid-svg-C1rXYKfcNyYoTquN .cluster-label span{color:#333;}#mermaid-svg-C1rXYKfcNyYoTquN .label text,#mermaid-svg-C1rXYKfcNyYoTquN span{fill:#333;color:#333;}#mermaid-svg-C1rXYKfcNyYoTquN .node rect,#mermaid-svg-C1rXYKfcNyYoTquN .node circle,#mermaid-svg-C1rXYKfcNyYoTquN .node ellipse,#mermaid-svg-C1rXYKfcNyYoTquN .node polygon,#mermaid-svg-C1rXYKfcNyYoTquN .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-C1rXYKfcNyYoTquN .node .label{text-align:center;}#mermaid-svg-C1rXYKfcNyYoTquN .node.clickable{cursor:pointer;}#mermaid-svg-C1rXYKfcNyYoTquN .arrowheadPath{fill:#333333;}#mermaid-svg-C1rXYKfcNyYoTquN .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-C1rXYKfcNyYoTquN .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-C1rXYKfcNyYoTquN .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-C1rXYKfcNyYoTquN .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-C1rXYKfcNyYoTquN .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-C1rXYKfcNyYoTquN .cluster text{fill:#333;}#mermaid-svg-C1rXYKfcNyYoTquN .cluster span{color:#333;}#mermaid-svg-C1rXYKfcNyYoTquN div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-C1rXYKfcNyYoTquN :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 3 8 -4 1 -2 4 7 -5 A B C D Floyd-Warshall算法图解
初始化距离矩阵 A B C D
A 0 3 8 -4
B ∞ 0 -2 1
C 4 ∞ 0 ∞
D ∞ -5 7 0通过顶点A更新距离矩阵 A B C D
A 0 3 8 -4
B 7 0 -2 1
C 4 ∞ 0 ∞
D 3 -5 7 0通过顶点B更新距离矩阵 A B C D
A 0 3 1 -4
B 5 0 -2 1
C 4 7 0 ∞
D 3 -5 2 0通过顶点C更新距离矩阵 A B C D
A 0 3 1 -4
B 5 0 -2 1
C 4 7 0 ∞
D 3 -5 2 0通过顶点D更新距离矩阵 A B C D
A 0 -1 1 -4
B 5 0 -2 1
C 4 -1 0 -3
D 3 -5 2 0Floyd-Warshall算法实现
下面是用Java实现Floyd-Warshall算法的代码示例
import java.util.Arrays;public class FloydWarshallAlgorithm {private static final int INF 99999; // 表示无穷大的值// 计算任意两点之间的最短路径public void floydWarshall(int[][] graph) {int vertices graph.length;int[][] dist new int[vertices][vertices];// 初始化距离矩阵for (int i 0; i vertices; i) {for (int j 0; j vertices; j) {dist[i][j] graph[i][j];}}// 更新距离矩阵for (int k 0; k vertices; k) {for (int i 0; i vertices; i) {for (int j 0; j vertices; j) {if (dist[i][k] ! INF dist[k][j] ! INF dist[i][k] dist[k][j] dist[i][j]) {dist[i][j] dist[i][k] dist[k][j];}}}}printSolution(dist);}// 打印最短路径矩阵private void printSolution(int[][] dist) {int vertices dist.length;System.out.println(顶点对之间的最短路径矩阵);for (int i 0; i vertices; i) {for (int j 0; j vertices; j) {if (dist[i][j] INF) {System.out.print(INF );} else {System.out.print(dist[i][j] );}}System.out.println();}}public static void main(String[] args) {int[][] graph {{0, 3, 8, -4},{INF, 0, -2, 1},{4, INF, 0, INF},{INF, -5, 7, 0}};FloydWarshallAlgorithm floydWarshall new FloydWarshallAlgorithm();floydWarshall.floydWarshall(graph);}
}代码注释 常量定义 private static final int INF 99999; // 表示无穷大的值INF 表示无穷大用于表示顶点之间没有直接连接。 Floyd-Warshall算法 public void floydWarshall(int[][] graph) {int vertices graph.length;int[][] dist new int[vertices][vertices];// 初始化距离矩阵for (int i 0; i vertices; i) {for (int j 0; j vertices; j) {dist[i][j] graph[i][j];}}// 更新距离矩阵for (int k 0; k vertices; k) {for (int i 0; i vertices; i) {for (int j 0; j vertices; j) {if (dist[i][k] ! INF dist[k][j] ! INF dist[i][k] dist[k][j] dist[i][j]) {dist[i][j] dist[i][k] dist[k][j];}}}}printSolution(dist);
}floydWarshall 方法实现了Floyd-Warshall算法计算任意两点之间的最短路径。 打印最短路径矩阵 private void printSolution(int[][] dist) {int vertices dist.length;System.out.println(顶点对之间的最短路径矩阵);for (int i 0; i vertices; i) {for (int j 0; j vertices; j) {if (dist[i][j] INF) {System.out.print(INF );} else {System.out.print(dist[i][j] );}}System.out.println();}
}printSolution 方法用于打印最短路径矩阵。
结论
通过上述讲解和实例代码我们详细展示了Floyd-Warshall算法的定义、步骤及其实现。Floyd-Warshall算法是一种重要的最短路径算法适用于计算任意两点之间的最短路径。希望这篇博客对您有所帮助 如果您觉得这篇文章对您有帮助请关注我的CSDN博客点赞并收藏这篇文章您的支持是我持续创作的动力 关键内容总结
Floyd-Warshall算法的定义Floyd-Warshall算法的步骤Floyd-Warshall算法的实现及其
代码注释 推荐阅读深入探索设计模式专栏详细讲解各种设计模式的应用和优化。点击查看深入探索设计模式。 特别推荐设计模式实战专栏深入解析设计模式的实际应用提升您的编程技巧。点击查看设计模式实战。
如有任何疑问或建议欢迎在评论区留言讨论。谢谢阅读
