兰州网站设计公司,网站内如何做内部链接,祭祀网站建设方案,北京品牌网站最短路径 穿越负权迷雾#xff1a;Floyd算法如何解锁全图最短路径#xff1f;一、Floyd算法1.1 算法思想1.2 算法逻辑1.3 算法评价1.4 算法限制 二、三种算法对比#x1f31f;结语 穿越负权迷雾#xff1a;Floyd算法如何解锁全图最短路径#xff1f;
大家好… 最短路径 穿越负权迷雾Floyd算法如何解锁全图最短路径一、Floyd算法1.1 算法思想1.2 算法逻辑1.3 算法评价1.4 算法限制 二、三种算法对比结语 穿越负权迷雾Floyd算法如何解锁全图最短路径
大家好很高兴又和大家见面啦
你是否曾为Dijkstra算法在负权图前折戟而苦恼这位单源最短路径的王者虽能高效征服正权图却对负权边束手无策——当图上出现“补贴路径”负权值时Dijkstra的贪心策略将彻底失效
而今天登场的图灵奖得主Floyd算法正为此而生它用动态规划的三重循环复杂度O(丨V丨³以惊人的简洁性完成两大壮举 1️⃣ 暴力破解全源最短路径同时计算图中任意两点的最短距离 2️⃣ 完美驾驭负权图轻松化解Dijkstra的致命弱点除负权环外
透过递推矩阵的魔法你将看到 ▸ 初始邻接矩阵如何在中转点催化下层层蜕变含分步图解 ▸ 路径矩阵如何像侦探般记录关键前驱节点 ▸ C语言实现如何用双矩阵破译路径密码 ▸ 负权环检测为何是算法必备的安全阀
文末更奉上三大算法对决表助你秒选最佳路径方案点击揭开全源最短路径的终极奥秘→
一、Floyd算法
Floyd算法是由罗伯特·弗洛伊德Robert·W·Floyd提出用于解决所有顶点之间的最短路径问题。 罗伯特·弗洛伊德Robert·W·Floyd: 1978年图灵奖得主提出了Floyd算法Floyd-Warshall算法提出了堆排序算法 1.1 算法思想
Floyd算法使用动态规划的思想将求解每一对顶点之间的最短路径分解为多个阶段进行求解
对于n个顶点的图G求任意一对顶点 V i − V j V_i-V_j Vi−Vj 之间的最短路径可将其分解为以下阶段 初始阶段不允许在其它顶点中转获取各顶点之间的最短路径 V 0 V_0 V0 阶段允许在 V 0 V_0 V0 中转再次获取各顶点之间的最短路径 V 1 V_1 V1 阶段允许在 V 0 、 V 1 V_0、V_1 V0、V1 中转再次获取各顶点之间的最短路径 ⋯ \cdots ⋯ V n − 1 V_{n-1} Vn−1阶段允许在 V 0 、 V 1 、 ⋯ 、 V n − 1 V_0、V_1、\cdots、V_{n-1} V0、V1、⋯、Vn−1 中转再次获取各顶点之间的最短路径
为了更好的说明该算法的思想下面我们以有向图G为例介绍一下整个算法的执行过程 #mermaid-svg-5YxciqcRJMb5QEVe {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-5YxciqcRJMb5QEVe .error-icon{fill:#552222;}#mermaid-svg-5YxciqcRJMb5QEVe .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-5YxciqcRJMb5QEVe .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-5YxciqcRJMb5QEVe .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-5YxciqcRJMb5QEVe .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-5YxciqcRJMb5QEVe .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-5YxciqcRJMb5QEVe .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-5YxciqcRJMb5QEVe .marker{fill:#333333;stroke:#333333;}#mermaid-svg-5YxciqcRJMb5QEVe .marker.cross{stroke:#333333;}#mermaid-svg-5YxciqcRJMb5QEVe svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-5YxciqcRJMb5QEVe .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-5YxciqcRJMb5QEVe .cluster-label text{fill:#333;}#mermaid-svg-5YxciqcRJMb5QEVe .cluster-label span{color:#333;}#mermaid-svg-5YxciqcRJMb5QEVe .label text,#mermaid-svg-5YxciqcRJMb5QEVe span{fill:#333;color:#333;}#mermaid-svg-5YxciqcRJMb5QEVe .node rect,#mermaid-svg-5YxciqcRJMb5QEVe .node circle,#mermaid-svg-5YxciqcRJMb5QEVe .node ellipse,#mermaid-svg-5YxciqcRJMb5QEVe .node polygon,#mermaid-svg-5YxciqcRJMb5QEVe .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-5YxciqcRJMb5QEVe .node .label{text-align:center;}#mermaid-svg-5YxciqcRJMb5QEVe .node.clickable{cursor:pointer;}#mermaid-svg-5YxciqcRJMb5QEVe .arrowheadPath{fill:#333333;}#mermaid-svg-5YxciqcRJMb5QEVe .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-5YxciqcRJMb5QEVe .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-5YxciqcRJMb5QEVe .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-5YxciqcRJMb5QEVe .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-5YxciqcRJMb5QEVe .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-5YxciqcRJMb5QEVe .cluster text{fill:#333;}#mermaid-svg-5YxciqcRJMb5QEVe .cluster span{color:#333;}#mermaid-svg-5YxciqcRJMb5QEVe 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-5YxciqcRJMb5QEVe :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 6 4 5 10 13 a b c 在这个图中包含3个顶点和5条弧 ∣ V ∣ { a , b , c } |V| \{a, b, c\} ∣V∣{a,b,c} ∣ E ∣ { a , b , 6 , a , c , 13 , b , a , 10 , b , c , 4 , c , a , 5 } |E| \{\\a, b, 6, a, c, 13, \\ b, a, 10, b, c, 4, \\ c, a, 5\\\} ∣E∣{a,b,6,a,c,13,b,a,10,b,c,4,c,a,5}
在Floyd算法执行的过程中算法每一次执行都会递推产生一个 3 3 3 阶方阵序列
初始阶段各顶点之间的路径默认没有中转点 点 V i V_i Vi 与点 V j V_j Vj 之间连通则从点 V i V_i Vi 到点 V j V_j Vj 的弧 v i , v j v_i, v_j vi,vj 的权值即为这两个顶点之间的路径长度点 V i V_i Vi 与点 V j V_j Vj 之间不连通则默认这两个顶点之间的路径长度为 ∞ \infty ∞初始阶段生成的 3 3 3 阶方阵如下所示 初始阶段方阵 V ( − 1 ) [ ∣ a ∣ b ∣ c ∣ — — — — — — — — a ∣ 0 ∣ 6 ∣ 13 ∣ — — — — — — — — b ∣ 10 ∣ 0 ∣ 4 ∣ — — — — — — — — c ∣ 5 ∣ ∞ ∣ 0 ∣ ] {初始阶段方阵V^{(-1)}} \begin{bmatrix} | a | b| c| \\ — — — — —— ——\\ a | 0| 6| 13| \\ — — — — —— ——\\ b | 10 | 0| 4| \\ — — — — —— ——\\ c | 5 | \infty | 0| \end{bmatrix} 初始阶段方阵V(−1) —a—b—c∣—∣—∣—∣a—0—10—5∣—∣—∣—∣b—6—0—∞∣—∣—∣—∣c—13—4—0∣—∣—∣—∣ V 0 V_0 V0阶段各顶点之间借助 a a a 为中转点继续查找各顶点之间的最短路径 点 a a a 到点 b b b 借助顶点 a a a 为中转点没有更优路径点 a a a 到点 c c c 借助顶点 a a a 为中转点没有更优路径点 b b b 到点 a a a 借助顶点 a a a 为中转点没有更优路径点 b b b 到点 c c c 借助顶点 a a a 为中转点没有更优路径点 c c c 到点 a a a 借助顶点 a a a 为中转点没有更优路径点 c c c 到点 b b b 借助顶点 a a a为中转点存在更优路径 c , a , b , 11 c, a, b, 11 c,a,b,11 V 0 V_0 V0 阶段生成的 3 3 3 阶方阵如下所示 V 0 阶段方阵 V ( 0 ) [ ∣ a ∣ b ∣ c ∣ — — — — — — — — a ∣ 0 ∣ 6 ∣ 13 ∣ — — — — — — — — b ∣ 10 ∣ 0 ∣ 4 ∣ — — — — — — — — c ∣ 5 ∣ 11 ∣ 0 ∣ ] {V_0阶段方阵V^{(0)}} \begin{bmatrix} | a | b| c| \\ — — — — —— ——\\ a | 0| 6| 13| \\ — — — — —— ——\\ b | 10 | 0| 4| \\ — — — — —— ——\\ c | 5 | \color{red}11 | 0| \end{bmatrix} V0阶段方阵V(0) —a—b—c∣—∣—∣—∣a—0—10—5∣—∣—∣—∣b—6—0—11∣—∣—∣—∣c—13—4—0∣—∣—∣—∣ V 1 V_1 V1阶段各顶点之间借助 a a a 为中转点继续查找各顶点之间的最短路径 点 a a a 到点 b b b 借助顶点 a 、 b a、b a、b 为中转点没有更优路径点 a a a 到点 c c c 借助顶点 a 、 b a、b a、b 为中转点存在更优路径 a , b , c , 10 a, b, c, 10 a,b,c,10点 b b b 到点 a a a 借助顶点 a 、 b a、b a、b 为中转点没有更优路径点 b b b 到点 c c c 借助顶点 a 、 b a、b a、b 为中转点没有更优路径点 c c c 到点 a a a 借助顶点 a 、 b a、b a、b为中转点没有更优路径点 c c c 到点 b b b 借助顶点 a 、 b a、b a、b为中转点没有更优路径 V 1 V_1 V1 阶段生成的 3 3 3 阶方阵如下所示 V 1 阶段方阵 V ( 1 ) [ ∣ a ∣ b ∣ c ∣ — — — — — — — — a ∣ 0 ∣ 6 ∣ 10 ∣ — — — — — — — — b ∣ 10 ∣ 0 ∣ 4 ∣ — — — — — — — — c ∣ 5 ∣ 11 ∣ 0 ∣ ] {V_1阶段方阵V^{(1)}} \begin{bmatrix} | a | b| c| \\ — — — — —— ——\\ a | 0| 6| \color{red}10| \\ — — — — —— ——\\ b | 10 | 0| 4| \\ — — — — —— ——\\ c | 5 | \color{red} 11| 0| \end{bmatrix} V1阶段方阵V(1) —a—b—c∣—∣—∣—∣a—0—10—5∣—∣—∣—∣b—6—0—11∣—∣—∣—∣c—10—4—0∣—∣—∣—∣ V 2 V_2 V2阶段各顶点之间借助 a a a 为中转点继续查找各顶点之间的最短路径 点 a a a 到点 b b b 借助顶点 a 、 b 、 c a、b、c a、b、c 为中转点没有更优路径点 a a a 到点 c c c 借助顶点 a 、 b 、 c a、b、c a、b、c 为中转点没有更优路径点 b b b 到点 a a a 借助顶点 a 、 b 、 c a、b、c a、b、c 为中转点存在更优路径 b , c , a , 9 b, c, a, 9 b,c,a,9点 b b b 到点 c c c 借助顶点 a 、 b 、 c a、b、c a、b、c 为中转点没有更优路径点 c c c 到点 a a a 借助顶点 a 、 b 、 c a、b、c a、b、c为中转点没有更优路径点 c c c 到点 b b b 借助顶点 a 、 b 、 c a、b、c a、b、c为中转点没有更优路径 V 2 V_2 V2 阶段生成的 3 3 3 阶方阵如下所示 V 2 阶段方阵 V ( 2 ) [ ∣ a ∣ b ∣ c ∣ — — — — — — — — a ∣ 0 ∣ 6 ∣ 10 ∣ — — — — — — — — b ∣ 9 ∣ 0 ∣ 4 ∣ — — — — — — — — c ∣ 5 ∣ 11 ∣ 0 ∣ ] {V_2阶段方阵V^{(2)}} \begin{bmatrix} | a | b| c| \\ — — — — —— ——\\ a | 0| 6| \color{red}10| \\ — — — — —— ——\\ b | \color{red}9 | 0| 4| \\ — — — — —— ——\\ c | 5 | \color{red} 11| 0| \end{bmatrix} V2阶段方阵V(2) —a—b—c∣—∣—∣—∣a—0—9—5∣—∣—∣—∣b—6—0—11∣—∣—∣—∣c—10—4—0∣—∣—∣—∣
到此为止我们就完成了该图G中所有顶点之间的最短路径的获取
1.2 算法逻辑
在上述的过程中我们不难发现整个Floyd算法在执行的过程中实际上就是在维护一个大小为 ∣ V ∣ × ∣ V ∣ |V| × |V| ∣V∣×∣V∣ 的二维数组或者说是图G的邻接矩阵
为了更加清晰的获取到各点之间的准确路径我们还可以再增加一个记录路径的矩阵path[][]该矩阵的功能就是记录从点 V i V_i Vi 到点 V j V_j Vj 时途径的中转点即最短路径中点 V j V_j Vj 的前驱顶点
算法的整个执行过程实际上就是在遍历图G的邻接矩阵只不过我们需要遍历 ∣ V ∣ |V| ∣V∣ 次每一次遍历都相当于将点 V k V_k Vk 作为中转点去查找是否存在更短的路径
算法的C语言实现如下所示
void Floyd(AMGraph* g,int*** A,int*** path) {// 创建递推矩阵A与路径矩阵path*A (int**)calloc(g-ver_num, sizeof(int*));assert(*A);*path (int**)calloc(g-ver_num, sizeof(int*));assert(*path);for (int i 0; i g-ver_num; i) {(*A)[i] (int*)calloc(g-ver_num, sizeof(int));assert((*A)[i]);(*path)[i] (int*)calloc(g-ver_num, sizeof(int));assert((*path)[i]);}// 初始阶段for (int i 0; i g-ver_num; i) {for (int j 0; j g-ver_num; j) {(*A)[i][j] g-edge_matrix[i][j];// 路径存在记录当前路径的前驱顶点if (i ! j (*A)[i][j] ! INT_MAX) {(*path)[i][j] i;}// 路径不存在则初始化为-1else {(*path)[i][j] -1;}}}// 递推阶段——以点K为中转点for (int k 0; k g-ver_num; k) {// 遍历矩阵for (int i 0; i g-ver_num; i) {for (int j 0; j g-ver_num; j) {// 当前距离大于以点k为中转点的路径长度if ((*A)[i][k] ! INT_MAX (*A)[k][j] ! INT_MAX ((*A)[i][j] (*A)[i][k] (*A)[k][j])) {(*A)[i][j] (*A)[i][k] (*A)[k][j]; // 更新点i到点j的路径长度(*path)[i][j] (*path)[k][j]; // 更新该路径上点j的前驱顶点信息}}}}
}1.3 算法评价
该算法实现的方式其时间复杂度和空间复杂度分别为
时间复杂度 T ( N ) O ( ∣ V ∣ 3 ) T(N) O(|V|^3) T(N)O(∣V∣3)空间复杂度 S ( N ) O ( ∣ V ∣ 2 ) S(N) O(|V|^2) S(N)O(∣V∣2)
可以看到算法中最主要的时间消耗在于递推的过程
遍历一趟矩阵需要 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2) 的时间复杂度总共需要遍历 ∣ V ∣ |V| ∣V∣ 趟
而算法的主要空间消耗在于对递推矩阵 A[][] 和路径矩阵path[][]的空间上为了完整的记录所有结点的信息因此这两个矩阵的大小均为 ∣ V ∣ 2 |V|^2 ∣V∣2
1.4 算法限制
在上述的实现中并不能完整的展示Floyd算法主要原因是因为该算法无法处理负权值回路 #mermaid-svg-WTFRxpjckaUh3uf4 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-WTFRxpjckaUh3uf4 .error-icon{fill:#552222;}#mermaid-svg-WTFRxpjckaUh3uf4 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-WTFRxpjckaUh3uf4 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-WTFRxpjckaUh3uf4 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-WTFRxpjckaUh3uf4 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-WTFRxpjckaUh3uf4 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-WTFRxpjckaUh3uf4 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-WTFRxpjckaUh3uf4 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-WTFRxpjckaUh3uf4 .marker.cross{stroke:#333333;}#mermaid-svg-WTFRxpjckaUh3uf4 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-WTFRxpjckaUh3uf4 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-WTFRxpjckaUh3uf4 .cluster-label text{fill:#333;}#mermaid-svg-WTFRxpjckaUh3uf4 .cluster-label span{color:#333;}#mermaid-svg-WTFRxpjckaUh3uf4 .label text,#mermaid-svg-WTFRxpjckaUh3uf4 span{fill:#333;color:#333;}#mermaid-svg-WTFRxpjckaUh3uf4 .node rect,#mermaid-svg-WTFRxpjckaUh3uf4 .node circle,#mermaid-svg-WTFRxpjckaUh3uf4 .node ellipse,#mermaid-svg-WTFRxpjckaUh3uf4 .node polygon,#mermaid-svg-WTFRxpjckaUh3uf4 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-WTFRxpjckaUh3uf4 .node .label{text-align:center;}#mermaid-svg-WTFRxpjckaUh3uf4 .node.clickable{cursor:pointer;}#mermaid-svg-WTFRxpjckaUh3uf4 .arrowheadPath{fill:#333333;}#mermaid-svg-WTFRxpjckaUh3uf4 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-WTFRxpjckaUh3uf4 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-WTFRxpjckaUh3uf4 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-WTFRxpjckaUh3uf4 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-WTFRxpjckaUh3uf4 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-WTFRxpjckaUh3uf4 .cluster text{fill:#333;}#mermaid-svg-WTFRxpjckaUh3uf4 .cluster span{color:#333;}#mermaid-svg-WTFRxpjckaUh3uf4 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-WTFRxpjckaUh3uf4 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} -9 2 5 a b c 在上图中如果我们要求顶点b到顶点b的最短路径显然我们每走一次路径 b , c , a , b b, c, a, b b,c,a,b 该带权路径长度就会-2走的次数越多该带权路径长度越小在这种情况下我们就无法通过Floyd算法正确的得到最短路径因此我们还需要在算法中加入对负权环的判断 // 检测负权环for (int i 0; i g-ver_num; i) {if ((*A)[i][i] 0) {printf(该图中存在负权环);return;}}我这里对负权环的处理是采取的打印提示的方式当然也可以选择别的方式只要能够对负权环进行一个正确的检测即可。
二、三种算法对比
现在我们已经介绍完了处理最短路径问题的三种算法BFS、Dijkstra、Floyd下面我们就从六个维度来对比一下这三个算法的区别
BFSDijkstraFloyd用途求单源最短路径求单源最短路径求各顶点之间的最短路径无权图适用适用适用带权图不适用适用适用带负权值的图不适用不适用适用带负权值回路的图不适用不适用不适用时间复杂度 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)或 O ( ∣ V ∣ ∣ E ∣ ) O(|V||E|) O(∣V∣∣E∣) O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)或 O ( ∣ E ∣ log ∣ V ∣ ) O(|E|\log|V|) O(∣E∣log∣V∣) O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)
在实际的问题中我们可以根据自己的需求选择合适的算法来处理最短路径问题
结语
通过本文的探索我们揭开了Floyd算法的神秘面纱 三重循环的优雅暴力以 O ( 丨 V 丨 3 ) O(丨V丨^3) O(丨V丨3) 时间复杂度征服全源最短路径问题 动态规划的智慧结晶通过递推矩阵的巧妙迭代层层解锁最优路径 负权图的破壁者打破Dijkstra算法局限轻松驾驭负权边除负权环外 双矩阵的完美协奏A矩阵记录距离path矩阵回溯路径实现路径溯源 下一篇预告 在图论的奇妙世界中我们将迎来新的伙伴 《有向无环图表达式的终极优化引擎》
揭秘如何用DAG实现表达式树的重构探索公共子表达式消除的图解法图解拓扑排序如何实现无环表达式优化直击编译器中表达式优化的核心技术
如果本文助你攻克了最短路径难题 点击关注 不迷路 点亮❤️【赞】支持创作火花 ️ 加入⭐【收藏】构建知识图谱 举手之劳【转发】让更多开发者突破算法迷雾
你对Floyd算法还有哪些疑问欢迎在评论区✍️留下思考我们一起探讨图论精髓
