Dijkstra shortest reach 2 hackerrank solution

Hackerrank - Dijkstra Shortest Reach 2

I got stuck at TestCase 7 (the only one I failed) which I thought was my fault. I downloaded the test case and checked against my output generated.

I do git diff and I can't see any difference between them. Can you help me verify what happened to my code?

Or perhaps if there isn't a catch in my code, I would like to alter the question:

Does HackerRank Platform often has bugs?

I often encountered an obscure failure (usually last one or two out of 13 testcases) when doing a HackerRank Challenge for my job interview, hence failed multiple times at these. I wonder if any of you has similar experience. My suspicion is that when I checked my submitted code with friends, we can't find any edge cases or bugs. It should be perfect. As programmer who had been coding in LeetCode, this terrifies me and I started to train on HackerRank.

Please advise. Thanks

Resource:

P.S in the google drive folder, I attached my output: output_me.txt and the ground truth output: output.txt. I did add new lines for both output (initially, all answer are in one long line, added new lines to make it easier to read.)

Code:

import os from collections import defaultdict from heapq import heappop, heappush MAX_INT = 2**31 # Build Graph def buildGraph(edges): graph = defaultdict(list) trackMinEdge = {} # build min edges from u - v (adjacent) # for handling duplicate edges for u, v, weight in edges: u, v = min(u, v), max(u, v) if (u, v) in trackMinEdge: minWeight = trackMinEdge[(u, v)] if minWeight <= weight: # do not update continue # only update if (u, v) not in trackMinWeight # or the new weight is smaller than minWeight trackMinEdge[(u, v)] = weight # build graph from minimum adjancent edge for u, v in trackMinEdge: weight = trackMinEdge[(u, v)] graph[u].append((weight, v)) graph[v].append((weight, u)) return graph # DJIKSTRA def djikstra(n, graph, src, dest=None): dists = {} # setups seen = set() queue = [(0, src)] dists[src] = 0 while queue: dist_u, u = heappop(queue) if u in seen: continue seen.add(u) for weight, v in graph.get(u, []): if v in seen: continue alt = dists[u] + weight if alt < dists.get(v, MAX_INT): dists[v] = alt heappush(queue, (alt, v)) return dists # Complete the shortestReach function below. def shortestReach(n, edges, src): graph = buildGraph(edges) # edge cases: src not connected to any node if not (src in graph): return [-1 for _ in range(n-1)] dists = djikstra(n, graph, src) distsTable = [] for i in range(1, n+1): if i in dists and i != src: distsTable.append(dists[i]) elif not (i in dists): distsTable.append(-1) return distsTable if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w+') t = int(input()) for t_itr in range(t): nm = input().split() n = int(nm[0]) m = int(nm[1]) edges = [] for _ in range(m): edges.append(list(map(int, input().rstrip().split()))) s = int(input()) result = shortestReach(n, edges, s) fptr.write(' '.join(map(str, result))) fptr.write('\n') fptr.close()

Regards,

Me

HackerRank Solution: Dijkstra Shortest Reach 2

Published on: 25th May 2018

This tutorial provides Java solution to "Dijkstra: Shortest Reach 2" challenge of HackerRank.

Given a graph consisting N nodes (labelled 1 to N) where a specific given node S represents the starting position S and an edge between two nodes is of a given length, which may or may not be equal to other lengths in the graph.

It is required to calculate the shortest distance from the start position (Node S) to all of the other nodes in the graph.

Note: If a node is unreachable , the distance is assumed as -1.

Input Format:

The first line contains T, denoting the number of test cases. 
First line of each test case has two integers N, denoting the number of nodes in the graph and M, denoting the number of edges in the graph.

The next M lines each consist of three space-separated integers x y r, where x and y denote the two nodes between which the undirected edge exists, r denotes the length of edge between these corresponding nodes.

The last line has an integer S, denoting the starting position.

Output Format:

For each of the T test cases, print a single line consisting N - 1 space separated integers denoting the shortest distance of N - 1 nodes other than S from starting position S in increasing order of their labels.

For unreachable nodes, print -1.

Constraints:

•  1 < T < 10
•  2 < N < 3000
•  1 < M < N X (N - 1) / 2
•  1 < x,y,S < N
•  1 < r < 350

If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges.

Sample Input:

1 4 4 1 2 24 1 4 20 3 1 3 4 3 12 1

Sample Output:

24 3 15

Explanation:

The graph given in the test case is shown as :

• The straight line is a weighted edge, denoting length of edge between the corresponding nodes.
• The nodes S,B,C and D denote the obvious node 1,2,3 and 4 in the test case.

The shortest paths followed for the three nodes B,C and D are as follows :

S->B - Shortest Path Value : 24

S->C - Shortest Path Value : 3

S->C->D - Shortest Path Value : 15

We will be using adjacency lists for modeling the nodes of our graph. In this model, each of the node will have list of nodes it is linked to along with the distance. Here is how our Node structure will look like with id, distance from source Node and linkedNodes- 

