弗洛伊德算法求两点见最短距离 两点间最短路径算法

弗洛伊德算法求两点见最短距离 两点间最短路径算法

Floyd-Warshall算法(FloydWarshallalgorithm)是解决任意两点间的最短路径的一种算法,可以正确处理带权有向图或负权的最短路径问题

解决此问题有两种方法:
其一是分别以图中每个顶点为源点共调用n次算法;
其二是采用Floyd算法。

两种算法的时间复杂度均为O(n3),但后者形式上比较简单。

Floyd算法的基本思想:
(1)利用二维数组dist[i][j]记录当前vi到vj的最短路径长度,数组dist的初值等于图的带权邻接矩阵;

(2)集合S记录当前允许的中间顶点,初值S=Φ;

(3)依次向S中加入v0 ,v1…vn-1,每加入一个顶点,对dist[i][j]进行一次修正:设S={v0,v1… vk-1},加入vk,则dist(k)[i][j] = min{dist(k-1)[i][j],dist(k-1)[i][k]+dist(k-1)[k][j]}。
dist(k)[i][j]的含义:允许中间顶点的序号最大为k时从vi到vj的最短路径长度。

dist(n-1)[i][j]就是vi到vj的最短路径长度。

最短距离有三种情况:
1、两点的直达距离最短。(如下图)
2、两点间只通过一个中间点而距离最短。(图)
3、两点间用通过两各以上的顶点而距离最短。(图)

对于第一种情况:

在初始化的时候就已经找出来了且以后也不会更改到。

对于第二种情况:
弗洛伊德算法的基本操作就是对于每一对顶点,遍历所有其它顶点,看看可否通过这一个顶点让这对顶点距离更短

对于第三种情况:
如下图的五边形,可先找一点(比如x,使=2),就变成了四边形问题,再找一点(比如y,使=2) ,可变成三角形问题了(v,u,w),也就变成第二种情况了,由此对于n边形也可以一步步转化成四边形三角形问题。(这里面不用担心哪个点要先找哪个点要后找,因为找了任一个点都可以使其变成(n-1)边形的问题)。

Java代码

  

爱华网本文地址 » http://www.413yy.cn/a/25101015/260239.html

更多阅读

弗洛伊德力比多理论解析自我(精神分析学) 弗洛伊德梦的解析

英文叫libido,力比多客体,在概念上讲,应该都是一样的。指那些在性方面能引起心理活动的事物,意识,观念。或指能使人倾注原欲于之的事物,意识,观念。等等。用弗洛伊德精神分析理论分析的中国现当代文学作品,太多了,基本上每一个文学文本都可进

心理悬疑小说:弗洛伊德禁地

心理悬疑小说:弗洛伊德禁地[总目录]神秘惊悚的心理克隆计划,带出一段残酷的寻父旅程,解开所有密码的孩子,却是被父亲遗弃的实验品,当人性和欲望纠缠在一起,死亡和遗忘让一切回归起点。男孩的父亲,连同汽车在空旷的雪地上平空消失;女孩的父亲

英国卢西恩·弗洛伊德油画作品 弗洛伊德油画

卢西恩。佛洛伊德生于1922年,是著名心理学家西蒙。佛洛伊德的孙子。和所有的维也纳人一样,他与生俱来的怀疑、孤独和好奇精神常常使自己不安,对世界的感知也就保持了一种特殊的知觉能力。1933年他移居英国并成为画家后,这种知觉能力也就

弗洛伊德精神分析人格理论 精神分析人格理论

奥地利精神病医生弗洛伊德是精神分析学派的创始人,弗洛伊德人格理论的内容主要包括人格结构、人格发展动力、人格适应及人格发展阶段。弗洛伊德人格性欲发展阶段因为这个理论中人格阶段的划分方式是根据性兴奋的不同部位所提出的。整

弗洛伊德.梅威瑟:家庭暴力阴影下成长起来的金钱梅

本帖最后由 看不下去 于 2013-11-17 14:50 编辑BY JOHNSON SNOWDEN弗洛伊德小梅威瑟发现自己正盯着一只猎枪枪管。 泪水以及随之而来的大哭预示着接下来他密西根州大急流城的家里将遭遇不幸。而那时候小梅还没满两岁。据滚石说,潜在

声明:《弗洛伊德算法求两点见最短距离 两点间最短路径算法》为网友苍景流年分享!如侵犯到您的合法权益请联系我们删除