文档章节

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

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

© 著作权归作者所有

共有 人打赏支持
千面人
粉丝 13
博文 43
码字总数 22299
作品 0
杭州
高级程序员
理解Floyd-Warshall算法

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

桥头堡2015 ⋅ 2016/08/27 ⋅ 0

最短路径-Dijkstra算法和Floyd算法

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

pointerException ⋅ 2015/08/07 ⋅ 0

可视化的数据结构和算法

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

戴威 ⋅ 2011/05/12 ⋅ 5

最短路径算法

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

Hosee ⋅ 2016/01/14 ⋅ 0

Dijkstra算法--单源最短路径

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

Hacker_ZhiDian ⋅ 2017/02/07 ⋅ 0

Johnson 全源最短路径算法

前言 上一篇文章已经阐述了Floyd-Warshall算法,适用于存在负权重路径的稠密图。本文讲述的算法适用于稀疏图。 全源最短路径求解其实是单源最短路径的推广,求解单源最短路径的两种算法时间复...

某昆 ⋅ 2017/12/15 ⋅ 0

考研复试系列——第七节 最短路径

考研复试系列——第七节 最短路径 前言 Floyd算法 //经过1号节点for(i=1;i<=n;i++)//遍历二维数组{for(j=1;j<=n;j++){if(e[i][j] > e[i][1] + e[1][j])//判断经过节点1是否距离更短e[i][j] =...

cassiepython ⋅ 2017/03/06 ⋅ 0

加权有向图----多源最短路径问题(Floyd算法)

Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。 Floyd算法能够处理带负权重的边的有向图但不能包含负权重环。 算法的基本思想是:从起始顶点...

Superheros ⋅ 2017/12/24 ⋅ 0

Floyd-Warshall 全源最短路径算法

前言 全源最短路径是相对单源最短路径而言的,用于查找图中所有点对其它点的最短路径。 Floyd-Warshall算法适用于存在负权重但不存在负回路的图,稠密图,它的运行时间为O(n3)。 它的实质是动...

某昆 ⋅ 2017/12/15 ⋅ 0

[Week 1] Princeton Algorithm PartII WordNet

最近在coursera上学习Princeton大学的Algorithm PartII,这个系列的两门课是我见过最好的算法课。主讲Robert Sedgewick师承高德纳,声名远播,虽然年纪大了,但是讲课思路清晰,深入浅出。与...

lyy0905 ⋅ 2017/01/25 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Day 17 vim简介与一般模式介绍

vim简介 vi和Vim的最大区别就是编辑一个文件时vi不会显示颜色,而Vim会显示颜色。显示颜色更便于用户编辑,凄然功能没有太大的区别 使用 yum install -y vim-enhanced 安装 vim的三种常用模式...

杉下 ⋅ 52分钟前 ⋅ 0

【每天一个JQuery特效】根据可见状态确定是否显示或隐藏元素(3)

效果图示: 主要代码: <!DOCTYPE html><html><head><meta charset="UTF-8"><title>根据可见状态确定 是否显示或隐藏元素</title><script src="js/jquery-3.3.1.min.js" ty......

Rhymo-Wu ⋅ 今天 ⋅ 0

OSChina 周四乱弹 —— 初中我身体就已经垮了,不知道为什么

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @加油东溪少年 :下完这场雨 后弦 《下完这场雨》- 后弦 手机党少年们想听歌,请使劲儿戳(这里) @马丁的代码 :买了日本 日本果然赢了 翻了...

小小编辑 ⋅ 今天 ⋅ 12

浅谈springboot Web模式下的线程安全问题

我们在@RestController下,一般都是@AutoWired一些Service,由于这些Service都是单例,所以并不存在线程安全问题。 由于Controller本身是单例模式 (非线程安全的), 这意味着每个request过来,...

算法之名 ⋅ 今天 ⋅ 0

知乎Java数据结构

作者:匿名用户 链接:https://www.zhihu.com/question/35947829/answer/66113038 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 感觉知乎上嘲讽题主简...

颖伙虫 ⋅ 今天 ⋅ 0

Confluence 6 恢复一个站点有关使用站点导出为备份的说明

推荐使用生产备份策略。我们推荐你针对你的生产环境中使用的 Confluence 参考 Production Backup Strategy 页面中的内容进行备份和恢复(这个需要你备份你的数据库和 home 目录)。XML 导出备...

honeymose ⋅ 今天 ⋅ 0

JavaScript零基础入门——(九)JavaScript的函数

JavaScript零基础入门——(九)JavaScript的函数 欢迎回到我们的JavaScript零基础入门,上一节课我们了解了有关JS中数组的相关知识点,不知道大家有没有自己去敲一敲,消化一下?这一节课,...

JandenMa ⋅ 今天 ⋅ 0

火狐浏览器各版本下载及插件httprequest

各版本下载地址:http://ftp.mozilla.org/pub/mozilla.org//firefox/releases/ httprequest插件截至57版本可用

xiaoge2016 ⋅ 今天 ⋅ 0

Docker系列教程28-实战:使用Docker Compose运行ELK

原文:http://www.itmuch.com/docker/28-docker-compose-in-action-elk/,转载请说明出处。 ElasticSearch【存储】 Logtash【日志聚合器】 Kibana【界面】 答案: version: '2'services: ...

周立_ITMuch ⋅ 今天 ⋅ 0

使用快嘉sdkg极速搭建接口模拟系统

在具体项目研发过程中,一旦前后端双方约定好接口,前端和app同事就会希望后台同事可以尽快提供可供对接的接口方便调试,而对后台同事来说定好接口还仅是个开始、设计流程,实现业务逻辑,编...

fastjrun ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部