文档章节

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

千面人
 千面人
发布于 2016/12/08 21:11
字数 292
阅读 8
收藏 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
博文 47
码字总数 24904
作品 0
杭州
高级程序员
理解Floyd-Warshall算法

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

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

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

pointerException
2015/08/07
0
0
可视化的数据结构和算法

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

戴威
2011/05/12
789
5
最短路径算法

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

Hosee
2016/01/14
2.2K
0
Dijkstra算法--单源最短路径

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

Hacker_ZhiDian
2017/02/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

你为什么在Redis里读到了本应过期的数据

一个事故的故事 晚上睡的正香突然被电话吵醒,对面是开发焦急的声音:我们的程序在访问redis的时候读到了本应过期的key导致整个业务逻辑出了问题,需要马上解决。 看到这里你可能会想:这是不...

IT--小哥
今天
2
0
祝大家节日快乐,阖家幸福! centos GnuTLS 漏洞

yum update -y gnutls 修复了GnuTLS 漏洞。更新到最新 gnutls.x86_64 0:2.12.23-22.el6 版本

yizhichao
昨天
5
0
Scrapy 1.5.0之选择器

构造选择器 Scrapy选择器是通过文本(Text)或 TextResponse 对象构造的 Selector 类的实例。 它根据输入类型自动选择最佳的解析规则(XML vs HTML): >>> from scrapy.selector import Sele...

Eappo_Geng
昨天
4
0
Windows下Git多账号配置,同一电脑多个ssh-key的管理

Windows下Git多账号配置,同一电脑多个ssh-key的管理   这一篇文章是对上一篇文章《Git-TortoiseGit完整配置流程》的拓展,所以需要对上一篇文章有所了解,当然直接往下看也可以,其中也有...

morpheusWB
昨天
5
0
中秋快乐!!!

HiBlock
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部