- 浏览: 604289 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理带权有向图或负权的最短路径问题
解决此问题有两种方法:其一是分别以图中每个顶点为源点共调用n次Dijkstrahttp://128kj.iteye.com/blog/1678532算法;其二是采用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的最短路径长度。
运行结果:
0 to 4,the cheapest path is:
[0, 3, 4]
40
最短距离有三种情况:
1、两点的直达距离最短。(如下图<v,x>)
2、两点间只通过一个中间点而距离最短。(图<v,u>)
3、两点间用通过两各以上的顶点而距离最短。(图<v,w>)
对于第一种情况:在初始化的时候就已经找出来了且以后也不会更改到。
对于第二种情况:弗洛伊德算法的基本操作就是对于每一对顶点,遍历所有其它顶点,看看可否通过这一个顶点让这对顶点距离更短
对于第三种情况:如下图的五边形,可先找一点(比如x,使<v,u>=2),就变成了四边形问题,再找一点(比如y,使<u,w>=2),可变成三角形问题了(v,u,w),也就变成第二种情况了,由此对于n边形也可以一步步转化成四边形三角形问题。(这里面不用担心哪个点要先找哪个点要后找,因为找了任一个点都可以使其变成(n-1)边形的问题)。
下载源码:
解决此问题有两种方法:其一是分别以图中每个顶点为源点共调用n次Dijkstrahttp://128kj.iteye.com/blog/1678532算法;其二是采用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的最短路径长度。
import java.util.ArrayList; import java.util.List; public class FloydInGraph { private static int INF=Integer.MAX_VALUE; //dist[i][j]=INF<==>顶点i和j之间没有边 private int[][] dist; //顶点i 到 j的最短路径长度,初值是i到j的边的权重 private int[][] path; private List<Integer> result=new ArrayList<Integer>(); public static void main(String[] args) { FloydInGraph graph=new FloydInGraph(5); int[][] matrix={ {INF,30,INF,10,50}, {INF,INF,60,INF,INF}, {INF,INF,INF,INF,INF}, {INF,INF,INF,INF,30}, {50,INF,40,INF,INF}, }; int begin=0; int end=4; graph.findCheapestPath(begin,end,matrix); List<Integer> list=graph.result; System.out.println(begin+" to "+end+",the cheapest path is:"); System.out.println(list.toString()); System.out.println(graph.dist[begin][end]); } public void findCheapestPath(int begin,int end,int[][] matrix){ floyd(matrix); result.add(begin); findPath(begin,end); result.add(end); } public void findPath(int i,int j){ int k=path[i][j]; if(k==-1)return; findPath(i,k); //递归 result.add(k); findPath(k,j); } public void floyd(int[][] matrix){ int size=matrix.length; //initialize dist and path for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ path[i][j]=-1; dist[i][j]=matrix[i][j]; } } for(int k=0;k<size;k++){ for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ if(dist[i][k]!=INF&& dist[k][j]!=INF&& dist[i][k]+dist[k][j]<dist[i][j]){ dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=k; } } } } } public FloydInGraph(int size){ //构造函数 this.path=new int[size][size]; this.dist=new int[size][size]; } }
运行结果:
0 to 4,the cheapest path is:
[0, 3, 4]
40
最短距离有三种情况:
1、两点的直达距离最短。(如下图<v,x>)
2、两点间只通过一个中间点而距离最短。(图<v,u>)
3、两点间用通过两各以上的顶点而距离最短。(图<v,w>)
对于第一种情况:在初始化的时候就已经找出来了且以后也不会更改到。
对于第二种情况:弗洛伊德算法的基本操作就是对于每一对顶点,遍历所有其它顶点,看看可否通过这一个顶点让这对顶点距离更短
对于第三种情况:如下图的五边形,可先找一点(比如x,使<v,u>=2),就变成了四边形问题,再找一点(比如y,使<u,w>=2),可变成三角形问题了(v,u,w),也就变成第二种情况了,由此对于n边形也可以一步步转化成四边形三角形问题。(这里面不用担心哪个点要先找哪个点要后找,因为找了任一个点都可以使其变成(n-1)边形的问题)。
下载源码:
发表评论
-
龙抬头
2014-11-10 15:06 632... -
求推箱子的最小步数(java)
2014-05-06 08:32 3776题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1679POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3062POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
图的练习题(有解答)
2012-12-27 22:23 26581. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2463//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1922经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2797POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3337回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1848一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9626如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1865题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1364Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1943很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5941Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1456Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1399题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1582拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1883无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ...
相关推荐
**标题与描述解析** 标题“floyd_floyd最短路径...综上,Floyd算法是一种强大的图论工具,用于找出所有节点对间的最短路径,其核心操作在于迭代地更新邻接矩阵。这个算法的效率和简洁性使其在各种问题中得到广泛应用。
弗罗伊德算法,也称为弗洛伊德-沃普斯德算法(Floyd-Warshall Algorithm),是一种解决图论中的最短路径问题的有效方法。它由美国计算机科学家罗伯特·弗罗伊德和理查德·沃普斯德在20世纪60年代提出。这个算法的...
总的来说,解决“任意两点最短路径”问题需要深厚的图论基础,熟练的算法实现能力,以及对数据结构和编程的深入理解。在实际应用中,还需要考虑如何高效地存储和检索图数据,以及如何适应动态变化的环境。
在给定的标题"求一些点的任意两点最短路径"和描述中,我们可以理解这是一道大学C++课程的编程题目,目的是编写一个程序来计算计量地理学中的任意两点之间的最短路径。 在计量地理学中,最短路径问题可能涉及到地图...
弗洛伊德算法,全称为弗洛伊德-沃瑟曼算法(Floyd-Warshall Algorithm),是图论中一种著名的解决所有顶点对之间最短路径问题的算法。它适用于有向图或无向图,能找出图中任意两个顶点之间的最短路径,并且在计算...
它能够计算任意两点间的最短路径,包括经过其他顶点的间接路径。该算法适用于有向图和无向图,包括带权重的边,但边权重不可以为负值。 算法的基本思想是动态规划。算法首先初始化一个距离矩阵,其中的距离值表示图...
对于任意两点间的最短路径,可以使用弗洛伊德算法(Floyd-Warshall Algorithm)。这个算法通过动态规划方法,逐步计算所有顶点对之间的最短路径。它通过考虑每一对顶点作为中间节点,逐步完善所有可能的路径,最终...
在计算机科学领域,寻找图中两点间的最短路径是一个常见的问题,这在许多应用中都有重要作用,例如网络路由、交通规划等。本文将详细介绍两种最常用的算法:Floyd(弗洛伊德)算法和Dijkstra(迪克斯特拉)算法,...
2. **任意两点之间的最短路径**:即全对最短路径问题。 3. **从一个指定的起点到一个指定的终点的最短路径**。 4. **从一组指定的起点到一组指定的终点的最短路径**。 5. **次短路径或较短路径**。 #### 二、最短...
Floyd算法是一种动态规划方法,用于求解有向图中任意两点间的最短路径。它允许图中存在负权重(但不能有负权回路)。算法步骤如下: - 初始化:构建一个二维距离矩阵`dist`,表示每对顶点之间的初始距离,如果两点...
本文将详细讨论一种经典算法——弗洛伊德算法(Floyd-Warshall Algorithm),它被广泛用于找出图中任意两个节点之间的最短路径,尤其是在存在负权边的情况下。 弗洛伊德算法的核心思想是动态规划,通过迭代的方式...
"图算法-所有点对最短路径"这个主题关注的是如何找到一个赋权有向图中任意两个节点之间的最短路径。这里我们主要讨论的是Floyd算法,也称为Floyd-Warshall算法,它是一种用于解决所有点对最短路径问题的有效方法。 ...
### Floyd算法原理与Java实现详解 #### 一、Floyd算法概述 Floyd算法,也称为弗洛伊德算法或插点法,是一种用于解决有向...通过动态规划的思想,逐步构建出完整的最短路径矩阵,最终实现了任意两点间的最短路径计算。
弗洛伊德算法的核心思想是动态规划,它通过逐步考虑所有可能的中间节点来找到任意两点之间的最短路径。算法步骤如下: 1. 初始化:首先,根据给定的邻接矩阵初始化所有的最短路径。对于每个顶点i到自身的路径,距离...
通过n次试探,最终得到任意两点间的最短路径。Floyd算法的伪代码较为简单,但详细实现涉及到邻接矩阵的更新以及多层循环的构建。 总结而言,最短路径问题在计算机科学领域中非常重要,尤其是在网络设计、导航系统...
3. 实现Floyd算法核心逻辑:通过三重循环遍历所有顶点,对于任意的顶点对(i, j),尝试通过中间顶点k来更新它们之间的最短路径。如果通过顶点k的路径比之前记录的路径更短,则更新该路径。核心公式为:Dis[i][j] = ...
与上述算法不同的是,弗洛伊德算法不仅仅局限于某个特定源点到其他顶点的最短路径,而是能够求出任意两点间的最短路径。 ##### 3.2 核心步骤 弗洛伊德算法的核心步骤如下: 1. **初始化**:建立一个二维数组 `d`...
弗洛伊德算法可以解决任意两点间的最短路径问题,而不仅仅是单源最短路径问题。它通过不断改进中间顶点来逐渐优化每一对顶点之间的路径,适用于有向图和无向图,但不适用于含负权重环的图。 #### 算法步骤 1. **...
该算法主要用于解决图论中的最短路径问题,即在给定加权无向图中找出任意两个顶点之间的最短路径。它采用动态规划的思想,通过逐步增加中间节点来更新最短路径。 算法的核心在于逐步考虑所有可能的中转节点,从不...