文档章节

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

千面人
 千面人
发布于 2016/12/08 21:11
字数 292
阅读 13
收藏 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 

© 著作权归作者所有

共有 人打赏支持
千面人
粉丝 17
博文 48
码字总数 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
最短路径算法

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

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

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

戴威
2011/05/12
16
0
可视化的数据结构和算法

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

戴威
2011/05/12
962
5

没有更多内容

加载失败,请刷新页面

加载更多

MySQL学习笔记之二

数据库的操作总结就是:增删改查(CURD),今天记录一下基础的检索查询工作。 检索MySQL 1.查询表中所有的记录 mysql> select * from apps;+----+------------+-----------------------+------...

凌宇之蓝
26分钟前
0
0
PaddlePaddle-GitHub的正确打开姿势

GitHub是一个面向开源及私有软件项目的托管平台、也是项目版本管理工具,会使用它是程序员入门的必备技能。PaddlePaddle也不例外,所有的源码及项目进展都在GitHub上开源公布。但对于刚入门写...

深度学习之路
26分钟前
1
0
最强NLP模型BERT可视化学习

摘要: 最强NLP模型谷歌BERT狂破11项纪录,全面超越人类,本文通过可视化带你直观了解它。 2018年是自然语言处理(Natural Language Processing, NLP)领域的转折点,一系列深度学习模型在智...

阿里云官方博客
33分钟前
1
0
导出功能

public void downloadD(HttpServletRequest request, HttpServletResponse res,String contractName, String contractPath) throws IOException {// FileAttach fileAttach = fileA......

卖星星的小矮人
37分钟前
1
0
gradle 打包可执行jar包

group 'android.com'version '1.0-SNAPSHOT'apply plugin: 'java'sourceCompatibility = 1.8repositories { mavenCentral()}jar { manifest { attributes ('Main-......

zdglf
48分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部