- 浏览: 583557 次
- 来自: ...
文章分类
最新评论
-
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 548... -
求推箱子的最小步数(java)
2014-05-06 08:32 3656题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1524POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2979POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
图的练习题(有解答)
2012-12-27 22:23 26111. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2404//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1838经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2740POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3110回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1774一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9549如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1776题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1299Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1864很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5817Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1398Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1350题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1531拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3983一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1783无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ...
相关推荐
使用floyd warshall算法求图中任意两点间最短路径 graph shortest path
用C++ 语言编写 用Floyd算法求有向图中任意两点间的最短路径 由用户输入顶点和有向边的信息
用邻接矩阵来存储图,Floyed算法求任意两点间的最短路径并输出,广度优先遍历,深度优先遍历
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
算法思想:将各收费站及其...基于以上分析:车辆从任意A进站从任意B出站的收费问题就演化成求加权图中任意两点间最短路径的问题(前提:过路费按最短路径收取),采用floyd算法很容易实现求任意两点间最短路径的问题
该程序是我写的博客“一起talk C栗子吧(第五十五回:C语言实例--图的最短路径三)”的配套程序,共享给大家使用
求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
floyd算法,求最短路径的权值,java实现的
floyd计算最短路径,只需要更改邻接矩阵
Floyd算法是经典的最短路径算法之一,应用广泛,可以求解多对多和一对一的最短路;
Floyd算法求任意两点之间的路径(matlab程序)
对同一场景分别进行dijkstra算法求指定节点间的最短路径,floyd求任意端间最短路径。 报告中含C++代码
含有各种障碍物的,水平面两点间最短的距离算法。就相当于计算你从一个地方走到另一个地方,最短的路径。 注意:不是图论!不是节点!不是Dijkstra!不是Floyd!
Floyd-Warshall算法,又叫Floyd算法,用于求每对顶点之间最短路径
该课件采用C++面向对象思想,对最短路径中的弗洛伊德算法进行完美演示,开发工具VC6.0,对于初学数据结构的学生比较合适。
通过floyd算法实现任意两个学校间最短路径(有的学校有直接公交,有的学校之间需要转)
最短路径算法 floyd
构造邻接矩阵,利用Floyd算法求最短路径。课程设计~~~
要求对任意的顶点有序对(v,w)找出从顶点v到顶点w的最短路径长度。这个问题就称为带权有向图的所有顶点对之间的最短路径问题。解决这个问题的一个办法是,每次以一个顶点为源,重复执行Dijkstra算法n法。这样,就...