迪杰斯特拉(Java)

java

 1 public class Dijsktra {

2

3 public static void main(String[] args)

4 {

5 Dijsktra d=new Dijsktra();

6 int[][] w={{0,1},{2,0}};

7

8 int[] a=d.DijsktraWay(w,0);

9 //System.out.println(1111);

10 }

11

12 // 返回来的是路径

13 public int[] DijsktraWay(int[][] weight, int start) {

14

15 // 接受一个有向图的权重矩阵和一个起点编号start从0编号顶点存在数组中

16 // 返回一个int[] 数组表示从start到它的最短路径长度

17 int n = weight.length; // 顶点个数

18

19 int[] shortPath = new int[n]; // 存放从start到其他各点的最短路径

20 String[] path = new String[n]; // 存放从start到其他各点的最短路径的字符串表示

21 for (int i = 0; i < n; i++) {

22 path[i] = new String(start + ">" + i);

23 shortPath[i] = Integer.MAX_VALUE / 2;

24 }

25 int[] visited = new int[n]; // 标记当前该顶点的最短路径是否已经求出,1表示已求出

26 // 初始化第一个顶点求出

27 shortPath[start] = 0;//没有环

28 visited[start] = 1; // 表示已经访问过

29

30 for (int count = 1; count <= n - 1; count++) // 要加入n-1个顶点,每次加入一个点后

31 //就会有一个点被标记

32 {

33 int k = -1; // 选出一个距离初始顶点start最近的未标记顶点

34 int dmin = Integer.MAX_VALUE / 2;

35 for (int i = 0; i < n; i++) {

36 //如果此点未访问并且距离起始点距离较上一个的小,则应进行修改

37 if (visited[i] == 0 && weight[start][i] < dmin) {

38 dmin = weight[start][i];//表示距离起始点最近的点

39 k = i;//将距离起始点最近的点标记为k

40 }

41 }

42

43 if (k == -1) {

44 break;

45 // return null;

46 }

47 // 将新选出的顶点标记为已求出最短路径且到start的最短路径就是dmin

48 shortPath[k] = dmin;

49 visited[k] = 1;

50 // 以k为中间点修正从start到未访问各点的距离

51 for (int i = 0; i < n; i++) {

52 if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) {

53 weight[start][i] = weight[start][k] + weight[k][i];

54 path[i] = path[k] + ">" + i;

55 }

56 //System.out.println(shortPath[i]);

57 System.out.println( path[i]);

58 }

59 }

60

61

62 return shortPath;

63 }

64

65 }

   

确定起点的最短路径问题:即已知起始结点,求最短路径的问题。适合迪杰斯特拉算法

确定终点的最短路径问题:与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径反转的确定起点的问题。

以上是 迪杰斯特拉(Java) 的全部内容, 来源链接: utcz.com/z/390909.html

回到顶部