MyException - 我的异常网
当前位置:我的异常网» 编程 » Dijkstra跟Floyd_warshall

Dijkstra跟Floyd_warshall

www.MyException.Cn  网友分享于:2014-08-05  浏览:0次
Dijkstra和Floyd_warshall

import java.util.Arrays;
import java.util.Scanner;

/*题目描述:
 有n个城市,城市间有m条道路,每条道路都有长度d,给你起点城市s终点终点t,要求输出起点到终点的最短距离
 输入:
 输入n,m,城市的编号是1~n,然后是m行,每行3个数 a,b,d,表示a城市和b城市之间有一条道路,且其长度为d。假设a与b之间若有道路,则只

 有一条道路。最后一行是两个数 s,t;起点s,终点t。n和m为0时输入结束。(1<n<=1000, 0<m<100000, s != t)
 输出:
 输出一行有一个数, 表示最短距离。
 样例输入:
 3 2
 1 2 5
 2 3 4
 1 3
 0 0
 样例输出:
 9*/

/*
 * 起点s,终点t
 * map[a][b]表示a点与b点直接连通的距离,没有直接连通则为无限大
 * d[i]表示s点到i点的距离
 * fa[i]表示i点是否已经更新过了最短距离,true表示没有被使用,false表示已经被使用
 * 
 * 大致过程如下:
 * 1.先从d数组里找到一个离起点最近的点k,而且fa[k]必须为true,距离为d[k]
 * 2.将fa[k]赋值为false,接下来将用k来更新最短距离
 * 3.任意一点j,且fa[j]为false,若d[k] + map[k][j]比d[j]小则将d[k] + map[k][j]赋值给d[j]
 * 	换句话说就是先从起点走到k点(d[k]),再从k点走到j(map[k][j]),若比从起点
 * 	到j的距离(d[j])短,则d[j]应该变为d[k] + map[k][j]
 * 4.回到步骤1,直到所有fa数组里所有点都为false。
 * 5.d[t]就是起点s到终点t的最短距离
 */
public class Dijkstra {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n = cin.nextInt();
		int m = cin.nextInt();
		while (n != 0 && m != 0) {
			int[][] map = new int[n + 5][n + 5];
			for (int i = 0; i < map.length; i++) {
				// 将map任意两点的初值设置一个很大的值,表示两点间的距离无限大,即没有通路
				// 除以3是因为后面有加的地方,我害怕两个值加会超过Integer.MAX_VALUE
				Arrays.fill(map[i], Integer.MAX_VALUE / 3);
			}
			for (int i = 1; i <= m; i++) {
				int a = cin.nextInt();
				int b = cin.nextInt();
				int c = cin.nextInt();
				// a点到b点的距离是c
				map[a][b] = c;// a到b的距离赋为c
				map[b][a] = c;// b到a的距离赋为c
			}
			int s = cin.nextInt();// 起点
			int t = cin.nextInt();// 终点
			// d数组:d[i]表示起点s到i点的最短距离
			int[] d = new int[n + 5];
			Arrays.fill(d, Integer.MAX_VALUE);
			// fa数组:fa[i]表示i点是否已经更新过了最短距离,true表示没有被使用,false表示已经被使用
			boolean[] fa = new boolean[n + 5];
			Arrays.fill(fa, true);// 初始值都为true,表示所有点都可以用
			fa[s] = false;// 起点不能更新自己,所以为false
			for (int i = 1; i <= n; i++) {
				d[i] = map[s][i];// d[i]的为题目给出的map[s][i]
			}
			// 将所有点的fa的值都变为false,因为s点已经为false,所以我这里写i<n而不是i<=n
			for (int i = 1; i < n; i++) {
				int min = Integer.MAX_VALUE;
				int k = 0;
				for (int j = 1; j <= n; j++) {
					if (fa[j] && min > d[j]) {
						min = d[j];// 找到一个最小的d[j]
						k = j;// 并记录下标为k

					}

				}
				fa[k] = false;// 这样接下来就不会出现d[k] + map[k][k]的情况了,k点在i增加时被抛弃
				for (int j = 1; j <= n; j++) {
					// if(j点可用 && 当前起点s到k的最短距离+k到j直接连通的距离<当前起点s到j的最短距离)
					if (fa[j] && d[k] + map[k][j] < d[j]) {
						d[j] = d[k] + map[k][j];// 找到了更优的s到j的最短距离
					}
				}

			}
			System.out.println(d[t]);// 整个过程之后d[t]就是s到t的最短距离了

			n = cin.nextInt();
			m = cin.nextInt();
		}

	}

}



