单源最短路径问题

问题描述

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

算法设计

Dijkstra算法是解决单源最短路径问题的一个贪心算法，其基本思想是：

• 设置顶点集合S并不断地做贪心选择来扩充这个集合，一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
• 初始时，S中仅含有源，设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。
• Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。
• 一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。

代码实现

public class test {

    static int maxint = 65533;

    public static void main(String[] args) {
        int n = 5;
        int[][] c = new int[n][n];
        c[0] = new int[]{0, 10, maxint, 30, 100};
        c[1] = new int[]{maxint, 0, 50, maxint, maxint};
        c[2] = new int[]{maxint, maxint, 0, maxint, 10};
        c[3] = new int[]{maxint, maxint, 20, 0, 60};
        c[4] = new int[]{maxint, maxint, maxint, maxint, 0};
        int[] dist = new int[n];
        int[] prev = new int[n];
        int v = 0;
        Dijkstra(n, v, dist, prev, c);
        path(2, prev);
    }

    public static void path(int x, int[] prev) {
        if (prev[x] == 0) {
            System.out.println((x + 1) + " <--- " + (prev[x] + 1));
        } else {
            System.out.println((x + 1) + " <--- " + (prev[x] + 1));
            path(prev[x], prev);
        }
    }

    public static void Dijkstra(int n, int v, int[] dist, int[] prev, int[][] c) {
        boolean[] s = new boolean[n];
        // 初始化第一个顶点。
        for (int i = 0; i < n; i++) {
            dist[i] = c[v][i];
            s[i] = false;
            if (dist[i] == maxint) {
                prev[i] = 0;
            } else {
                prev[i] = v;
            }
        }
        dist[v] = 0;
        s[v] = true;
        System.out.println("          1       2       3       4       5");
        for (int j = 0; j < s.length; j++) {
            if (j == 0) {
                System.out.print("初始化： s: ");
            }
            System.out.printf("%-8b", s[j]);
            if (j == s.length - 1) {
                System.out.println();
            }
        }

        for (int i = 0; i < dist.length; i++) {
            if (i == 0) {
                System.out.print("    dist: ");
            }
            if (dist[i] == maxint) {
                System.out.print("inf     ");
            } else {
                System.out.printf("%-8d", dist[i]);
            }
            if (i == dist.length - 1) {
                System.out.println();
            }
        }
        // 寻找其他顶点。
        for (int i = 1; i < n; i++) {
            int temp = maxint;
            int u = v;
            // 找到dist[]中路径最小的顶点，并加入s中。
            for (int j = 0; j < n; j++) {
                if ((!s[j]) && (dist[j] < temp)) {
                    u = j;
                    temp = dist[j];
                }
            }
            s[u] = true;
            for (int j = 0; j < s.length; j++) {
                if (j == 0) {
                    System.out.print(i + ":     s: ");
                }
                System.out.printf("%-8b", s[j]);
                if (j == s.length - 1) {
                    System.out.println();
                }
            }
            // 加入新顶点后，更新dist[]
            for (int j = 0; j < n; j++) {
                if ((!s[j]) && (c[u][j] < maxint)) {
                    int newdist = dist[u] + c[u][j];
                    if (newdist < dist[j]) {
                        dist[j] = newdist;
                        prev[j] = u;
                    }
                }
            }
            for (int k = 0; k < dist.length; k++) {
                if (k == 0) {
                    System.out.print("    dist: ");
                }
                if (dist[k] == maxint) {
                    System.out.print("inf     ");
                } else {
                    System.out.printf("%-8d", dist[k]);
                }
                if (k == dist.length - 1) {
                    System.out.println();
                }
            }
        }
    }
}

• Dijkstra(int n, int v, int[] dist, int[] prev, int[][] c)：通过Dijkstra算法计算源顶点v到其他顶点间的最短路径值。
  • int n：顶点的数量。
  • int v：源顶点的下标。
  • int[] dist：表示当前从源到顶点i的最短特殊路径长度，即可通过其他顶点的路径长度。
  • int[] prev：记录从源到顶点i的最短路径上i的前一个顶点。
  • int[][] c：表示边（i,j）的权值。
• path(int x, int[] prev)：计算源顶点到其他顶点x的最短路径。
  • int x：其他顶点。
  • int[] prev：记录从源到顶点i的最短路径上i的前一个顶点。