一、Dijkstra算法

问题描述：求一个点到任意个点的距离 思路：单源最短路径问题，使用Dijkstra算法 city

Input： 6 9 1 2 1 1 3 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4

Output： 0 1 8 4 13 17

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
import java.util.Scanner;

public class minPath4 {
    static int[][] e = new int[10][10];
    static int[] book = new int[10];
    static int[] dis = new int[10];
    static int n, m;
    static int min = 99999999;
    static int mark = 0;
    static Scanner input = new Scanner(System.in);

    public static void main(String[] args) {
        n = input.nextInt();
        m = input.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    e[i][j] = 0;
                } else {
                    e[i][j] = 99999999;
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            int a = input.nextInt();
            int b = input.nextInt();
            int c = input.nextInt();
            e[a][b] = c;
        }
        /**
         * 1到其他各点的距离
         * */
        for (int i = 1; i <= n; i++) {
            dis[i] = e[1][i];
        }
        book[1] = 1;

        dijkstra();

        for (int i = 1; i <= n; i++) {
            System.out.print(dis[i] + " ");
        }
    }
    public static void dijkstra() {
        /**
         * 遍历n-1次，每次找出一个 1到某个点的最短距离
         * */
        for (int i = 1; i <= n-1; i++) {
            min = 99999999;
            /**
             * 选出离1号点最近的顶点
             * */
            for (int j = 1; j <= n; j++) {
                if (book[j] == 0 && dis[j] < min) {
                    min = dis[j];
                    mark = j;
                }
            }
            book[mark] = 1;
            /**
             * 松弛
             * */
            for (int j = 1; j <= n; j++) {
                if (e[mark][j] < 99999999) {
                    if (dis[j] > dis[mark] + e[mark][j]) {
                        dis[j] = dis[mark] + e[mark][j];
                    }
                }
            }
        }
    }
}

Dijkstra算法的时间复杂度为O(N^2) 这是采取邻接矩阵存放数据的时间复杂度。而如果采用下面的邻接表将会使算法的时间复杂度优化为O((M+N)logN)

邻接表： 数据存储思路：u[i],v[i],w[i] 代表存储u[i]------->v[i]的两个可连通的点，w[i]代表权值 first[u[i]]存放顶点u[i]的第一条边编号，next[i]存放编号为i的边的下一条边

下面给出邻接表定义和打印的代码，感兴趣的读者可以将其运用到Dijkstra算法中 

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
import java.util.Scanner;

public class minPath {
    static int[] u = new int[6];
    static int[] v = new int[6];
    static int[] w = new int[6];
    static int[] first = new int[6];
    static int[] next = new int[6];
    static int n, m;
    static int k;
    static Scanner input = new Scanner(System.in);

    public static void main(String[] args) {
        n = input.nextInt();
        m = input.nextInt();
        for (int i = 1; i <= m; i++) {
            u[i] = input.nextInt();
            v[i] = input.nextInt();
            w[i] = input.nextInt();
            for (int j = 1; j <= n; j++) {
                first[i] = -1;
            }
            next[i] = first[u[i]];
            first[u[i]] = i;

        }
        for (int i = 1; i <= n; i++) {
            k = first[i];
            while (k != -1) {
                System.out.println(u[k] + " " + v[k] + " " + w[k]);
                k = next[k];
            }
        }
    }
}

对于单源最短路径使用Dijkstra算法的确是一个好方法，但是如果是多源最短路径问题呢？ 当然，我们可以才用n次Dijkstra算法解决，但是下面的Floyd算法貌似给了我们更友好的解法

而且当出现带有负权值的图的时候，这Dijkstra算法就没有办法解决了,我在这篇文章整理了另一种算法来针对单源带负权最短路径问题。 图论算法（三）--最短路径 的Bellman-Flod [ 带负权值图 ] 的解法（JAVA ）

二、Floyd算法

问题描述：有如下的地图，求任意两点之间的最短距离 思路：典型的多源最短路径问题，这大可以使用n^2次深搜或者广搜完成，但是下面的Floyd算法才是更巧妙、快速的一种算法 city Input: 4 8 1 2 2 1 3 6 1 4 4 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12 Output: 0 2 5 4 9 0 3 4 6 8 0 1 5 7 10 0

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
import java.util.Scanner;

public class minPath {
    static int[][] e = new int[10][10];
    static int n, m;
    static Scanner input = new Scanner(System.in);

    public static void main(String[] args) {
        n = input.nextInt();
        m = input.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
               if (i == j) {
                   e[i][j] = 0;
               } else {
                   e[i][j] = 99999999;
               }
            }
        }
        for (int i = 1; i <= m; i++) {
            int a = input.nextInt();
            int b = input.nextInt();
            int c = input.nextInt();
            e[a][b] = c;
        }
        floyd();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(e[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void floyd() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (e[i][j] > e[i][k] + e[k][j]) {
                        e[i][j] = e[i][k] + e[k][j];
                    }
                }
            }
        }
    }
}