/** * Represents Node of the graph and contains node id along with the nodes and distance that are attached to it. */ private static class Node implements Comparable{ final int id; int distance = Integer.MAX_VALUE; final Map linkedNodes = new HashMap<>(); private Node(int id) { this.id = id; } /** * Links the input node to this node by adding it to linkedNodes list. */ private void addLinkedNode(Node node, Integer distance) { linkedNodes.put(node, distance); } @Override public int compareTo(Node o) { return this.distance - o.distance; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + id; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Node other = (Node) obj; if (id != other.id) return false; return true; } }

We also have added hashCode, equals and compareTo method as we will be using PriorityQueue to keep distance for each node. In order to do this, we define equality based on id so that we don't add two records with same id. However, we want to sort the Nodes on the basis of their distances so we use distance field in compareTo method.

Now here is the complete Java implemenation of this algorithm - 

package com.saintech.allprogtutorials.hackerrank.algos; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Map.Entry; import java.util.PriorityQueue; import java.util.Scanner; /** * @author Sain Technology Solutions * * Solution to Problem - https://www.hackerrank.com/challenges/dijkstrashortreach * */ public class DijkstraShortestReach2 { /** * Represents Node of the graph and contains node id along with the nodes and distance that are attached to it. */ private static class Node implements Comparable{ final int id; int distance = Integer.MAX_VALUE; final Map linkedNodes = new HashMap<>(); private Node(int id) { this.id = id; } /** * Links the input node to this node by adding it to linkedNodes list. */ private void addLinkedNode(Node node, Integer distance) { linkedNodes.put(node, distance); } @Override public int compareTo(Node o) { return this.distance - o.distance; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + id; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Node other = (Node) obj; if (id != other.id) return false; return true; } } /** * Updates distances of nodes in input array with the distance from input source node. */ private static void updateNodeDistances(Node[] graphNodes, int source) { // Create priority queue instance and add all the graphNodes to priority queue. Since compareTo of nodes // is based on distance, it will order graph nodes in increasing order of distances final PriorityQueue pQ = new PriorityQueue<>(); pQ.addAll(Arrays.asList(graphNodes)); //Since distance of sourceNode from sourceNode is 0, we will need to update the distance of sourceNode to 0 // as initially distance of all nodes are set to max integer value. final Node sourceNode = graphNodes[source]; // Since Java implementation of priority queue doesn't allow mechanism to update the priority once it is added. // Moreover it becomes unstable if attributes used in compareTo are changed after addition. // In order to work this, we remove sourceNode, update distance and then re-insert it. pQ.remove(sourceNode); // This requires id based equals implementation in Node structure sourceNode.distance = 0; pQ.add(sourceNode); while(!pQ.isEmpty()) { final Node node = pQ.poll(); // For each of linkedNodes of this node for(Entry linkedNodeEntry : node.linkedNodes.entrySet()) { final Node linkedNode = linkedNodeEntry.getKey(); final int linkedNodeEdgeWeight = linkedNodeEntry.getValue(); // calculated distance of linked node from source node will be addition of distance of this node from // source and weight of edge between this node and linked node int targetDistance = node.distance + linkedNodeEdgeWeight; if(!(node.distance == Integer.MAX_VALUE) && targetDistance < linkedNode.distance) { // If target calculated distance is less than linkedNode's current distance, we need to update this // linked node's priority so we do same ritual of removing, updating and re-inserting! pQ.remove(linkedNode); linkedNode.distance = targetDistance; pQ.offer(linkedNode); } } } } public static void main(String[] args) { final Scanner in = new Scanner(System.in); int T = in.nextInt(); // For each test case while(T-- > 0) { final int N = in.nextInt(); final int M = in.nextInt(); final Node[] graphNodes = new Node[N]; for(int j = 0; j < M; j++) { // Subtract 1 out of first node id to fit this into our graph elements as array index starts with 0 final int x = in.nextInt() - 1; // If node is present in array, fetch it, otherwise create a new instance of Node and put in array Node xNode = graphNodes[x]; if(xNode == null) { xNode = new Node(x); graphNodes[x] = xNode; } // Subtract 1 out of second node id to fit this into our graph elements as array index starts with 0 final int y = in.nextInt() - 1; // If node is present in array, fetch it, otherwise create a new instance of Node and put in array Node yNode = graphNodes[y]; if(yNode == null) { yNode = new Node(y); graphNodes[y] = yNode; } final int r = in.nextInt(); // Since there could be multiple edges between two nodes, we will just keep the smallest one if(xNode.linkedNodes.get(yNode) == null || xNode.linkedNodes.get(yNode) > r ) { // Since graph is undirected, we set both nodes into each other's linked nodes to have a bi-directional mapping xNode.addLinkedNode(yNode, r); yNode.addLinkedNode(xNode, r); } } // Subtract 1 out of start node id to fit this into our graph elements as array index starts with 0 final int S = in.nextInt() - 1; updateNodeDistances(graphNodes, S); for(Node node : graphNodes) { if(node.distance != 0) { System.out.print((node.distance == Integer.MAX_VALUE ? -1 : node.distance) + " "); } } System.out.println(); } in.close(); } }

Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.

Published on: 25th May 2018