非加权无向图Floyd-Warshall算法优化与改进

By | 06月18日
Advertisement

http://yxwang.spaces.live.com/Blog/cns!BD1957499C10CE30!487.entry

非加权无向图Floyd-Warshall算法优化与改进最近反复用到图的(两两结点)最短路径长度算法,对于非加权、无向图的邻接矩阵,采用经典的Floyd-Warshall算法似乎效率不高。

在网上找了点资料,Valerio Schiavoni的这篇日志有点帮助。简要摘录过来,并统一了符号,校正了错误。

以下代码中, int a[i][j]表示从结点i到j的最短路径长度, n为结点总数。

--------------------------------------------------------------------------------

经典实现

<textarea cols="50" rows="15" name="code" class="cpp">void computeAPSP(const int n) { /* calculate shortest paths from every vertex to every vertex */ for (int k = 0; k &lt; n; k++) { for (int i = 0; i &lt; n; i++) { for (int j = 0; j &lt; n; j++) { a[i][j] = min( a[i][j], a[i][k] + a[k][j] ); } } } }</textarea>

--------------------------------------------------------------------------------

第1次优化: 利用矩阵的对称性

<textarea cols="50" rows="15" name="code" class="cpp">void computeAPSP(const int n) { for (int k = 0; k &lt; n; k++) { for (int i = 0; i &lt; n; i++) { const int a_ki = a[k][i]; for (int j = 0; j &lt; i; j++) { a[i][j] = min( a[i][j], a_ki + a[k][j] ); a[j][i] = a[i][j]; } } } }</textarea>

--------------------------------------------------------------------------------

第2次优化: 只使用矩阵的下三角部分

<textarea cols="50" rows="15" name="code" class="cpp">void computeAPSP(const int n) { for (int k = 0; k &lt; n; k++) { for (int i = 0; i &lt; n; i++) { if (k != i) { const int a_ki = (k &lt; i) ? a[i][k] : a[k][i]; for (int j = 0; j &lt; min(k, i); j++) a[i][j] = min( a[i][j], a_ki + a[k][j] ); for (int j = k + 1; j &lt; i; j++) a[i][j] = min( a[i][j], a_ki + a[j][k] ); } } } } </textarea>

--------------------------------------------------------------------------------

第3次优化: 跳过不存在的路径

