求两个顶点间的最短距离,直觉是这样的问题可以用尝试和枚举的办法来求解,这显然可行,但是我们可以换个方式来看待这个问题,比如, 可以这样描述,“在给定的点集(编号为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算法的更多相关文章
-
最短路径之Floyd算法
Floyd算法又称弗洛伊德算法,也叫做Floyd's algorithm,Roy–Warshall algorithm,Roy–Floyd algorithm, WFI algorithm. Floy ...
-
最短路径—Dijkstra算法和Floyd算法
原文链接:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html 最后边附有我根据文中Dijkstra算法的描述使用jav ...
-
最短路径问题——floyd算法
floyd算法和之前讲的bellman算法.dijkstra算法最大的不同在于它所处理的终于不再是单源问题了,floyd可以解决任何点到点之间的最短路径问题,个人觉得floyd是最简单最好用的一种算法 ...
-
floyd算法小结
floyd算法是被大家熟知的最短路算法之一,利用动态规划的思想,f[i][j]记录i到j之间的最短距离,时间复杂度为O(n^3),虽然时间复杂度较高,但是由于可以处理其他相似的问题,有着广泛的应用,这 ...
-
Uvaoj 10048 - Audiophobia(Floyd算法变形)
1 /* 题目大意: 从一个点到达另一个点有多条路径,求这多条路经中最大噪音值的最小值! . 思路:最多有100个点,然后又是多次查询,想都不用想,Floyd算法走起! */ #include< ...
-
Floyd算法(三)之 Java详解
前面分别通过C和C++实现了弗洛伊德算法,本文介绍弗洛伊德算法的Java实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3. 弗洛伊德算法的代码说明 4. 弗洛伊德算法的源码 转载请注明 ...
-
Floyd算法(二)之 C++详解
本章是弗洛伊德算法的C++实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3. 弗洛伊德算法的代码说明 4. 弗洛伊德算法的源码 转载请注明出处:http://www.cnblogs.c ...
-
Floyd算法(一)之 C语言详解
本章介绍弗洛伊德算法.和以往一样,本文会先对弗洛伊德算法的理论论知识进行介绍,然后给出C语言的实现.后续再分别给出C++和Java版本的实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3 ...
-
最短路径---Dijkstra/Floyd算法
1.Dijkstra算法基础: 算法过程比prim算法稍微多一点步骤,但思想确实巧妙也是贪心,目的是求某个源点到目的点的最短距离,总的来说dijkstra也就是求某个源点到目的点的最短路,求解的过程也 ...
-
最短路径(Floyd)算法
#include <stdio.h>#include <stdlib.h>/* Floyd算法 */#define VNUM 5#define MV 65536int P[VN ...
随机推荐
-
mongo快速翻页方法(转载)
翻阅数据是MongoDB最常见的操作之一.一个典型的场景是需要在你的用户界面中显示你的结果.如果你是批量处理的数据,同样重要的是要让你的分页策略正确,以便你的数据处理可以规模化. 接下来,让我们通过一 ...
-
两个C++对象是否相等,要程序员自己下定义,通常是覆盖==操作符
我曾经好多年对Java的==和equals的区别和联系搞不清楚,后来搞清楚了,笔记在这里: http://www.cnblogs.com/findumars/p/3240761.htmlhttp:// ...
-
nyoj 1185 最大最小值【线段树最大值最小值维护】
最大最小值 时间限制:1000 ms | 内存限制:65535 KB 难度:2 描述 给出N个整数,执行M次询问. 对于每次询问,首先输入三个整数C.L.R: 如果C等于1,输出第L个数到第R ...
-
Android 一个绚丽的loading动效分析与实现!
http://blog.csdn.net/tianjian4592/article/details/44538605 前两天我们这边的头儿给我说,有个 gif 动效很不错,可以考虑用来做项目里的loa ...
-
sencha touch datepicker/datepickerfield(时间选择控件)扩展
参考资料: https://market.sencha.com/extensions/datetimepicker 适用于2.4.1版本 uxPickerTime 使用方法参考:datepicker控 ...
-
web.config/app.config敏感数据加/解密的二种方法
一 建立虚拟目录 http://localhost/EncryptWebConfig,并添加web.config,其中包含数据库连接字符串: <connectionStrings> ...
-
音频 API 一览
iOS 和 OS X 平台都有一系列操作音频的 API,其中涵盖了从低到高的全部层级.随着时间的推移.平台的增长以及改变,不同 API 的数量可以说有着非常巨大的变化.本文对当前可以使用的 API 以 ...
-
深入浅出OAuth2.0授权
一.前言 说到OAuth,先来一段百度到的比较官方的解释: OAUTH协议为用户资源的授权提供了一个安全的.开放而又简易的标准.与以往的授权方式不同之处是OAUTH的授权不会使第三方触及到用户的帐号信 ...
-
为什么HashMap桶(链表)的长度超过8会转换成红黑树?
百度了一下,感觉能说清楚的并不多,所以在此记录一下. 首先说一说转换为红黑树的必要性: 红黑树的插入.删除和遍历的最坏时间复杂度都是log(n), 因此,意外的情况或者恶意使用下导致hashCode( ...
-
Machine Learing 入门 —— 开门第0篇
一.最近懒了 7月没怎么写博客,倒是一直在学Machine Learning的入门知识,在这里给大家推荐一个不错的自学网站:https://www.coursera.org/ ,Andrew Ng是联 ...