- 浏览: 583865 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
Dijkstra算法是用来解决:确定起点的最短路径问题:即已知起始结点,求最短路径的问题。
它是常用的最短路径算法之一。最常用的路径算法有:Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。
缺陷:它一般用来解决正权,单源路径的最短路问题。
Dijkstra算法思想:设G=(V,E)是一个带权有向图,把图中顶点分为两部分,第一组我们就称它为蓝点集合(就是用来存放已经得到最短路径的点)用S表示,另一个我们称他们为红点集合(就是用来存放尚未找到最短路径的点)用U来表示。一开始蓝点集合中只有一个源点,以后任务就是不断动消灭红点,使他们成为蓝点集合的成员。在这个过程中每次策反一个红点成员。直到红点集合被消灭掉。
Dijkstra算法具体的步骤:
(1)初始时,S 只包含源点设为V0,U包含剩余的点。
(2)从U中选取一个距离V0最小的顶点Vi,将Vi加入到蓝点集合中。
(3)然后对U中的点到源点的距离进行一次更新就是以Vi为中间节点,修改U中各顶点到源点的距离。(修改动方法见下面程序)
(4)重复步骤2和3直到所有顶点都变成蓝点中动成员。
例: 某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。
Input
本题目包含多组数据,请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000),分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0~N-1编号。接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N),分别代表起点和终点。
Output
对于每组数据,请在一行里输出最短需要行走的距离。如果不存在从S到T的路线,就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
源码:
它是常用的最短路径算法之一。最常用的路径算法有:Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。
缺陷:它一般用来解决正权,单源路径的最短路问题。
Dijkstra算法思想:设G=(V,E)是一个带权有向图,把图中顶点分为两部分,第一组我们就称它为蓝点集合(就是用来存放已经得到最短路径的点)用S表示,另一个我们称他们为红点集合(就是用来存放尚未找到最短路径的点)用U来表示。一开始蓝点集合中只有一个源点,以后任务就是不断动消灭红点,使他们成为蓝点集合的成员。在这个过程中每次策反一个红点成员。直到红点集合被消灭掉。
Dijkstra算法具体的步骤:
(1)初始时,S 只包含源点设为V0,U包含剩余的点。
(2)从U中选取一个距离V0最小的顶点Vi,将Vi加入到蓝点集合中。
(3)然后对U中的点到源点的距离进行一次更新就是以Vi为中间节点,修改U中各顶点到源点的距离。(修改动方法见下面程序)
(4)重复步骤2和3直到所有顶点都变成蓝点中动成员。
例: 某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。
Input
本题目包含多组数据,请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000),分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0~N-1编号。接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N),分别代表起点和终点。
Output
对于每组数据,请在一行里输出最短需要行走的距离。如果不存在从S到T的路线,就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
//最短路径问题(dijkstra算法) import java.util.*; public class Main { private int n;// n个城市(n个点) private int[][] map;// 邻接矩阵 private int[] pre;// 记录前驱点、原点、终点 。若pre[i]=k,表示从s到i的最短路径中i的前一个点是k private int[] dist;// s到终点的最短路径 private int s, e;// 原点、终点 public Main(int n,int s,int e,int[][] map){ this.n=n; this.s=s; this.e=e; this.map=map; pre = new int[n]; dist = new int[n]; } public int[] getDist(){ return dist; } public void dijkstra() { boolean[] p = new boolean[n];// 记录此点是否属于集合S或U // 初始化 for (int i = 0; i < n; i++) { p[i] = false; if (i != s) { dist[i] = map[s][i]; pre[i] = s; } } dist[s] = 0;//原点到自己的距离为0; p[s] = true; //循环n-1次,求s点到其它点的最短路径 for(int i = 0;i<n-1;i++){ int min = Integer.MAX_VALUE;//s到某个点的最短路径 int k = -1; //在集合U中寻找从s到其路径最短的的点k for(int j = 0;j<n;j++){ if(!p[j] && dist[j]<min){ min = dist[j]; k = j; } } if(k==-1) return;//已经找完了,没有点可以扩展 p[k] = true;//将点k加入集合S //更新s到集合U中的点的路劲长度 for(int j = 0;j<n;j++){ if(!p[j] && map[k][j]!=Integer.MAX_VALUE && dist[j] > dist[k] +map[k][j]){ dist[j]=dist[k]+map[k][j]; pre[j] = k; } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n,m,s,e,u,v,w; int[][] map; while (sc.hasNext()) { n = sc.nextInt(); m = sc.nextInt(); map = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) map[i][j] = Integer.MAX_VALUE; while (m-- > 0) { u = sc.nextInt(); v = sc.nextInt(); w = sc.nextInt(); if (map[u][v] > w || map[v][u] > w) {//注意是双向的 map[u][v] = w; map[v][u] = w; } } s = sc.nextInt(); e = sc.nextInt(); Main ma=new Main(n,s,e,map); ma.dijkstra(); int[] dist=ma.getDist(); if (dist[e] == Integer.MAX_VALUE) System.out.println(-1); else System.out.println(dist[e]); } } }
源码:
- Main1874.zip (1.2 KB)
- 下载次数: 1
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1526POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26111. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2405//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1840经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
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 1777题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1865很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5819Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1398Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1352题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1532拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3986一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1785无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 4964prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5355为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6219Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9033单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5467当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ... -
最小生成树:Kruskal(克鲁斯卡尔)算法实现(java)
2012-09-01 20:50 2594算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
毕业设计:最短路径算法实现,Dijkstra算法,双向Dijkstra算法,CH算法,SILC算法 毕业设计:最短路径算法实现,Dijkstra算法,双向Dijkstra算法,CH算法,SILC算法 毕业设计:最短路径算法实现,Dijkstra算法,双向...
代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...
dijkstra算法C++实现的程序代码
Dijkstra算法算是贪⼼思想实现的,⾸先把起点到所有点的距离存下来找个最短的,然后松弛⼀次再找出最短的,所谓的松弛操作就是,遍历⼀遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,...
Dijkstra算法应用举例 Dijkstra算法应用举例Dijkstra算法应用举例 Dijkstra算法应用举例
本程序使用C语言实现了Dijkstra算法。程序中,定义好邻接矩阵,可以计算出任一节点到其他所有节点的最短路径,并打印路径与长度。其中对最短路径的存储是依据所得到的生成树,可以减少内存空间占用。
Dijkstra算法的应用, Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用
最短路径Dijkstra算法-最短路Dijkstra算法.rar 最短路径Dijkstra算法
能够实现 Dijkstra算法,内涵代码,运行即可实现
Dijkstra算法,Dijkstra算法详细讲解,Dijkstra算法详细讲解
文章研究了一种多核架构下基于OpenMP的Dijkstra并行算法,以Dijkstra算法为基础设计并行程序。对传统Dijkstra算法进行分析,明确优化方向,再利用OpenMP开发工具对并行程序进行优化调试。结果表明,文中算法易于操作...
Dijkstra算法的Matlab程序,用于求各点之间的最短路距离。该程序解决了一个有九个点的无向图中求任意两点之间最短路距离的例子。程序中的每一步都有详细说明。
Dijkstra算法求解格栅地图路径matlab代码
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
Dijkstra算法演示flash 一看就会Dijkstra算法~~
基于Dijkstra算法的路径规划算法,matlab代码
C语言版Dijkstra算法,有注释。 只是简单的Dijkstra算法的实现。
求解单源最短路径的Dijkstra算法模板,数学建模竞赛必备。
该模型是dijkstra算法求解路径规划问题,对该方面算法感兴趣的可以借鉴学习