吉克斯特拉的最短路径算法

Question

我正在学习Djikstra's，我已经根据与Djikstra略有不同的想法准备了下面的代码。现在，在许多网站中，我已经看到使用提取最小值和访问边的布尔数组。我没有使用，我的答案也是正确的。是否有任何测试用例或场景，我的算法不会工作。

    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算法。

1. 即使存在负边(但没有负循环)也会给出正确的最短路径

2. 它可以检测是否存在负循环(但如果存在负循环则不会给出正确的解决方案，因此最好终止代码)