文档章节

Dijkstra Java

aqia358
 aqia358
发布于 2014/06/06 09:39
字数 453
阅读 54
收藏 1

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
博文 82
码字总数 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
【目录导航】JAVA零基础进阶之路

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

MFrank
06/21
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
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

没有更多内容

加载失败,请刷新页面

加载更多

手写tomcat+servlet

写程序一定要有思路,思路很重要! 一、我们分两步第一步先实现手写tomcat,第二部写servlet 所用技术: 1、soket通信 IO流 2、http请求与相应 3、解析xml 4、java反射技术 导入所需要的jar...

jason_kiss
28分钟前
1
0
Beetl模板的基础用法 【变量、循环、条件】---《Beetl视频课程》(2)

本期视频做了一个博客的首页列表; 内容简介:springboot 集成 beetlsql;使用for循环,使用if控制语句,使用虚拟属性,定义变量等等 一起学beetl目录:https://my.oschina.net/u/1590490?ta...

Gavin-King
34分钟前
1
0
各种视频监控上墙方案的比较

方案1、一使用 DVR 、NVR 直接显示上墙 不得不说,这种办法是成本最低廉的,但这里有不少限制: 无法实现分散点的集中上墙。譬如连锁经营的酒店,如果我在总部建立一个集中上墙的环境,这个就...

PeakFang-BOK
57分钟前
4
0
netfilter 和 iptables

一. netfilter 1. 什么是entfilter 和 iptables netfilter指整个项目名 在这个项目里面,netfilter特指内核中的netfilter框架, iptables指用户空间的配置工具。 netfilter在协议栈中添加了5...

Fc丶
今天
2
0
搞定了微信小程序富文本渲染解决方案-后端渲染方案Html2Wxml2J

先介绍一下最近遇到的问题: 最近小程序项目中有文章详情页需要渲染富文本,微信小程序官方提供的<rich-text>是个弱鸡,很多标签不支持,用起来也麻烦,性能也不咋地。 吐槽完了,我们决定寻...

山东-小木
今天
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部