- 浏览: 583581 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。
一.最短路径的最优子结构性质
该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。
假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。
二.Dijkstra算法
Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止。
对于下图:
运行结果:
从0出发到0的最短路径为:0-->0
从0出发到1的最短路径为:0-->1
从0出发到2的最短路径为:0-->3-->2
从0出发到3的最短路径为:0-->3
从0出发到4的最短路径为:0-->3-->2-->4
=====================================
从0出 发到0的最短距离为:0
从0出 发到1的最短距离为:10
从0出 发到2的最短距离为:50
从0出 发到3的最短距离为:30
从0出 发到4的最短距离为:60
下载源码:
一.最短路径的最优子结构性质
该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。
假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。
二.Dijkstra算法
Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止。
public class Dijkstra { static int M=10000;(此路不通) public static void main(String[] args) { // TODO Auto-generated method stub int[][] weight1 = {//邻接矩阵 {0,3,2000,7,M}, {3,0,4,2,M}, {M,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][] weight2 = { {0,10,M,30,100}, {M,0,50,M,M}, {M,M,0,M,10}, {M,M,20,0,60}, {M,M,M,M,0} }; int start=0; int[] shortPath = Dijsktra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("从"+start+"出发到"+i+"的最短距离为:"+shortPath[i]); } public static int[] Dijsktra(int[][] weight,int start){ //接受一个有向图的权重矩阵,和一个起点编号start(从0编号,顶点存在数组中) //返回一个int[] 数组,表示从start到它的最短路径长度 int n = weight.length; //顶点个数 int[] shortPath = new int[n]; //存放从start到其他各点的最短路径 String[] path=new String[n]; //存放从start到其他各点的最短路径的字符串表示 for(int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] visited = new int[n]; //标记当前该顶点的最短路径是否已经求出,1表示已求出 //初始化,第一个顶点求出 shortPath[start] = 0; visited[start] = 1; for(int count = 1;count <= n - 1;count++) //要加入n-1个顶点 { int k = -1; //选出一个距离初始顶点start最近的未标记顶点 int dmin = Integer.MAX_VALUE; for(int i = 0;i < n;i++) { if(visited[i] == 0 && weight[start][i] < dmin) { dmin = weight[start][i]; k = i; } } // System.out.println("k="+k); //将新选出的顶点标记为已求出最短路径,且到start的最短路径就是dmin shortPath[k] = dmin; visited[k] = 1; //以k为中间点,修正从start到未访问各点的距离 for(int i = 0;i < n;i++) { if(visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]){ weight[start][i] = weight[start][k] + weight[k][i]; path[i]=path[k]+"-->"+i; } } } for(int i=0;i<n;i++) System.out.println("从"+start+"出发到"+i+"的最短路径为:"+path[i]); System.out.println("====================================="); return shortPath; } }
对于下图:
运行结果:
从0出发到0的最短路径为:0-->0
从0出发到1的最短路径为:0-->1
从0出发到2的最短路径为:0-->3-->2
从0出发到3的最短路径为:0-->3
从0出发到4的最短路径为:0-->3-->2-->4
=====================================
从0出 发到0的最短距离为:0
从0出 发到1的最短距离为:10
从0出 发到2的最短距离为:50
从0出 发到3的最短距离为:30
从0出 发到4的最短距离为:60
下载源码:
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1525POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
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个点的无向图,求一个最小环(各 ... -
深度优先搜索输出有向图中的所有环(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无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 4963prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5354为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6218Floyd-Warshall算法(Floyd-Warsha ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5467当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ... -
最小生成树:Kruskal(克鲁斯卡尔)算法实现(java)
2012-09-01 20:50 2589算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
java算法分析与设计之单源最短路径(Dijkstra算法)源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络...
java单源最短路径(贪心算法) public class TheShortestWay { static int MAX_SIZE = 6; public static void dijkstra(int v, float[][] a, float[] dist, int[] prev) { int n = dist.length - 1; if (v ||...
由Dijkstra贪心算法实现,设置顶点集合实现贪心扩充直到找到源点到所有顶点的路径长度;用dist数组记录当前从源到顶点的最短特殊路径长度
最短路径算法java 单源点最短路径Dijkstra算法的JAVA实现
主要为大家详细介绍了java使用Dijkstra算法实现单源最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
NULL 博文链接:https://tianyalinfeng.iteye.com/blog/1579525
Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的...
•实现了Dijkstra的“单源最短路径”算法,以查找和打印无向图中任意两个给定节点之间的最短路径 •通过使用斐波那契堆来存储该图,优化了算法的运行时复杂度 第2部分:路由方案: •对于网络中的每个路由器,借助...
数据结构课程实践:1. 问题描述: 以顶点表示校平面图中各景点,要有景点名称、代号、简介等信息;以边表示路径,存放路径长度等...(2)解决单源点最短路径问题;(3)任意两个景点之间的最短路径。 我用java实现的
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业...
Dijkstra算法通过计算起始顶点到其他顶点的最短路径来解决单源最短路径问题。在示例代码中,我们使用数组distance来记录起始顶点到其他顶点的最短距离。 首先,我们初始化所有顶点的距离为无穷大(用Integer.MAX_...
Thorup发现了第一个确定性算法,用于解决线性时间和空间中具有正整数权重的无向图的经典单源最短路径问题。 该算法需要一个层次化的存储桶结构来标识必须访问顶点的顺序,而又不会破坏该时间范围,从而避免了...
一个简单的Java库,用于解决图形单源最短路径问题,这在数学或算法难题中很常见。 包括的示例应用程序。 基本用法 Dijkstra算法的主要代码在spdijklib模块内。 客户端应为ProblemState,ProblemStateFactory和...
迪杰斯特拉算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都...
我邀请您下载文件 Dijkstra-Maze-Game.jar 并尝试一下。 脚步: 1 / 加载一个已保存的迷宫或创建一个新迷宫。 2 / 键入“E”(空)或“W”(墙)以移除或设置实心块来构建地图。 3 / 通过点击选择一个方块来...
该项目旨在测量最著名的单源最短路径算法之一,Dijkstra 最短路径算法的不同实现的性能。 我正在考虑使用现有的斐波那契堆的开源实现的具有二元堆和优先级队列的简单优先队列和斐波那契堆类型实现。 我在这个实验中...
单源最短路径(Dijkstra) 全源最短路径(Floyd Warshall) Prim 的 MST 克鲁斯卡尔的 MST 拓扑排序(例如用于确定多模块项目中的项目构建顺序) 约翰逊算法 图中的连接点 图中的桥梁 检测图中的循环 11.a Using BFS...
实验五:最短路径算法一、实验目的(1)理解路径松驰技术的思想(2)掌握迪杰斯特拉算法(Dijkstra)的基本思想二、实验内容实现单源最短路经的迪杰斯特拉算法
·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地将注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...