Dijkstra Java
博客专区 > aqia358 的博客 > 博客详情
Dijkstra Java
aqia358 发表于4年前
Dijkstra Java
  • 发表于 4年前
  • 阅读 47
  • 收藏 1
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

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();
		}
	}

}




标签: Java dijkstra
共有 人打赏支持
粉丝 7
博文 81
码字总数 30297
×
aqia358
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: