- 浏览: 604157 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
题(HDU2544):
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?
Input
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。
接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
源码:
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?
Input
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。
接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
import java.util.Scanner; import java.util.Queue; import java.util.LinkedList; public class Main{ static final int INF = 99999999; private int map[][];//邻接矩阵 private int dist[];//最终存放从商店到各路口的最短距离 private boolean visit[];//visit[i]标记dist[i]是否已经求出。 private int n;//路口和道路数(顶点和边数) public Main(int n,int[][] map){ this.n=n; this.map=map; dist=new int[n+1]; } private void floyd(){ //Floyd算法 for(int k = 1; k <= n; k++) //k为中间点 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(map[i][k] + map[k][j] < map[i][j]){ map[i][j] = map[i][k] + map[k][j]; } System.out.println(map[1][n]); } private void dijk() { //Dijkstra算法 int next=0, MIN; visit=new boolean[n+1]; for(int i =1; i <= n; i++) dist[i] = INF; dist[1] = 0; for(int i = 1; i <= n; i++) { MIN = INF; for(int j = 1; j <= n; j++) if(!visit[j] && dist[j] <= MIN){ MIN = dist[j]; next=j; } if(MIN == INF) break; visit[next] = true; for(int j = 1; j <= n; j++) if(!visit[j] && dist[j] > dist[next] + map[next][j]) dist[j] = dist[next] + map[next][j]; } System.out.println(dist[n]); } private void spfa(){ //SPFA算法 int now; visit=new boolean[n+1]; for(int i = 1; i <= n; i++) dist[i] = INF; dist[1] = 0; Queue<Integer> Q=new LinkedList<Integer>(); Q.offer(1); visit[1] = true; while(!Q.isEmpty()){ now = Q.poll(); visit[now] = false; for(int i = 1; i <= n; i++){ if(dist[i] > dist[now] + map[now][i]){ dist[i] = dist[now] + map[now][i]; if(visit[i] == false) { Q.offer(i); visit[i] = true; } } } } System.out.println(dist[n]); } public static void main(String[] args){ Scanner in=new Scanner(System.in); while(in.hasNext()) { int n=in.nextInt();//图的顶点数 int m=in.nextInt();//边数 if(n==0&&m==0) break; int[][] map=new int[n+1][n+1]; for(int i = 1; i <= n; i++){//初始化 for(int j = 1; j <= n; j++){ if(i == j) map[i][j] = 0; else{ map[i][j] = map[j][i] = INF; } } } int vi, vj, cost; while(m-->0){//m条边的数据 vi=in.nextInt(); vj=in.nextInt(); cost=in.nextInt(); if(cost < map[vi][vj]){ map[vi][vj] = map[vj][vi] = cost; } } Main ma=new Main(n,map); // ma.floyd(); // ma.dijk(); ma.spfa(); } } }
源码:
- hdu2544.zip (1.1 KB)
- 下载次数: 13
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1679POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26581. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2463//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1919经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2797POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9625如图:求出有向图的所有环。 import java.uti ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1363Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1942很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5940Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1455Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1398题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1582拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1882无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 5051prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5427为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6304Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9127单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5543当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ... -
最小生成树:Kruskal(克鲁斯卡尔)算法实现(java)
2012-09-01 20:50 2635算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
Dijkstra算法是最常用的单源最短路径算法,适用于有权图。它的基本思想是从起点开始,逐步扩展最短路径树,直到覆盖所有顶点。C语言实现时,通常会用到优先队列(如二叉堆)来存储待处理的顶点,每次取出距离源点...
本文将深入探讨三个著名的最短路径算法:Floyd算法、Dijkstra算法和SPFA(Shortest Path Faster Algorithm)。这些算法广泛应用于图论和网络分析,特别是在路由选择、物流规划、社交网络分析等场景。 1. **Floyd...
下面将详细讲解三种常用的算法:迪杰斯特拉算法(Dijkstra算法)、弗洛伊德算法(Floyd算法)以及SPFA算法。 1. **迪杰斯特拉算法(Dijkstra算法)** Dijkstra算法是一种基于贪心策略的单源最短路径算法,适用于...
总的来说,单源最短路径问题的解决方法多种多样,每种算法都有其适用的场景和优缺点。理解这些算法的设计思想和性能特性对于优化实际问题的解决方案至关重要。在实际应用中,根据图的特性和需求,选择合适的算法能...
总的来说,不同的最短路径算法适用于不同的场景,选择哪种算法取决于图的性质(有向/无向、带负权重/无负权重、稠密/稀疏)、需求(单源/多源、所有路径/特定路径)以及对时间和空间效率的要求。理解这些算法的工作...
Dijkstra算法是一种解决单源最短路径问题的经典方法,它通过维护一个优先队列来逐步扩展最短路径。SPFA(Shortest Path Faster Algorithm)则是另一种基于Bellman-Ford算法的启发式策略,尽管在某些情况下效率更高,...
Dijkstra算法和Floyd-Warshall算法是解决单源最短路径问题的经典算法,它们并不属于贪心算法。 对于多点最短路径,一种可能的贪心策略是每次选择未访问且与当前路径代价最小的节点,但这通常无法保证得到全局最优解...
3. Floyd-Warshall算法:Floyd-Warshall算法是解决所有对最短路径问题的一种动态规划方法,它计算了图中任意两个节点间的最短路径。对于每个节点对,尝试通过所有中间节点作为路径的一部分来更新最短路径。 4. A*...
Dijkstra算法是一种广泛应用的单源最短路径算法,其原理基于贪心策略,每次选择当前未访问顶点中最短路径。Dijkstra算法的优点在于效率高,但无法处理负权边。为了解决负权边问题,论文引入了Bellman-Ford算法,该...
1. **迪杰斯特拉(Dijkstra)算法**:适用于无负权重边的图,能够高效地解决单源最短路径问题。 2. **贝尔曼-福特(Bellman-Ford)算法**:可以处理包含负权重边的图,并且能够检测是否存在负权回路。 3. **SPFA算法**:...
1. **Dijkstra算法**:由荷兰计算机科学家艾兹格·迪科斯彻发明,是最常用的单源最短路径算法。适用于有向或无向图,它通过维护一个优先队列来逐步确定从起点到其他顶点的最短路径。每次迭代,Dijkstra算法都会选择...
本压缩包文件“Shortest-path-template.rar_SPFA”提供了四种经典的最短路径算法模板:Dijkstra算法、Bellman-Ford算法、SPFA(Shortest Path Faster Algorithm)以及Floyd-Warshall算法。这些算法主要适用于加权有...
1. Dijkstra算法:这是一种贪心算法,用于寻找单源最短路径,适用于没有负权边的图。 2. A*算法:结合了Dijkstra算法和启发式搜索,能更高效地找到最短路径,通过预估目标距离来指导搜索。 3. SPFA(Shortest Path ...
Dijkstra算法是解决单源最短路径问题的标准方法,它以起始节点为中心,逐步扩展找到最短路径,适用于通信网络路由选择等问题。尽管Dijkstra算法能够给出最优解,但其效率相对较低,因为它需要遍历所有节点。 在设计...
Dijkstra算法是解决单源最短路径问题的经典算法,适用于计算一个节点到图中所有其他节点的最短路径。它以起点为中心,逐步扩展到其他节点,直到找到目标节点的最短路径。尽管Dijkstra算法能够确保找到最优解,但其...
这两种算法各有其特点和适用场景,对于理解和实现图的最短路径计算至关重要。 **Dijkstra算法** Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻于1956年发明的,主要用于单源最短路径问题。该算法基于贪心策略...
通过这两种算法的实践,学生能够深入理解通信网基础课程中的最短路径问题和最小生成树的概念,提高对网络路由算法的掌握。 在实际操作中,学生需要独立完成代码编写,实现算法在图形界面的展示,包括输出结果图和对...