最短路径

简单图最短路径直接上BFS

Network Delay Time

• single source shortest path的题，用Dijkstra 求最短路

• Dijkstra 算法类似于BFS, 也需要一个Queue存candidate和visited set, 区别在于

  • BFS总是找curNode的neighbor

  • Dijkstra找的是离curNode距离最近的nextNode, 类似贪心算法

  • 需要用PriorityQuue/minHeap来根据距离排序，找出距离最近的nextNode

• Time complexity: O(V + ELogV) 借助heap

• Space complexity: O(V)

public int networkDelayTime(int[][] times, int N, int K) {
        //construct graph, key is node, value is neighbor-> dist map
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] time : times) {
            graph.putIfAbsent(time[0], new HashMap<>());
            graph.get(time[0]).put(time[1], time[2]);
        }
        //minHeap, sort by dist
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b)->(a[1] - b[1]));
        Set<Integer> visited = new HashSet<>();
        minHeap.offer(new int[] {K, 0});
        int res = 0;
        while (!minHeap.isEmpty()) {
            int[] cur = minHeap.poll();
            if (visited.contains(cur[0])) continue;
            visited.add(cur[0]);
            res = Math.max(res, cur[1]);
            Map<Integer, Integer> neighborMap = graph.get(cur[0]);
            if (neighborMap == null) continue;
            for (int neighbor : neighborMap.keySet()) {
                int dist = cur[1] + neighborMap.get(neighbor);
                minHeap.offer(new int[] {neighbor, dist});
            }
        }
        return visited.size() == N ? res : -1;
    }