Dijkstra 的最短路径算法

Question

我正在学习 Djikstra，我根据与 Djikstra 略有不同的想法准备了下面的代码。现在，在许多网站中，我已经看到使用 Extract min 和 boolean array of visited edges。我用过none，我的答案也是正确的。是否存在我的算法无法运行的任何测试用例或场景。

    import java.util.*;
    class ShortestPath2 {
        static int Ar[][];
        static int dist[];

        static int nodes;
        public static void djikstra(int source) {
            LinkedList < Integer > list = new LinkedList < Integer > ();
            dist[source] = 0;

            list.add(source);
            while (!list.isEmpty()) {
                source = list.removeFirst();

                for (int i = 0; i < nodes; i++) {
                    if (Ar[source][i] != 0) {

                        if (dist[i] > dist[source] + Ar[source][i]) {
                            dist[i] = Math.min(dist[i], dist[source] + Ar[source][i]);
                            list.add(i);
                        }
                    }
                }

            }
            System.out.println(Arrays.toString(dist));
        }

        public static void main(String[] args) {
            nodes = 9;

            Ar = new int[nodes][nodes];
            dist = new int[nodes];

            Arrays.fill(dist, Integer.MAX_VALUE);

            Ar = new int[][] {
                 {0,  4, 0,  0,  0,  0, 0,  8, 0},
                 {4,  0, 8,  0,  0,  0, 0, 11, 0},
                 {0,  8, 0,  7,  0,  4, 0,  0, 2},
                 {0,  0, 7,  0,  9, 14, 0,  0, 0},
                 {0,  0, 0,  9,  0, 10, 0,  0, 0},
                 {0,  0, 4, 14, 10,  0, 2,  0, 0},
                 {0,  0, 0,  0,  0,  2, 0,  1, 6},
                 {8, 11, 0,  0,  0,  0, 1,  0, 7},
                 {0,  0, 2,  0,  0,  0, 6,  7, 0}
            };

            djikstra(0);
        }
    }

Answer 1

Dijkstra 算法背后的整个思想是使用优先级队列。您不能从 Dijkstra 中删除优先级队列并仍将其称为 Dijkstra 算法。你写的是一个没有检查访问的 BFS。如果图表有负循环，您的代码将不会终止。您的代码将在图 a 上找到没有负循环的最短路径，但复杂性可能会呈指数级增长。因为有可能一遍又一遍地重新访问节点（作为删除访问列表的结果）。如果您将已访问列表添加到您的代码中，您的代码将不会总能找到最短路径，因为您没有使用优先级队列。所以你需要优先级队列和访问列表才能在线性时间内找到最短路径。

A --100---B --100-- I---100---O  // A-B, B-I, I-O weight : 100
|        / \       / \        |  // A-C, C-D, ... weight : 1
C-D-E-F-G   H-J-K-L   M-N-P-Q-R

例如，您可以使用上图查看您的代码将重新访问多少次 O。

Answer 2

Dijkstra 的原始实现没有解决负边沿（但可以检测到）和负循环问题。

要解决这个问题，我们可以使用 Bellman Ford 算法。

即使有负边（但没有负循环）也会给出正确的最短路径
它可以检测是否存在负循环（但如果存在负循环则不会给出正确的解决方案，所以我们最好终止代码）

Dijkstra 的最短路径算法

Djikstra's Shortest path algorithm

java

algorithm

dijkstra

shortest-path

graph-algorithm