文档章节

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
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

没有更多内容

加载失败,请刷新页面

加载更多

一次由HandlerInterceptor进行的深入思考

HandlerInterceptor 是SpringFramework为我们提供的拦截器,一般我们可以用来鉴权或者日志记录等。 它是一个interface,主要方法有: /** * Intercept the execution of a handler. Called...

kipeng300
30分钟前
1
0
cmd中查询mysql表出现中文乱码

问题:在pycharm中正常的fetchall拉取数据,能够正常显示,而在cmd中直接select却出现中文乱码。 解决思路:右键查看cmd命令窗口属性得到,cmd窗口默认编码是gbk(如下图所示),而设置的mys...

fang_faye
56分钟前
2
0
centOS 安装Python3与python2并存

centOS 安装Python3与python2并存 如果本机安装了python2,尽量不要管他,使用python3运行python脚本就好,因为可能有程序依赖目前的python2环境, 比如yum!!!!! 不要动现有的python2环...

MedivhXu
今天
2
0
Spring JdbcTemplate模板模式与回调结合分析

在看Spring的JdbcTemplate的时候,看到其将模板模式和回调模式结合使用的实现,可以精妙的解决很多的问题。详见Spring中涉及的设计模式总结中的关于模板模式和回调模式结合的具分析,本文利用...

宸明
今天
1
0
docker update:更新一个或多个容器的配置

更新容器的配置 docker update:更新一个或多个容器的配置。 具体内容请访问:https://docs.docker.com/engine/reference/commandline/update/#options 语法:docker update [OPTIONS] CONTA...

lwenhao
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部