图算法(二)-最短路径

本文主要是介绍图算法(二)-最短路径，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1. 

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Dijkstra

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        //1.define map to store the other vertics and distance
        Map<Integer,List<int[]>> map = new HashMap();
        for(int[] time:times){
            List<int[]> list = map.getOrDefault(time[0],new ArrayList());
            list.add(new int[]{time[1],time[2]});
            map.put(time[0],list);
        }
        //2.init distance
        int[] distance = new int[n+1];
        boolean[] visited = new boolean[n+1];
        Arrays.fill(distance,Integer.MAX_VALUE);
        //3.start from the source
        distance[k]=0;
        while(true){
            int curr = -1;
            for(int i=1;i<=n;i++){
                if(!visited[i]){
                    if(curr==-1 || distance[i]<distance[curr]) curr=i;
                }
            }
            if(curr==-1) break;
            visited[curr]=true;
            for(int[] other:map.getOrDefault(curr,Arrays.asList())){
                if(distance[other[0]]>distance[curr]+other[1]) distance[other[0]] = distance[curr]+other[1];//relaxation
            }
        }
        int max = 0;
        for(int i=1;i<=n;i++) max = Math.max(max,distance[i]);
        return max==Integer.MAX_VALUE ? -1 : max;//坑点，注意有可能压根不连通时要返回-1
    }
}

Dijkstra PQ 优化版

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        //1.define map to store the other vertics and distance
        Map<Integer,List<int[]>> map = new HashMap();
        for(int[] time:times){
            List<int[]> list = map.getOrDefault(time[0],new ArrayList());
            list.add(new int[]{time[1],time[2]});
            map.put(time[0],list);
        }
        //2.init distance
        int[] distance = new int[n+1];
        Arrays.fill(distance,Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>((x,y)->x[1]-y[1]);
        //3.start from the source
        distance[k]=0;
        pq.offer(new int[]{k,0});
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            for(int[] other:map.getOrDefault(curr[0],Arrays.asList())){
                if(distance[other[0]]>distance[curr[0]]+other[1]) {
                    distance[other[0]] = distance[curr[0]]+other[1];//relaxation
                    pq.offer(new int[]{other[0],distance[other[0]]});
                }
            }
        }
        int max = 0;
        for(int i=1;i<=n;i++) max = Math.max(max,distance[i]);
        return max==Integer.MAX_VALUE ? -1 : max;//坑点，注意有可能压根不连通时要返回-1
    }
}

这篇关于图算法(二)-最短路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！