Dijkstra算法

Dijkstra算法是用来解决单源最短路径问题的，单源最短路径问题就是有向无环图中从一个顶点到其他顶点的最短路径问题，Dijkstra算法属于贪婪算法。

image.png

随便画了一个图，现在咱们求从顶点1到其余各点的最短路径。

邻接矩阵表示

对于稠密图，建议使用邻居矩阵表示，邻接矩阵在Java语言中就是一个二维数据，从顶点1到2有边，则A[1][2] = 4，从顶点1到顶点5没有边，则A[1][5] = ♾，得到如下邻接矩阵

image.png

此处只是示意，从图中看，这应该属于稀疏图，但我们仍然使用邻接矩阵表示，谁让这只是一个例子呢。

class Dijkstra {

    private static final int MAX_VALUE = 10000;

    public static void main(String[] args) {
        System.out.println("hello algorithm");

        int[][] matrix = {
                {0, 4, 7, MAX_VALUE, MAX_VALUE},
                {MAX_VALUE, 0, MAX_VALUE, 3, 10},
                {MAX_VALUE, MAX_VALUE, 0, 2, 5},
                {MAX_VALUE, MAX_VALUE, MAX_VALUE, 0, 9},
                {MAX_VALUE, MAX_VALUE, MAX_VALUE, MAX_VALUE, 0}
        };

        int[] distance = new int[5];
        for (int i = 0; i < 5; i++) {
            distance[i] = matrix[0][i];
            System.out.print(distance[i] + ", ");
        }

        boolean[] visited = new boolean[5];
        for (int i = 0; i < 5; i++) {
            System.out.print(visited[i] + ", ");
        }
        visited[0] = true;

        while (hasUnknown(visited)) {
            int minIndex = findMin(distance, visited);
            System.out.println(minIndex);
            visited[minIndex] = true;
            for (int i = 0; i < 5; i++) {
                if (!visited[i] && (distance[i] > distance[minIndex] + matrix[minIndex][i])) {
                    distance[i] = distance[minIndex] + matrix[minIndex][i];
                }
            }
        }

        for (int i = 0; i < 5; i++) {
            System.out.print(distance[i] + ", ");
        }
    }

    private static int findMin(int[] distance, boolean[] known) {
        int min = MAX_VALUE;
        int index = -1;
        for (int i = 0; i < distance.length; i++) {
            if (!known[i] && (distance[i] < min)) {
                min = distance[i];
                index = i;
            }
        }

        return index;
    }

    private static boolean hasUnknown(boolean[] known) {
        for (int i = 0; i < known.length; i++) {
            if (!known[i]) {
                return true;
            }
        }

        return false;
    }
}

代码中用到了一个二维数组，一个一维int数组表示到其他顶点的最短距离，一个一维boolean数组表示顶点是否已被访问过，时间复杂度为O(n^2)。

邻接表表示

对于稀疏图，建议使用邻接表表示，而Dijkstra算法更适合稀疏图。

image.png

class Dijkstra2 {

    private static final int MAX_VALUE = 10000;

    public static void main(String[] args) {
        List<List<Edge>> graph = new ArrayList<>();

        for (int i = 0; i < 5; i++) {
            graph.add(new LinkedList<Edge>());
        }

        addEdge(graph, 0, 1, 4);
        addEdge(graph, 0, 2, 7);
        addEdge(graph, 1, 3, 3);
        addEdge(graph, 1, 4, 10);
        addEdge(graph, 2, 3, 2);
        addEdge(graph, 2, 4, 5);
        addEdge(graph, 3, 4, 9);

        int[] distance = new int[5];
        for (int i = 1; i < 5; i++) {
            distance[i] = MAX_VALUE;
        }

        for (Edge edge: graph.get(0)) {
            distance[edge.dest] = edge.weight;
        }
        printDistance(distance);

        boolean[] visited = new boolean[5];
        visited[0] = true;

        while (hasUnknown(visited)) {
            int minIndex = findMin(distance, visited);
            System.out.println(minIndex);
            visited[minIndex] = true;
            for (Edge edge: graph.get(minIndex)) {
                if (!visited[edge.dest] && (distance[edge.dest] > distance[minIndex] + edge.weight)) {
                    distance[edge.dest] = distance[minIndex] + edge.weight;
                }
            }
            printDistance(distance);
        }

        printDistance(distance);
    }

    public static void printDistance(int[] distance) {
        for (int i = 0; i < distance.length; i++) {
            if (i == distance.length - 1) {
                System.out.println(distance[i]);
            } else {
                System.out.print(distance[i] + " ");
            }
        }
    }

    private static int findMin(int[] distance, boolean[] known) {
        int min = MAX_VALUE;
        int index = -1;
        for (int i = 0; i < distance.length; i++) {
            if (!known[i] && (distance[i] < min)) {
                min = distance[i];
                index = i;
            }
        }

        return index;
    }

    private static boolean hasUnknown(boolean[] known) {
        for (int i = 0; i < known.length; i++) {
            if (!known[i]) {
                return true;
            }
        }

        return false;
    }

    private static void addEdge(List<List<Edge>> graph, int src, int dest, int weight) {
        graph.get(src).add(new Edge(dest, weight));
    }

    private static class Edge {
        final int dest;
        final int weight;

        public Edge(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }
}

具有负权的图(Bellman-Ford 算法)

斐波那契堆实现

参考：

1. 《数据结构与算法分析》
2. 经典算法研究系列：二、Dijkstra 算法初探
3. 经典算法研究系列：二之续、彻底理解Dijkstra算法