Simple Java Solution using BFS (similar to dijkstra's shortest path algorithm) with explanation


  • 5
    A

    The idea is to find the time to reach every other node from given node K
    Then, to check if all nodes can be reached and if it can be reached then return the time taken to reach the farthest node (node which take longest to get the signal).
    As the signal traverses concurrently to all nodes, we have to find the maximum time it takes to reach a node among all nodes from given node K.
    If any single node takes Integer.MAX_Value, then return -1, as not all nodes can be reached

    add the index of all the nodes which can be reached from a node to a list and store this list in a hashmap

    then its similar to dijkstra's shortest path algorithm except that I am not using Priority Queue to get the minimum distance node. See comments.

    class Solution {
        public int networkDelayTime(int[][] times, int N, int K) {
            int r = times.length, max = Integer.MAX_VALUE;
            
            Map<Integer,List<Integer>> map = new HashMap<>();
            for(int i=0;i<r;i++){
                int[] nums = times[i];
                int u = nums[0];
                int v = nums[1];
                List<Integer> list = map.getOrDefault(u,new ArrayList<>());
                
                list.add(i);
                
                map.put(u,list);
            }
            if(map.get(K) == null){
                return -1;// no immediate neighbor of node K, so return -1
            }
            int[] dist = new int[N+1];//dist[i] is the time taken to reach node i from node k
            Arrays.fill(dist,max);
            
            dist[K] = 0;
            Queue<Integer> queue = new LinkedList<>();
            
            queue.add(K);
            
            while(!queue.isEmpty()){
                int u = queue.poll();
                int t = dist[u];
                List<Integer> list = map.get(u);// get the indices of all the neighbors of node u
                if(list == null)
                    continue;
                
                for(int n:list){
                    int v = times[n][1];
                    int time = times[n][2];// time taken to reach from u to v
                     if(dist[v] > t + time){// if time taken to reach v from k is greater than time taken to reach from k to u + time taken to reach from u to v, then update dist[v]
                        dist[v] = t + time;
                        queue.add(v);// as we have found shorter distance to node v, explore all neighbors of v
                    }                
                }
            }
            
            int res = -1;
            
            for(int i=1;i<=N;i++){
                int d = dist[i];
                if(d == max){// if d is max, it means node i can not be reached from K, so return -1
                    return -1;
                }
                res = d > res ? d : res;
            }
            
            return res;
        }
    }
    

    Note: I have updated the solution description and solution. Yes, my solution is not exactly dijkstra, but it was inspired by it and I thought it was very similar except that it is not very similar.


  • 0
    G

    Tiny improvement for initializing Adjacent map.

    for (int i = 0; i < r; i++) {
        map.computeIfAbsent(nums[0], (ArrayList::new)).add(i);
    }
    

  • 0
    J

    @ashish53v said in Simple Java Solution using dijkstra's shortest path algorithm with explanation:

    dijkstra's shortest path algorithm

    How did you ensure u is the shortest next node when calling "u = queue.poll();"?


  • 0
    A

    @jinsheng u = queue.poll();
    u is not a shortest next node.
    See in dijkstra's algorithm we use Visited set and we do not explore same node again and again. But, the nodes are explored in shortest distance first manner.

    What I am doing is, I am not using the Visited set and also not getting the nodes shortest first.
    But as I am exploring the same node again and again, it ensures correctness. A node J will be explored N times if it can be reached in N different ways from node K (directly or via other nodes)

    see this example:

    nodes 1,2,3,4
    K = 1
    say we have (1,2,2)
    (1,3,2)
    (1,4,100)
    (2,4,10)
    (3,2,5)
    initialy dist [max,0,max,max,max];
    lets assume after K (1 node) node 4, node 2 and node 3 goes into queue in this order
    after 1 is explored
    dist becomes [max,0,2,2,100]
    queue {4,2,3}
    after 4 is explored
    dist becomes [max,0,2,2,100]
    queue {2,3}
    when 2 is explored, 
    
    dist becomes [max,0,2,max,12]
    
    dist[4] gets updated, As we have found a shorter distance to 4, we need to check all the neighbors of node 4 again, so we add node 4 to the queue again.
    
    queue becomes {3,4}...
    
    

    So as node 4 can be reached in 2 ways from node K, so we checked the distance to node 4 twice and found the minimum distance (time required).
    This is not exactly dijkstra's shortest path algorithm, but I use a similar idea.

    I hope this helps.


  • 0
    A

    @Ghost_141 I am not familiar with this map method. What does it do?

    Is it similar to this, like we need to put list on the map only once and not again and again

    List<Integer> list = map.getOrDefault(u,new ArrayList<>());
    list.add(i);
    if(list.size() == 1)//only put list in the map for the first time
          map.put(u,list);
    

  • 0
    J

    @ashish53v
    Thanks for your explanation!
    I thought this is not dijkstra's algorithm as well.


  • 0
    G

    @ashish53v No it's not similar with your code here.

    The code I provide is basically doing following two things.

    Get the mapping value for the given key and do computation to generate it when key is missing.

    // Code here is equal to computeIfAbsent(u, (ArrayList::new));
    List<Integer> list;
    if (!map.containsKey(u)) {
        list = do_some_computation();
    } else {
        list = map.get(y);
    }
    return list;
    

    and then add the index into it.

    // add(i)
    list.add(i);
    

    So it won't check the size of list but indeed will only put the list in map once.


  • 0
    A

    i have to say, this is not Dijkstra algorithm.
    In Dijkstra, you should use priorityQueue to choose the nearst node to update the Dis.


  • 0
    A

    @aqin yes it's not dijkstra, I have updated the solution.


  • 0
    A

    @ashish53v how did you detect loops?


  • 0
    Z

    @ashish53v said in Simple Java Solution using BFS (similar to dijkstra's shortest path algorithm) with explanation:

    for(int n:list){
    int v = times[n][1];
    int time = times[n][2];// time taken to reach from u to v

    does this work ? is there a statement suggests that v is connected to the index in times ?


  • 0
    A

    @AaronChiu

    this if condition (dist[v] > t + time) takes care of loops

    if there is loop, then when the node is seen second time, it will not be added to the queue again, as its distance will be bigger that what we got when we first saw it.

    See this example

    suppose we have the loop like this

    (1,2,a)
    (2,3,b)
    (3,4,c)
    (4,1,d)
    1 ->2 -> 3 -> 4 -> 2
    suppose k = 1
    we have loop of 2 3 4 2

    as 2 is the only neighbor of 1 it gets explored , we get dist[2] = a;
    then 3 gets explored (as 3 is the neighbor of 2), we get dist[3] = a + b;
    then 4 gets explored, we get dist[4] = a + b + c;

    then 1 is again seen as we have an edge from 4 to 1, but
    is (dist[v] > t + time)
    here u = 4, v = 1 and time = d and t = dist[4] = a + b + c

    is(dist[1] > d + a + b + c), no
    dist[1] is 0;

    hence 1 is not added to queue again.

    see you are going from 2 to 3 to 4 and then again 2

    when you first saw 2 you got dist[2] as say x;

    then to go to 3 dist[3] = x + something positive = x + y
    then to go to 4 dist[4] = x + y + something positive = x + y + z

    then when you again go to 2 (loop entrance point), previously dist[2] was x

    now you will check if (x > x + y + z + something positive)
    this condition will never be true, hence we take care of loop

    I hope this helps.


  • 0
    A

    @zinking
    Actually, v is not connected to times directly
    index of the time in which v is present is conncted to u.

    int u = nums[0];
    int v = nums[1];
    List<Integer> list = map.getOrDefault(u,new ArrayList<>());
                
    list.add(i);
                
    map.put(u,list);
    

    in first for loop, I traversed all nodes, and I put all the indices of times in a list and mapped it u

    basically, when I get a times[i] in this loop
    I am getting u and index i;
    I am putting the index i in a list and mapping it to u

    so, if I have these times
    (1,2,3), (1,3,4), (2,4,4)
    first I will get (1,2,3)
    u = 1, i = 0;
    so I will map 1 to [0]
    then I get (1,3,4)
    u = 1, i = 1;
    then I get list from map associated with 1 which is [0]
    add current i to this list [0,1]
    so now 1 is mapped to [0,1]
    similarly we get 2 mapped to [2]

    so when we get list mapped to m in map
    we get a list in which all the indices of times are stored in which u = m;

    I hope this helps.


  • 0
    X

    I think it is a bellman-ford algorithm inplementation


  • 0
    B

    same idea:

    class Solution {
        static class Pair {
            int dest, time;
            Pair(int dest, int time) {
                this.dest = dest;
                this.time = time;
            }
        }
    
        public int networkDelayTime(int[][] times, int N, int K) {
            Map<Integer, Set<Pair>> map = new HashMap<>();
            for (int[] time: times) {
                if (!map.containsKey(time[0]))
                    map.put(time[0], new HashSet<>());
                map.get(time[0]).add(new Pair(time[1], time[2]));
            }
            int[] dp = new int[N + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = dp[K] = 0;
            Queue<Integer> q = new LinkedList<>();
            q.offer(K);
            while (!q.isEmpty()) {
                int n = q.poll();
                if (!map.containsKey(n))
                    continue;
                for (Pair p: map.get(n)) {
                    int time = dp[n] + p.time;
                    if (dp[p.dest] > time) {
                        q.offer(p.dest);
                        dp[p.dest] = time;
                    }
                }
            }
            int delay = 0;
            for (int n: dp)
                delay = Math.max(delay, n);
            return delay == Integer.MAX_VALUE ? -1 : delay;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.