floyd算法

时间:2022-09-03 14:41:59

求两个顶点间的最短距离,直觉是这样的问题可以用尝试和枚举的办法来求解,这显然可行,但是我们可以换个方式来看待这个问题,比如, 可以这样描述,“在给定的点集(编号为1~k,k=图中所有的顶点数量)中,i,j之间的最短路径长度"(称为p1), 基于这样一个描述我们可以对问题规模进行缩减得到另一个问题"在给定的点集(编号为1~k-1)中,i,j之间的最短路径长度"(称为p2),  可以再次缩减问题,即"在给定的点集(编号为1~k-2)中,i,j之间的最短路径长度", 照此类推,直到点集不能再缩减(只有i,j),我们便到达了一个终极子问题,如果我们总是可以用一个子问题的解,得到比该子问题多一个顶点的问题的解,那么可以想见,我们可以从终极子问题出发,逐步求解,直到得到母问题的解。下面我们尝试找到这两个点集相差一个的问题之间的关系,以p1和p2的关系为例,用更加简洁的式子来表示问题,p1 表示为ShortestPath(i,j,k), p2表示为ShortestPath(i,j,k-1), p1比p2多了一个编号为k的顶点,那么会有两种可能:

1. 虽然多了点集中多了一个编号为k的顶点,但ShortestPath(i,j,k) = ShortestPath(i,j,k-1), 也就是说并没有因为加入了新的顶点k而出现新的最短路径

2. 因为加入了顶点k ShortestPath(i,j,k)有一条新的最短路径,要短于 ShortestPath(i,j,k-1), 我们也可以得出这条新的最短路径必然经过顶点k(如果不经过k,那么最短路径不可能变短),这时最短路径可以表示为ShortestPath(i,k,k-1),+ShortestPath(k,j,k-1)。

基于以上两种可能,继续得到ShortestPath(i,j,k) = min(ShortestPath(i,j,k-1),ShortestPath(i,k,k-1),+ShortestPath(k,j,k-1))

floyd算法的更多相关文章

  1. 最短路径之Floyd算法

    Floyd算法又称弗洛伊德算法,也叫做Floyd's algorithm,Roy–Warshall algorithm,Roy–Floyd algorithm, WFI algorithm. Floy ...

  2. 最短路径—Dijkstra算法和Floyd算法

    原文链接:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html 最后边附有我根据文中Dijkstra算法的描述使用jav ...

  3. 最短路径问题——floyd算法

    floyd算法和之前讲的bellman算法.dijkstra算法最大的不同在于它所处理的终于不再是单源问题了,floyd可以解决任何点到点之间的最短路径问题,个人觉得floyd是最简单最好用的一种算法 ...

  4. floyd算法小结

    floyd算法是被大家熟知的最短路算法之一,利用动态规划的思想,f[i][j]记录i到j之间的最短距离,时间复杂度为O(n^3),虽然时间复杂度较高,但是由于可以处理其他相似的问题,有着广泛的应用,这 ...

  5. Uvaoj 10048 - Audiophobia(Floyd算法变形)

    1 /* 题目大意: 从一个点到达另一个点有多条路径,求这多条路经中最大噪音值的最小值! . 思路:最多有100个点,然后又是多次查询,想都不用想,Floyd算法走起! */ #include< ...

  6. Floyd算法&lpar;三&rpar;之 Java详解

    前面分别通过C和C++实现了弗洛伊德算法,本文介绍弗洛伊德算法的Java实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3. 弗洛伊德算法的代码说明 4. 弗洛伊德算法的源码 转载请注明 ...

  7. Floyd算法&lpar;二&rpar;之 C&plus;&plus;详解

    本章是弗洛伊德算法的C++实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3. 弗洛伊德算法的代码说明 4. 弗洛伊德算法的源码 转载请注明出处:http://www.cnblogs.c ...

  8. Floyd算法&lpar;一&rpar;之 C语言详解

    本章介绍弗洛伊德算法.和以往一样,本文会先对弗洛伊德算法的理论论知识进行介绍,然后给出C语言的实现.后续再分别给出C++和Java版本的实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3 ...

  9. 最短路径---Dijkstra&sol;Floyd算法

    1.Dijkstra算法基础: 算法过程比prim算法稍微多一点步骤,但思想确实巧妙也是贪心,目的是求某个源点到目的点的最短距离,总的来说dijkstra也就是求某个源点到目的点的最短路,求解的过程也 ...

  10. 最短路径&lpar;Floyd&rpar;算法

    #include <stdio.h>#include <stdlib.h>/* Floyd算法 */#define VNUM 5#define MV 65536int P[VN ...

随机推荐

  1. mongo快速翻页方法(转载)

    翻阅数据是MongoDB最常见的操作之一.一个典型的场景是需要在你的用户界面中显示你的结果.如果你是批量处理的数据,同样重要的是要让你的分页策略正确,以便你的数据处理可以规模化. 接下来,让我们通过一 ...

  2. 两个C&plus;&plus;对象是否相等,要程序员自己下定义,通常是覆盖&equals;&equals;操作符

    我曾经好多年对Java的==和equals的区别和联系搞不清楚,后来搞清楚了,笔记在这里: http://www.cnblogs.com/findumars/p/3240761.htmlhttp:// ...

  3. nyoj 1185 最大最小值【线段树最大值最小值维护】

    最大最小值 时间限制:1000 ms  |  内存限制:65535 KB 难度:2   描述 给出N个整数,执行M次询问. 对于每次询问,首先输入三个整数C.L.R: 如果C等于1,输出第L个数到第R ...

  4. Android 一个绚丽的loading动效分析与实现!

    http://blog.csdn.net/tianjian4592/article/details/44538605 前两天我们这边的头儿给我说,有个 gif 动效很不错,可以考虑用来做项目里的loa ...

  5. sencha touch datepicker&sol;datepickerfield&lpar;时间选择控件&rpar;扩展

    参考资料: https://market.sencha.com/extensions/datetimepicker 适用于2.4.1版本 uxPickerTime 使用方法参考:datepicker控 ...

  6. web&period;config&sol;app&period;config敏感数据加&sol;解密的二种方法

    一 建立虚拟目录  http://localhost/EncryptWebConfig,并添加web.config,其中包含数据库连接字符串: <connectionStrings>    ...

  7. 音频 API 一览

    iOS 和 OS X 平台都有一系列操作音频的 API,其中涵盖了从低到高的全部层级.随着时间的推移.平台的增长以及改变,不同 API 的数量可以说有着非常巨大的变化.本文对当前可以使用的 API 以 ...

  8. 深入浅出OAuth2&period;0授权

    一.前言 说到OAuth,先来一段百度到的比较官方的解释: OAUTH协议为用户资源的授权提供了一个安全的.开放而又简易的标准.与以往的授权方式不同之处是OAUTH的授权不会使第三方触及到用户的帐号信 ...

  9. 为什么HashMap桶&lpar;链表&rpar;的长度超过8会转换成红黑树?

    百度了一下,感觉能说清楚的并不多,所以在此记录一下. 首先说一说转换为红黑树的必要性: 红黑树的插入.删除和遍历的最坏时间复杂度都是log(n), 因此,意外的情况或者恶意使用下导致hashCode( ...

  10. Machine Learing 入门 —— 开门第0篇

    一.最近懒了 7月没怎么写博客,倒是一直在学Machine Learning的入门知识,在这里给大家推荐一个不错的自学网站:https://www.coursera.org/ ,Andrew Ng是联 ...