单源最短路径问题（Java）

单源最短路径问题（Java）

---

---

1、问题描述

给定带权有向图G=(V,E),其中每条边的权是非负实数。另外，还给定V中的一个顶点， 称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

其中，V表示顶点集合，E表示各个节点之间的边。

2、算法思路

对于单源最短路径问题，Dijkstra算法是解决这个问题的贪心算法。

基本思想

设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时，S 中仅含有源。设u是G 的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u 的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra 算法每次从v-s中取出具有最短特殊路长度的顶点u,将u添加到S中，同时对数组dist 进行必要的修改。一旦S包含了所有V中顶点，dist数组就记录了从源到所有其他顶点之间的最短路径长度。

Dijkstra 算法可描述如下。

其中， 输入的带权有向图是G = （V, E) , V = {1 , 2, …, n} 。顶点v是源。a是一个二维数组，a[i][j]表示边(i,j)的权。当(i, j) 时，a[i][j]是一个大数。如dist[i]表示当前从源到顶点t的最短特殊路径长度。

3、代码实现

例如，对下图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。

题目示意图

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * TODO  1 --> 4 --> 3 --> 5
 */
public class Solution {

    private static int vNum, eNum;
    private static int[] v;
    private static float[][] e;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("input the number of vertix and edge:");
        vNum = scanner.nextInt();
        eNum = scanner.nextInt();

        v = new int[vNum];
        e = new float[vNum + 1][vNum + 1];
        for (int i = 0; i < e.length; i++) {
            for (int j = 0; j < e.length; j++) {
                e[i][j] = Float.MAX_VALUE;
            }
        }

        System.out.print("input the vertix information:");
        for (int i = 0; i < v.length; i++) {
            v[i] = scanner.nextInt();
        }
        System.out.println("input the weight of edges:");
        for (int i = 0; i < eNum; i++) {
            int start = scanner.nextInt(), target = scanner.nextInt();
            e[start][target] = (float) scanner.nextInt();
        }

        System.out.print("顶点有：");
        for (int i = 0; i < v.length; i++) {
            if (i == v.length - 1) {
                System.out.println(v[i]);
            } else {
                System.out.print(v[i] + ", ");
            }
        }

        System.out.println("边与边之间的距离：");
        for (int i = 1; i < e.length; i++) {
            for (int j = 1; j < e.length; j++) {
                if (i != j && e[i][j] != Float.MAX_VALUE) {
                    System.out.print("[" + i + ", " + j + "] = " + e[i][j] + "; ");
                }
            }
        }
        System.out.println();

        int[] path = new int[vNum + 1];
        float[] dist = new float[vNum + 1];

        Dijkstra(v[0], e, dist, path);

        System.out.print("Dijkstra路径为：");
        List list = new ArrayList<>();
        list.add(vNum);
        list.add(path[vNum]);
        while (true) {
            if (path[list.get(list.size() - 1)] == 1) {
                list.add(1);
                break;
            }
            list.add(path[list.get(list.size() - 1)]);
        }
        for (int j = list.size() - 1; j >= 0; j--) {
            if (j != 0) {
                System.out.print(list.get(j) + "-->");
            } else {
                System.out.println(list.get(j));
            }
        }

        System.out.println("从顶点1到各顶点最短距离：");
        for (int i = 1; i < dist.length; i++) {
            System.out.println("dist[" + i + "] = " + dist[i]);
        }

    }

    public static void Dijkstra(int vertix, float[][] weight, float[] dist, int[] path) {
        int n = dist.length - 1;
        if (vertix < 1 || vertix > n + 1) {
            return;
        }
        boolean[] vis = new boolean[n + 2];
        // initialize
        for (int i = 1; i <= n; i++) {
            dist[i] = weight[vertix][i];
            vis[i] = false;
            if (dist[i] == Float.MAX_VALUE) {
                path[i] = 0;
            } else {
                path[i] = vertix;
            }
        }
        dist[vertix] = 0;
        vis[vertix] = true;
        for (int i = 1; i < n; i++) {
            float tmp = Float.MAX_VALUE;
            int u = vertix;
            for (int j = 1; j <= n; j++) {
                if ((!vis[j]) && (dist[j] < tmp)) {
                    u = j;
                    tmp = dist[j];
                }
            }
            vis[u] = true;
            for (int j = 1; j <= n; j++) {
                if ((!vis[j]) && (weight[u][j] < Float.MAX_VALUE)) {
                    float newDist = dist[u] + weight[u][j];
                    if (newDist < dist[j]) {
                        dist[j] = newDist;
                        path[j] = u;
                    }
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

运行结果

Dijkstra算法的迭代过程：

图解过程

4、算法正确性和计算复杂性

4.1 贪心选择性质

（1）根据算法可知，最短距离是最小的路长，故
dist[x]<= d(v,x)

（2）假设存在另外一条更短路红色线所示，故
d(v,x)+d(x,u)=d(v,u)

（3）由（1）（2）可知，dist[x]

4.2 最优子结构性质

该性质描述为：如果S(i,j)={Vi…Vk…Vs…Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么S(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

假设S(i,j)={Vi…Vk…Vs…Vj}是从顶点i到j的最短路径，则有S(i,j)=S(i,k)+S(k,s)+S(s,j)。而S(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径S’(k,s)，那么S’(i,j)=S(i,k)+S’(k,s)+S(s,j)

4.3 计算复杂性

对于具有n个顶点和e条边的带权有向图， 如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n) 时间。这个循环需要执行n-1次，所以完成循环需要
0(n²）时间。算法的其余部分所需要时间不超过0(n²）。

5、参考资料

• 算法设计与分析（第四版）