import java.util.Arrays;
import java.util.Scanner;
/*题目描述和那道Dijkstra的题一样,不过这个时间复杂度是O(n^3),
 如果和上一道题一样,n要是最多1000的话,这个算法就会超时
看完了这个算法可以看看九度1447,分别用这两种算法都做一下
 这里有一篇别人写的博客可以参考一下:http://blog.csdn.net/jdplus/article/details/19816375
 */
 
/*
 * 起点s,终点t
 * map[a][b]表示a点与b点直接连通的距离,没有直接连通则为无限大
 * 这个代码很简单大致思路:
 * 分别把所有节点都当做媒介节点
 */
public class Floyd_warshall{
 
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        while (n != 0 && m != 0) {
            int[][] map = new int[n + 5][n + 5];
            for (int i = 0; i < n + 5; i++){
                //和Dijkstra的算法一样我害怕会超过范围就除以了3
                Arrays.fill(map[i], Integer.MAX_VALUE / 3);
            }
            for (int i = 1; i <= m; i++) {
                int a = cin.nextInt();
                int b = cin.nextInt();
                int c = cin.nextInt();
                map[a][b] = c;
                map[b][a] = c;
            }
            //这个代码很简单,下面两段分割线之间就是最核心的代码
            //----------------------------------
            for (int k = 1; k <= n; k++)//k为媒介节点
                for (int i = 1; i <= n; i++)//i为所有的起点
                    for (int j = 1; j <= n; j++)//j为所有的终点
                    	/*
                    	 * 下面是最关键的两句:
                    	 * 如果i到k的距离加上k到j的距离比i到j的距离小,
                    	 * 则更新map[i][j]为map[i][k] + map[k][j]
                    	 * 就是不断把k当做中间节点来更新其他的两点的距离
                    	 */
                        if (map[i][k] + map[k][j] < map[i][j]) {//如果i到k的距离加上k到j的距离比i到j的距离小
                            map[i][j] = map[i][k] + map[k][j];//更新map[i][j]
                        }
            //----------------------------------
            int s = cin.nextInt();
            int t = cin.nextInt();
            System.out.println(map[s][t]);//更新后的map[s][t]已经是s到t的最短里的
 
            n = cin.nextInt();
            m = cin.nextInt();
        }
 
    }
 
}


九度1447可以两种方法都可以,九度1008只能用第一种方法


文章评论

如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
旅行,写作,编程
旅行,写作,编程
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
中美印日四国程序员比较
中美印日四国程序员比较
 程序员的样子
程序员的样子
每天工作4小时的程序员
每天工作4小时的程序员
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员和编码员之间的区别
程序员和编码员之间的区别
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
如何成为一名黑客
如何成为一名黑客
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
代码女神横空出世
代码女神横空出世
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
我是如何打败拖延症的
我是如何打败拖延症的
程序员都该阅读的书
程序员都该阅读的书
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员必看的十大电影
程序员必看的十大电影
老程序员的下场
老程序员的下场
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
编程语言是女人
编程语言是女人
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
Java程序员必看电影
Java程序员必看电影
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员应该关注的一些事儿
程序员应该关注的一些事儿
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
漫画:程序员的工作
漫画:程序员的工作
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
我的丈夫是个程序员
我的丈夫是个程序员
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
鲜为人知的编程真相
鲜为人知的编程真相
那些争议最大的编程观点
那些争议最大的编程观点
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
为什么程序员都是夜猫子
为什么程序员都是夜猫子
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有