文档章节

最短路径(shortest path)之Floyd算法

千面人
 千面人
发布于 2016/12/08 21:11
字数 292
阅读 9
收藏 0

Floyd算法求解最短路径应该是本科数据结构的课程,以前没什么感觉,经过多年,再次看到,发现实在太漂亮了,形式如此简洁,忍不住要赞下:

/* Floyd算法,求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */ 
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{ 
    int v,w,k; 
    for(v=0; v<G.numVertexes; ++v)            /* 初始化D与P */ 
    { 
        for(w=0; w<G.numVertexes; ++w) 
        {
            (*D)[v][w]=G.arc[v][w];          /* D[v][w]值即为对应点间的权值 */
            (*P)[v][w]=w;                    /* 初始化P */
        }
    }
    for(k=0; k<G.numVertexes; ++k) 
    {
        for(v=0; v<G.numVertexes; ++v) 
        { 
            for(w=0; w<G.numVertexes; ++w) 
            {
                if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
                {
                    /* 如果经过下标为k顶点路径比原两点间路径更短 */
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];     /* 将当前两点间权值设为更小的一个 */
                    (*P)[v][w]=(*P)[v][k];                /* 路径设置为经过下标为k的顶点 */
                }
            }
        }
    }
}

参考资料:

【1】数据结构之最短路径(Floyd) http://blog.chinaunix.net/uid-26548237-id-3834873.html 

© 著作权归作者所有

共有 人打赏支持
千面人
粉丝 16
博文 48
码字总数 24904
作品 0
杭州
高级程序员
私信 提问
理解Floyd-Warshall算法

我们之前分别讨论了Dijkstra算法和Bellman-Ford算法,它们解决的都是单源最短路径问题。本文讨论的Floyd-Warshall算法(下称FW算法)则适用于解决可有负权边但不可有负权环的“全局最短路径问...

桥头堡2015
2016/08/27
323
0
最短路径算法

单源最短路径问题 问题描述:给你一个顶点做源点,你想要知道,如何从源点到达其他所有点的最短路径。 OK,这个问题看起来没什么用。我们一般想知道的是A点到B点的最短路径,这个单源最短路径...

Hosee
2016/01/14
2.2K
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
789
5
最短路径-Dijkstra算法和Floyd算法

Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dij...

pointerException
2015/08/07
0
0
Dijkstra算法--单源最短路径

在http://blog.csdn.net/hackerzhidian/article/details/54898064这一篇博客中总结了一下在求图的最短路中的一个算法-Floyd算法,Floyd算法用于求图的多源最短路径(多源最短路径:图的所有顶...

Hacker_ZhiDian
2017/02/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

小白带你认识netty(三)之NioEventLoop的线程(或者reactor线程)启动(一)

在第一章中,我们看关于NioEventLoopGroup的初始化,我们知道了NioEventLoopGroup对象中有一组EventLoop数组,并且数组中的每个EventLoop对象都对应一个线程FastThreadLocalThread,那么这个...

天空小小
今天
3
0
PHP动态扩展Redis模块

查看已有模块 [root@test-a ~]# /usr/local/php/bin/php -m[PHP Modules]bz2Core...zlib[Zend Modules] 下载包,解压,生成configure文件 [root@test-a ~]# cd /usr/local/src/[ro......

野雪球
今天
3
0
在Ignite中使用线性回归算法

在本系列前面的文章中,简单介绍了一下Ignite的机器学习网格,下面会趁热打铁,结合一些示例,深入介绍Ignite支持的一些机器学习算法。 如果要找合适的数据集,会发现可用的有很多,但是对于...

李玉珏
今天
5
0
Mybatis应用学习——简单使用示例

1. 传统JDBC程序中存在的问题 1. 一个简单的JDBC程序示例: public class JDBCDemo {public static void main(String[] args) {Connection con=null;PreparedStatement statemen...

江左煤郎
今天
4
0
使用JavaScript编写iOS应用业务逻辑

JSAUIKitCocoa使你可以使用JavaScript编写对性能要求不高但可能变动性很大的iOS应用的业务逻辑部分,View组件、需要多线程支持的Model等则直接使用原生对象。 编写方式与React Native相似,但...

neal01
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部