力扣幺九七六，为何使用dfs版本的dijkstra会超时，而用minHeap的bfs可以过

https://leetcode.com/problems/nu ... ive-at-destination/注释掉的是我自己写的dfs，未注释的是使用minHeap的bfs，如何计算这两种方法的时间复杂度，求教嘎人们！


//     int[][] record;
//     List<int[]>[] graph;
//     int MOD = 1000000007;
//     public int countPaths(int n, int[][] roads) {
//         record = new int[n][2];
//         for(int i = 0; i < n; i++) {
//             Arrays.fill(record, -1);
//         }

//         graph = new List[n];
//         for(int i = 0; i < n; i++) {
//             graph = new ArrayList<>();
//         }
//         buildGraph(roads);

//         dfs(0, -1, 0);

//         return record[n-1][1];
//     }

//     private void dfs(int cur, int parent, int curDis) {
//         if(record[cur][0] == -1 || record[cur][0] > curDis) {
//             record[cur][0] = curDis;
//             record[cur][1] = 1;
//         }
//         else{
//             record[cur][1]++;
//             record[cur][1] %= MOD;
//         }
//         for(int[] next_dis : graph[cur]) {
//             int next = next_dis[0], dis = next_dis[1];
//             if(record[next][0] != -1 && (next == parent || record[next][0] < curDis + dis)) continue;
//             dfs(next, cur, curDis + dis);
//         }
//     }

//     private void buildGraph(int[][] roads) {
//         for(int[] road : roads) {
//             graph[road[0]].add(new int[]{road[1], road[2]});
//             graph[road[1]].add(new int[]{road[0], road[2]});
//         }
//     }

    public int countPaths(int n, int[][] roads) {
        List<int[]>[] graph = new List[n];
        for (int i = 0; i < n; i++) graph = new ArrayList<>();
        for (int[] e : roads) {
            graph[e[0]].add(new int[]{e[1], e[2]});
            graph[e[1]].add(new int[]{e[0], e[2]});
        }
        return dijkstra(graph, n, 0);
    }
   int dijkstra(List<int[]>[] graph, int n, int src){
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        int[] ways = new int[n];
        ways[src] = 1;
        dist[src] = 0;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a,b)->a[0] - b[0]);
        minHeap.offer(new int[]{0, 0});  // dist, src
        while (!minHeap.isEmpty()) {
            int[] top = minHeap.poll();
            int d = top[0], u = top[1];
            if (d > dist) continue;
            for (int[] nei : graph) {
                int v = nei[0], time = nei[1];
                if (dist[v] > d + time) {
                    dist[v] = d + time;
                    ways[v] = ways;
                    minHeap.add(new int[]{dist[v], v});
                } else if (dist[v] == d + time) {
                    ways[v] = (ways[v] + ways) % 1_000_000_007;
                }
            }
        }
        return ways[n-1];
    }

player927 发表于 2021-11-20 17:30:16
就是O(|V|log|V|+|E|)，Wikipedia上也是这么写的，你想一下Dijkstra当中我们遍历每个节点一遍的同时每次是要从Priority Queue里面remove first的，这样

VlogV + E的复杂度是有前提的，那就是priority queue需要用fibonacci heap来实现，但内置的PriorityQueue class都是用binary heap来实现的，所以复杂度就是(V+E)logE，LZ的疑问没问题
两个复杂度的差异是在于decrease priority这个操作上，一个有E条边的图最坏会产生E次decrease priority操作，普通的binary heap最坏要花O(logV)，而fibonacci的amortized time是O(1)
虽然fibonacci理论上更优，但由于结构和操作过程都很复杂，它的常数项成本很高，实际情况通常高于O(logn)，所以也是内置类不用它而用binary heap的原因
如果面试被问到复杂度，建议说(V+E)logE，你是不太可能能在面试时手写一个fibonacci heap出来的

补充内容 (2021-11-22 08:34 +08:00):
当然(V+E)logV的复杂度也是有前提的，就是这个priority queue类得支持decrease priority这个操作，如果不支持，那就需要把same node with different priorities 压进priority queue里，那最坏情况会变成ElogE，当然有很多方法可以去优化，但无法避免

不是，你DFS还能叫Dijkstra吗。。。本来你Dijkstra要想在O(|V|log|V|+|E|)的complexity那就得用基于min-heap的Priority Queue啊。。。你每个node上DFS更新一遍worst case直接奔着O(|V|^2+|E|)去了吧。。。

idealmaster 发表于 2021-11-21 12:17
VlogV + E的复杂度是有前提的，那就是priority queue需要用fibonacci heap来实现，但内置的PriorityQueue  ...

"那最坏情况会变成ElogE"

最好的情况是图是个链表，那么用Dijkstra的时候，V=E，则复杂度为VLogV
最坏的情况是图是个满图，那么ElogE = Elog(V2)=2ELogV.

所以我还是觉得即便是用BinaryHeap，仍然是V + E Log V。可能有个常数是二。

player927 发表于 2021-11-20 17:06
不是，你DFS还能叫Dijkstra吗。。。本来你Dijkstra要想在O(|V|log|V|+|E|)的complexity那就得用基于min-hea ...

感谢回复！看了点资料，大概明白了，您说的这个O(|V|log|V|+|E|)是打错了吗?是不是O(|E|log|V|+|E|)?

云水遥遥 发表于 2021-11-20 17:12:14
感谢回复！看了点资料，大概明白了，您说的这个O(|V|log|V|+|E|)是打错了吗?是不是O(|E|log|V|+|E|)?

就是O(|V|log|V|+|E|)，Wikipedia上也是这么写的，你想一下Dijkstra当中我们遍历每个节点一遍的同时每次是要从Priority Queue里面remove first的，这样就是|V|log|V|，再加上还要检查由每个节点而延伸出来的每条edge，那就是O(|V|log|V|+|E|)了

mc2 发表于 2021-11-22 08:40
"那最坏情况会变成ElogE"

最好的情况是图是个链表，那么用Dijkstra的时候，V=E，则复杂度为VLogV

你说的很有道理！