Java 实现 Dijsktra 算法

2019-11-06 07:45:01

字体：大中小

来源：转载

供稿：网友

看看书中的描述：这里写图片描述

书中是用C++实现的，C++比较难，懂个思路就行，这里用java实现：

这里写图片描述

package graph;public class Dijkstra { PRivate static final int MAXSIZE = 1000; private static final int INF = 1200; private static final int N = 6; public static void main(String[] args) { System.out.println("------------Dijsktra------------"); int[][] data = { {MAXSIZE, 12, MAXSIZE, 12, 5, MAXSIZE}, {MAXSIZE, MAXSIZE, 7, MAXSIZE, 4, MAXSIZE}, {MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, 1}, {MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, 7}, {MAXSIZE, MAXSIZE, 14, 9, MAXSIZE, 32}, {MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE}, }; int v = 1; System.out.println("打印有向图的邻接矩阵："); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { System.out.print(" " + data[i][j]); } System.out.println(); } System.out.println("打印原点1到其它各点的最短路径及其长度："); toDijsktra(data, v); } private static void toDijsktra(int[][] data, int v) { //dist[]顶点到顶点的最短距离 int[] dist = new int[N]; //path[]存放上一个顶点 int[] path = new int[N]; //s[]存放已经加入到最短路径的顶点 int[] s = new int[N]; int f = v - 1; //初始化第一个顶点 for(int i = 0; i < N; i++) { dist[i] = data[f][i]; if(dist[i] != MAXSIZE) { path[i] = v; } else { path[i] = 0; } } for(int i = 0; i < N; i++) { s[i] = 0; } //将第一个顶点加入最短路径集合 s[f] = 1; //第一个顶点到第一个顶点的距离为0 dist[f] = 0; int k = 0; for(int i = 0; i < N - 1; i++) { int min = INF; //该for循环找出最短的边 for(int j = 0; j < N; j++) { if((s[j] == 0) && (dist[j] < min)) { min = dist[j]; //最短边的顶点赋给K k = j; } } //将K顶点加入最短路径集合 s[k] = 1; //更新d[]的值，保证d[j]里面的值是有第一个顶点到k顶点的最短距离 for(int j = 0; j < N; j++) { if((s[j] == 0) && (dist[j] > (dist[k] + data[k][j]))) { dist[j] = dist[k] + data[k][j]; path[j] = k + 1; } } } for(int i = 0; i < N; i++) { System.out.print(v + "到" + (i+1) + "的最短距离是"); System.out.print(dist[i]); System.out.println(); int pre = path[i]; System.out.print("路径:" + (i+1)); while(pre != 0) { System.out.print("<------" + pre); pre = path[pre-1]; } System.out.println(); System.out.println("-----------------------"); } }}

运行结果：

这里写图片描述