<textarea cols="50" rows="15" name="code" class="cpp">void computeAPSP(const int n) { for (int k = 0; k &lt; n; k++) { for (int i = 0; i &lt; n; i++) { if (k != i) { const int a_ki = (k &lt; i) ? a[i][k] : a[k][i]; // skip if no path if (a_ki == POSITIVE_INFINITY) continue; for (int j = 0; j &lt; min(k, i); j++) a[i][j] = min( a[i][j], a_ki + a[k][j] ); for (int j = k + 1; j &lt; i; j++) a[i][j] = min( a[i][j], a_ki + a[j][k] ); } } } }</textarea>

--------------------------------------------------------------------------------

第4次优化: 避免大量调用数学函数

<textarea cols="50" rows="15" name="code" class="cpp">void computeAPSP(const int n) { for (int k = 0; k &lt; n; k++) { for (int i = 0; i &lt; n; i++) { if (k != i) { const int a_ki = (k &lt; i) ? a[i][k] : a[k][i]; // skip if no path if (a_ki == POSITIVE_INFINITY) continue; for (int j = 0; j &lt; min(k, i); j++) { const int s_kj = a_ki + a[k][j]; if( s_kj &lt; a[i][j] ) a[i][j] = s_kj; } for (int j = k + 1; j &lt; i; j++) { const int s_jk = a_ki + a[j][k]; if( s_jk &lt; a[i][j] ) a[i][j] = s_jk; } } } } }</textarea>

Similar Posts:

  • 每日一省之————加权无向图的最小生成树算法(Prim/Kruskal算法)

    1.带权重的边的数据结构 /** * 该类对象可以表示图中的一条边 * @author lhever 2017年2月19日 下午5:10:49 * @version v1.0 */ public class Edge implements Comparable<Edge> { private int v; private int w; private final double weight; /** * 构造 * * @param v * @param w * @param weight *

  • floyd和warshall算法(作业)

    floyd算法的实现: #include <stdio.h> #include <stdlib.h> int n, dist[10][10]; //矩阵中的数字:999表示不可达,无穷大 void printDist(); void floyd() //floyd实现算法 { int i, j, k; for(k = 0; k < n; ++k){ printDist(); for(i = 0; i < n; ++i){ for(j = 0; j < n; ++j

  • 算法代码实现之Union-Find,Golang(Go语言)实现,quick-find、quick-union、加权quick-union(附带路径压缩优化)

    本算法主要解决动态连通性一类问题,这里尽量用精炼简洁的话来阐述. 数据结构描述: 有N个节点(索引0~N-1),可以查询节点数量 可以连接两个节点 可以查询两个节点是否连通 算法大致设计思路: 每个节点初始化为不同的整数标记 通过一个辅助函数查询某个节点的标记值 如果两节点标记相同,说明两节点是连通的 用一个包专门处理union-find算法(unionfind) 定义接口和基类(union_find.go): package unionfind   //union-find的quick-fin

  • 一道算法优化题,求有序数组是否存在两数之和等于第三个给定的数字

    1.题:给出一个函数,判断在一个给定的有序数组中,是否存在两个数之和等于给定的第三个数. 这道题本身挺简单,但是如果直接使用嵌套两个 for 循环的方式去做的话,时间复杂度非常之高. 希望能有大牛给出一个简单的算法优化思路. --cut-- 小亮_eecs在1970-01-01 20:22:20回答到: 经典的two sum problem,保存双指针,分别指向数组开头和末尾,假设数组非降序排列,分情况讨论: 如果当前两个数的和等于给定值,成功. 如果当前两个数的和小于给定值,头指针右移. 如果

  • 人工智能算法- 优化算法

    文/腾讯soso 林世飞 优化算法通常用来处理问题最优解的求解--这个问题有多个变量共同决定的,举一个例子比如有这样一张 人员关系表,需要绘制一张SOSO华尔兹(一种socialnetwork,http://tag.soso.com/),比如: 绘制方法有很多种,我们希望能够最终展现给用户的绘制是比较好阅读的,比如交叉线比较少,每个人的点排的比较开等等. 我们利用以下一个数据格式来描述最终的一个解,即一个向量包含每个人的坐标,假设:通常我们用一个 向量来表示解x, x =[a1,a2,-.] 这

  • WarShall算法--图的传递闭包(进一步演变成flayd算法)

    package graph; import java.util.ArrayList; import java.util.List; public class WarshallTest { public static void main(String[] args) { Warshall w = new Warshall(8); w.addVertex("a"); w.addVertex("b"); w.addVertex("c"); w.addV

  • poj 3660 Cow Contest(warshall算法)

    poj 3660 Cow Contest Description N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the co

  • 多线程队列的算法优化

    http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/ 多线程队列(Concurrent Queue)的使用场合非常多,高性能服务器中的消息队列,并行算法中的Work Stealing等都离不开它.对于一个队列来说有两个最主要的动作:添加(enqueue)和删除(dequeue)节点.在一个(或多个)线程在对一个队列进行enqueue操作的同时可能会有一个(或多个)线程对这个队列进行dequeue操

  • 算法优化之车牌识别---车牌识别优化项

    基于DM6437的车牌识别算法移植及优化 http://cdmd.cnki.com.cn/Article/CDMD-10701-1013114119.htm 5.1 车牌识别算法的移植52-54 5.1.1 车牌识别算法工程的创建52 5.1.2 算法的编译及调试52-53 5.1.3 算法的测试53-54 5.2 车牌程序设计54-55 5.2.1 图像采集和显示54 5.2.2 数据处理54-55 5.3 DSP算法优化概述55-59 5.3.1 DSP算法优化思想55-59 5.4 车牌识

  • 【算法】AES算法优化

    算法优化主要就是在矩阵相乘中,优化的方式也很简单,就是空间换时间. AES算法的矩阵是有特点的,矩阵如下: 02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 每一竖行都是02 01 01 03 组成. 分析矩阵相乘 02 03 01 01 a1 02*a1 + 03*a2 + 01*a3 + 01*a4 b1 01 02 03 01 * a2 = 01*a1 + 02*a2 + 03*a3 + 01*a4 = b2 01 01 02 03 a3 01

Tags: