文档章节

Dijkstra Java

aqia358
 aqia358
发布于 2014/06/06 09:39
字数 453
阅读 54
收藏 1
点赞 0
评论 0

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。

其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Dijkstra {

	public static int[][] f;
	public static int[] vis;
	public static int[] fa;
	public static int N;

	public static void dijkstra() {
		int i, j, start, dmin, next;
		i = j = start = next = 0;
		vis[start] = 1;
		fa[0] = 0;

		for(int count = 1; count < N - 1; ++count){
			dmin = 9999;
			for (i = 1; i < N; ++i) {
				if (vis[i] == 0 && f[start][i] < dmin) {
					dmin = f[start][i];
					next = i;
				}
			}
			vis[next] = 1;
			for (j = 1; j < N; ++j) {
				if (vis[j] == 0
						&& f[start][next] + f[next][j] < f[start][j]) {
					fa[j] = next;
					f[start][j] = f[start][next] + f[next][j];
				}
			}
		}
		print();
	}
	public static void dijkstra(int start, int end) {
		int i, j, dmin, next;
		i = j = start = next = 0;
		vis[start] = 1;
		
		while(next != end){
			dmin = 9999;
			for (i = 1; i < N; ++i) {
				if (vis[i] == 0 && f[start][i] < dmin) {
					dmin = f[start][i];
					next = i;
				}
			}
			vis[next] = 1;
			for (j = 1; j < N; ++j) {
				if (vis[j] == 0
						&& f[start][next] + f[next][j] < f[start][j]) {
					f[start][j] = f[start][next] + f[next][j];
					fa[j] = next;
				}
			}
		}
		print();
		printPath(start, end);
	}

	
	public static void print(){
		for(int i = 0; i < N; ++i){
			for(int j = 0; j < N; ++j){
				System.out.print(f[i][j]+"\t");
			}
			System.out.println();
		}
	}
	
	public static void printPath(int start, int target){
		if(target == start){
			System.out.print(start);
		}else{
			printPath(start, fa[target]);
			System.out.print("=>"+target);
		}
	}
	public static void main(String[] args) {
		try {
			Scanner s = new Scanner(new File("d:/c.txt"));
			N = s.nextInt();
			f = new int[N][N];
			vis = new int[N];
			fa = new int[N];
			for(int i = 0; i < N; ++i){
				for(int j = 0; j < N; ++j){
					f[i][j] = s.nextInt();
				}
			}
//			dijkstra();
			dijkstra(0, 1);
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

}




© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 81
码字总数 30297
作品 0
海淀
程序员
飞龙的程序员书单 – 数据结构、算法

入门向 啊哈!算法 这本书真心简洁易懂,dijkstra我是看课本怎么看也看不懂,最后看这本书才懂的。真心推荐。 大话数据结构 工程向 算法 Java实现 C实现 C++实现 普林斯顿的算法课程教材,Cou...

apachecn_飞龙
2016/01/15
0
0
JDK、JRE、JVM三者间的关系

  JDK(Java Development Kit)是针对Java开发员的产品,是整个Java的核心,包括了Java运行环境JRE、Java工具和Java基础类库。Java Runtime Environment(JRE)是运行JAVA程序所必须的环境...

张德德
2014/02/28
0
0
JDK 1.7 基本概念和目录结构

参考资料: http://blog.csdn.net/kindazrael/article/details/7270673 http://docs.oracle.com/javase/7/docs/index.html JDK and JRE File Structure http://docs.oracle.com/javase/7/doc......

jack688
06/26
0
0
一句话讲清楚什么是JavaEE

Java技术不仅是一门编程语言而且是一个平台。同时Java语言是一门有着特定语法和风格的高级的面向对象的语言,Java平台是Java语言编写的特定应用程序运行的环境。Java平台有很多种,很多的Jav...

qq58edeba279279
06/26
0
0
My java——JVM(java 虚拟机)一

JVM是Java Virtual Machine(Java虚拟机)的缩写。一般我们在学习java中会用到很多缩写名称,如JRE、JDK、SDK、JAVA SE、JAVA EE、JAVA ME、JAVA FX、还有j2se、j2ee、javaee5,我勒个去!多...

tngou
2013/03/13
0
2
linux下的jdk环境变量配置

新安装的ubuntu不能以root用户登录,可以这样做 sudo passwd root //然后设置密码 su //输入密码登录 ubuntu 新建简单文本 touch hello.sh //新建文件 hello.sh vim hello.sh // 打开hello文...

苏云飞
2015/11/18
0
0
【目录导航】JAVA零基础进阶之路

【JAVA零基础入门系列】(已完结)导航目录 Day1 开发环境搭建 Day2 Java集成开发环境IDEA Day3 Java基本数据类型 Day4 变量与常量 Day5 Java中的运算符 Day6 Java字符串 Day7 Java输入与输出...

MFrank
06/21
0
0
ThreadLocal in Java - Example Program and Tutorial

ThreadLocal in Java is another way to achieve thread-safety apart from writing immutable classes. If you have been writing multi-threaded or concurrent code in Java then you mus......

perfectspr
2014/12/10
0
0
JVM基础:深入学习JVM堆与JVM栈

以前堆是干啥栈是干啥都知道,就是没连在一起想想。感觉讲的不错的一篇儿~~JVM栈解决程序的运行问题,即程序如何执行,或者说如何处理数据;JVM堆解决的是数据存储的问题,即数据怎么放、放在...

李星
2014/06/04
0
0
JVM -verbose参数详解(转)

转自:http://www.javaranger.com/archives/367 java -verbose[:class|gc|jni] 在输出设备上显示虚拟机运行信息。 1.java -verbose:class 在程序运行的时候有多少类被加载!你可以用verbose...

巴顿
2014/12/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周一乱弹 —— 如果是你喜欢的女同学找你借钱

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @guanglun :分享Michael Learns To Rock的单曲《Fairy Tale》 《Fairy Tale》- Michael Learns To Rock 手机党少年们想听歌,请使劲儿戳(这...

小小编辑
24分钟前
7
3
NNS域名系统之域名竞拍

0x00 前言 其实在官方文档中已经对域名竞拍的过程有详细的描述,感兴趣的可以移步http://doc.neons.name/zh_CN/latest/nns_protocol.html#id30 此处查阅。 我这里主要对轻钱包开发中会用到的...

暖冰
今天
0
0
32.filter表案例 nat表应用 (iptables)

10.15 iptables filter表案例 10.16/10.17/10.18 iptables nat表应用 10.15 iptables filter表案例: ~1. 写一个具体的iptables小案例,需求是把80端口、22端口、21 端口放行。但是,22端口我...

王鑫linux
今天
0
0
shell中的函数&shell中的数组&告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析

影夜Linux
今天
0
0
Linux网络基础、Linux防火墙

Linux网络基础 ip addr 命令 :查看网口信息 ifconfig命令:查看网口信息,要比ip addr更明了一些 centos 7默认没安装ifconfig命令,可以使用yum install -y net-tools命令来安装。 ifconfig...

李超小牛子
今天
1
0
[机器学习]回归--Decision Tree Regression

CART决策树又称分类回归树,当数据集的因变量为连续性数值时,该树算法就是一个回归树,可以用叶节点观察的均值作为预测值;当数据集的因变量为离散型数值时,该树算法就是一个分类树,可以很...

wangxuwei
昨天
1
0
Redis做分布式无锁CAS的问题

因为Redis本身是单线程的,具备原子性,所以可以用来做分布式无锁的操作,但会有一点小问题。 public interface OrderService { public String getOrderNo();} public class OrderRe...

算法之名
昨天
11
0
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
昨天
1
0
数据结构与算法1

第一个代码,描述一个被称为BankAccount的类,该类模拟了银行中的账户操作。程序建立了一个开户金额,显示金额,存款,取款并显示余额。 主要的知识点联系为类的含义,构造函数,公有和私有。...

沉迷于编程的小菜菜
昨天
1
0
从为什么别的队伍总比你的快说起

在机场候检排队的时候,大多数情况下,别的队伍都要比自己所在的队伍快,并常常懊悔当初怎么没去那个队。 其实,最快的队伍只能有一个,而排队之前并不知道那个队快。所以,如果有六个队伍你...

我是菜鸟我骄傲
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部