This tutorial provides Java solution to "Dijkstra: Shortest Reach 2" challenge of HackerRank.
Hackerrank Challenge Details
Problem Statement:
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
Solution Details
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<Node>{
final int id;
int distance = Integer.MAX_VALUE;
final Map<Node, Integer> 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<Node>{
final int id;
int distance = Integer.MAX_VALUE;
final Map<Node, Integer> 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<Node> 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<Node, Integer> 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.