HackerRank Dijkstra: Shortest Reach 2 Solution

In this post, we will solve HackerRank Dijkstra: Shortest Reach 2 Problem Solution.

Given an undirected graph and a starting node, determine the lengths of the shortest paths from the starting node to all other nodes in the graph. If a node is unreachable, its distance is -1. Nodes will be numbered consecutively from 1 to n, and edges will have varying distances or lengths.

For example, consider the following graph of 5 nodes:

Begin	End	Weight
1	2	5
2	3	6
3	4	2
1	3	15

Starting at node 1, the shortest path to 2 is direct and distance 5. Going from 1 to 3, there are two paths: 1 →2→ 3 at a distance of 5+ 6 = 11 or 1 → 3 at a distance of 15. Choose the shortest path, 11. From 1 to 4, choose the shortest path through 3 and extend it: 1→2→34 for a distance of 11 + 2 = 13 There is no route to node 5, so the distance is -1.
The distances to all nodes in increasing node order, omitting the starting node, are 5 11 13
-1.

unction Description

Complete the shortestReach function in the editor below. It should return an array of integers that represent the shortest distance to each node from the start node in ascending order of node number.

shortestReach has the following parameter(s):

n: the number of nodes in the graph
edges: a 2D array of integers where each edges[i] consists of three integers that represent the start and end nodes of an edge, followed by its length
s: the start node number

Input Format
The first line contains t, the number of test cases.
Each test case is as follows:
-The first line contains two space-separated integers n and m, the number of nodes and edges in the graph.

Each of the next m lines contains three space-separated integers x, y, and r, the beginning and ending nodes of an edge, and the length of the edge.
The last line of each test case has an integers, denoting the starting position.

Output Format
For each of the t test cases, print a single line consisting – 1 space separated integers denoting the shortest distance to the n – 1 nodes from starting position & in increasing order of their labels, excluding s.
For unreachable nodes, print -1.

Sample Input

Sample Output

24 3 15

Explanation

The lines are weighted edges where weight denotes the length of the edge.
The shortest paths followed for the three nodes 2, 3 and 4 are as follows:
1/S->2 – Shortest Path Value: 24
1/S->3 – Shortest Path Value: 3
1/S->3->4 – Shortest Path Value: 15

HackerRank Dijkstra: Shortest Reach 2 Problem Solution

Dijkstra: Shortest Reach 2 C Solution

#include<stdio.h>
#define N 5000000
long int i,j,k,t,tt;
long int V, E;
long int visited[N], sptset[N], dist[N], src[2*N], dest[2*N], wt[2*N];

int mindis(){
	long int min;
	min=1000; long int minp, p,q;
	for(p=0;p<V;p++){
		if(sptset[p]==0 && min>dist[p]){
			min=dist[p];
			minp=p;
		}
		
	}
	return minp;
}
int main(){
	long int source, u, s, d, w;
	scanf("%ld", &t);
	for(tt=1;tt<=t;tt++){
		scanf("%ld %ld", &V, &E);
		for(i=0;i<2*E;i++){
			scanf("%ld %ld %ld", &s, &d, &wt[i]);
			src[i]=s-1;dest[i]=d -1;
			i++;
			src[i]=d-1;dest[i]=s -1; wt[i]=wt[i-1];
		}
		scanf("%ld", &source);
		for(i=0;i<V;i++){
			dist[i]=1000;
			sptset[i]=0;
		}
		dist[source-1]=0;
		
		for(i=0;i<V-1;i++){
			u = mindis();
			sptset[u]=1;
			for(j=0;j<2*E;j++){
				if(src[j]==u){
					s=src[j];d=dest[j];w=wt[j];
					if(sptset[d]==0 && dist[d]>dist[s]+ w)
						dist[d] = dist[s]+w;
				}
			}
		}
			
			
			
			for(i=0;i<V;i++){
				if(dist[i] && dist[i]!=1000)
				printf("%ld ", dist[i]);
                if(dist[i]==1000)
                    printf("-1 ");
			}

			printf("\n");
		
		
		
		
		
	}
	
	
}

Dijkstra: Shortest Reach 2 C++ Solution

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

// graph by adjacency list
template <typename T>
struct Edge {
  int dst; T weight;
  Edge(int dst, T weight) : dst(dst), weight(weight) { }
  bool operator < (const Edge<T> &e) const {
    return weight > e.weight;
  }
};

template <typename T>
struct Graph {
  int V;
  vector<vector<Edge<T>>> E;
  Graph(int V) : V(V) { E.resize(V); }
  void add_edge(int src, int dst, T weight) {
    E[src].emplace_back(dst, weight);
  }
};

#define INF INT_MAX

template <typename T>
struct Node {
  int v; T dist;
  Node(int v, T dist) : v(v), dist(dist) { };
  bool operator < (const Node<T> &n) const {
    return dist > n.dist; // reverse
  }
};

template <typename T>
struct ShortestPath {
  const Graph<T> g;
  vector<T> dist;
  vector<int> prev;

  ShortestPath(const Graph<T> g) : g(g) { dist.resize(g.V), prev.resize(g.V); }

  void dijkstra(int start) {
    priority_queue<Node<T>> que;
    dist.assign(g.V, INF);
    dist[start] = 0;
    que.emplace(start, 0);
    prev[0] = -1;

    while (!que.empty()) {
      Node<T> n = que.top(); que.pop();
      int v = n.v; T cost = n.dist;
      if (dist[v] < cost) continue;
      for (Edge<T> e : g.E[v]) {
        if (dist[v] < dist[e.dst] - e.weight) {
          dist[e.dst] = dist[v] + e.weight;
          prev[e.dst] = v;
          que.emplace(e.dst, dist[e.dst]);
        }
      }
    }
  }

  vector<int> build_path(int goal) {
    vector<int> path;
    for (int v = goal; v != -1; v = prev[v]) {
      path.emplace_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
  }
};


int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int T; cin >> T;
  REP(_, T) {
    int V, E; cin >> V >> E;
    Graph<int> g(V);
    REP(_, E) {
      int s, t, r; cin >> s >> t >> r; s--, t--;
      g.add_edge(s, t, r);
      g.add_edge(t, s, r);
    }
    ShortestPath<int> sp(g);
    int s; cin >> s; s--;
    sp.dijkstra(s);
    if (s != V-1) {
      REP(i, V) if (i != s) cout << (sp.dist[i] == INF ? -1 : sp.dist[i]) << (i == V-1 ? '\n' : ' ');
    } else {
      REP(i, V-1) cout << (sp.dist[i] == INF ? -1 : sp.dist[i]) << (i == V-2 ? '\n' : ' ');
    }
  }

  return 0;
}

Dijkstra: Shortest Reach 2 C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    class Edge{
        public int Y;        
        public int Weight;
        
        public Edge(){
            
        }
    }
    class Node{
        public bool Processed;
        public int Distance;
        public Node Parent;
        
        public List<Edge> edges;
        
        public Node(){
            edges = new List<Edge>();            
            Processed = false;
            Distance = Int32.MaxValue;             
        }
    }
    
    static void djikstra(int startNode, IList<int>[,] edges, Node[] nodes, int numOfNodes){
        var node = new Node{Distance = 0};
        var nodeIndx = startNode-1;                        
        while(!node.Processed){
            node.Processed = true;
            nodes[nodeIndx] = node;
            
            for(var i=0; i<numOfNodes;i++){
                if (edges[nodeIndx, i].Count>0){
                    foreach(var edgeWeight in edges[nodeIndx, i]){
                        node.edges.Add(new Edge{ Y = i+1, Weight = edgeWeight});                                                                              
                        if (nodes[i].Distance > node.Distance+edgeWeight){
                            nodes[i].Distance = node.Distance+edgeWeight;
                            nodes[i].Parent = node;
                        }
                            
                    }
                    
                                        
                }                    
            }
            
            var dist = Int32.MaxValue;            
            for (var i=0;i<numOfNodes;i++){
                if (!nodes[i].Processed && (dist > nodes[i].Distance)){
                    dist = nodes[i].Distance;
                    node = nodes[i];
                    nodeIndx = i;
                }
            }                        
        }        
        return;
    }
    
    static void TestCase(){
        var line1 = Console.ReadLine().Split(' ');
        var numOfNodes = Convert.ToInt32(line1[0]);
        var numOfEdges = Convert.ToInt32(line1[1]);
        
        var nodes = new Node[numOfNodes];        
        var edges = new List<int>[numOfNodes, numOfNodes];
        for(var i=0;i<numOfNodes;i++){
            nodes[i] = new Node();
            for(var j=0;j<numOfNodes;j++)
                edges[i,j] = new List<int>();
        }
        
        for(var iEdge = 1; iEdge<=numOfEdges; iEdge++){
            var edgeLine = Console.ReadLine().Split(' ');
            var x = Convert.ToInt32(edgeLine[0]);
            var y = Convert.ToInt32(edgeLine[1]);
            var w = Convert.ToInt32(edgeLine[2]);
            
            if (!edges[x-1,y-1].Contains(w))
                edges[x-1,y-1].Add(w);            
            if (!edges[y-1,x-1].Contains(w))
                edges[y-1,x-1].Add(w);            
        }
        
        var startNode = Convert.ToInt32(Console.ReadLine());
                        
        djikstra(startNode, edges, nodes, numOfNodes);
        
        for(var i = 0;i<numOfNodes;i++){
            if (nodes[i].Distance == Int32.MaxValue)
                nodes[i].Distance = -1;
            
            if (i!=(startNode-1))
                Console.Write("{0} ", nodes[i].Distance);
        }
        Console.WriteLine("");
        
    }
    
    static void Main(String[] args) {
        var numTestCases = Convert.ToInt32(Console.ReadLine());
        for (var itest=1;itest<=numTestCases;itest++){
            TestCase();                
        }
    }
}

Dijkstra: Shortest Reach 2 Java Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Result
{
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            if (st == null || !st.hasMoreElements ()) {
                do {
                    try {
                        st = new StringTokenizer (br.readLine ());
                    } catch (IOException e) {
                        e.printStackTrace ();
                    }
                } while (st == null || !st.hasMoreElements ());
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) {
        FastReader in=new FastReader();//creating the object
        int t1=in.nextInt();//taking input of the number of testcases to be solved
        for(int gj=0;gj<t1;gj++){//taking input of hte odes ad edges
            int n=in.nextInt();
            int m=in.nextInt();
            long w[][]=new long [n+1][n+1];
            for (long[] row: w)
                Arrays.fill(row, 1000000l);
            IntStream.range (0, m).forEach (i -> {
                int x = in.nextInt (), y = in.nextInt ();
                long cmp = in.nextLong ();
                if (w[x][y] > cmp) {
                    w[x][y] = cmp;
                    w[y][x] = cmp;
                }
            });
            Stack <Integer> t=new Stack<Integer>();
            int src=in.nextInt();
            for(int i=1;i<=n;i++){
                if(i!=src){t.push(i);}}
            Stack <Integer> p=new Stack<Integer>();
            p.push(src);
            w[src][src]=0;
            if (!t.isEmpty ()) {
                do {
                    int min = 989997979, loc = -1;
                    for (int i = 0; i < t.size (); i++) {
                        w[src][t.elementAt (i)] = Math.min (w[src][t.elementAt (i)], w[src][p.peek ()] + w[p.peek ()][t.elementAt (i)]);
                        if (w[src][t.elementAt (i)] <= min) {
                            min = (int) w[src][t.elementAt (i)];
                            loc = i;
                        }
                    }
                    p.push (t.elementAt (loc));
                    t.removeElementAt (loc);
                } while (!t.isEmpty ());
            }
            int i=1;
            while (i<=n) {
                if(i!=src && w[src][i]!=1000000l){System.out.print(w[src][i]+" ");}
                else if(i!=src){System.out.print("-1"+" ");}
                i++;
            }
            System.out.println();
        }
    }}

Dijkstra: Shortest Reach 2 JavaScript Solution

function lessThan(a, b) {
    if (a == -1) return false
    else if (b == -1) return true;
    else return a < b;
}

function PriorityQueue() {
    this.heapIndex = [];
    this.dist = [];
    this.heap = [];
}

PriorityQueue.prototype.populate = function (list) {
    this.heap = list;
    for (var i = 0; i < list.length; i++) {
        this.heapIndex[list[i]] = i;
    }
}

PriorityQueue.prototype.insert = function (value) {
    var i = this.heap.length;
    this.heap.push(value);
    this.heapIndex[value] = i;
    this.lowerPriority(value);
}

PriorityQueue.prototype.lowerPriority = function (value) {
    var i = this.heapIndex[value];
    while (i != 0 && lessThan(this.dist[this.heap[i]], this.dist[this.heap[Math.trunc((i - 1) / 2)]])) {
        var parentIndex = Math.trunc((i - 1) / 2) ;
        var parentValue = this.heap[parentIndex];
        this.heap[parentIndex] = value;
        this.heap[i] = parentValue;
        this.heapIndex[value] = parentIndex;
        this.heapIndex[parentValue] = i;
        i = parentIndex;
    }
}

PriorityQueue.prototype.isFull = function () {
    return this.heap.length != 0;
}

PriorityQueue.prototype.peek = function () {
    return this.heap[0];
}

PriorityQueue.prototype.takeLowest = function () {
    var result = this.heap[0];
    this.heapIndex[result] = null;
    var i = 0;
    while (i * 2 + 1 < this.heap.length) {
        var left = i * 2 + 1;
        var right = i * 2 + 2;
        if (right >= this.heap.length || lessThan(this.dist[this.heap[left]], this.dist[this.heap[right]])) {
            this.heap[i] = this.heap[left];
            this.heapIndex[this.heap[i]] = i;
            i = left;
        } else {
            this.heap[i] = this.heap[right];
            this.heapIndex[this.heap[i]] = i;
            i = right;
        }
    }
    if (i != this.heap.length - 1) {
        var last = this.heap.pop();
        this.heap[i] = last;
        this.heapIndex[last] = i;
    } else {
        this.heap.pop();
    }
    return result;
}

function processData(input) {
    var inputLines = input.split("\n");
    var t = Number(inputLines[0]);
    var j = 1;
    for (i = 0; i < t; i++) {
        var edges = [];
        var nm = inputLines[j].split(" ");
        var n = Number(nm[0]);
        for (var k = 0; k < n; k++) {
            edges[k] = [];
        }
        var m = Number(nm[1]);
        j++;
        for (var k = 0; k < m; k++) {
            var v1v2w = inputLines[j].split(" ").map(Number);
            var v1 = v1v2w[0];
            var v2 = v1v2w[1];
            var w = v1v2w[2];
            edges[v1 - 1].push({dest: v2 - 1, weight: w});
            edges[v2 - 1].push({dest: v1 - 1, weight: w});
            j++;
        }
        var starting = Number(inputLines[j]) - 1;
        j++;
        
        var q = new PriorityQueue();
        var initial = [];
        for (var k = 0; k < n; k++) {
            q.dist[k] = -1;
            initial[k] = k;
        }
        q.dist[starting] = 0;
        q.populate(initial);
        q.lowerPriority(starting);
        while (q.isFull() && q.dist[q.peek()] != -1) {
            var current = q.takeLowest();
            var neighbors = edges[current];
            for (var l = 0; l < neighbors.length; l++) {
                var dest = neighbors[l].dest;
                var weight = neighbors[l].weight;
                if (lessThan((q.dist[current] + weight), q.dist[dest])) {
                    q.dist[dest] = q.dist[current] + weight;
                    q.lowerPriority(dest);
                }
            }
        }
        var result = "";
        for (var l = 0; l < q.dist.length; l++) {
            if (l == starting) continue;
            if (result != "") result += " ";
            result += q.dist[l];
        }
        console.log(result);
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Dijkstra: Shortest Reach 2 Python Soluton

from collections import OrderedDict
from collections import defaultdict


class Graph:

    def __init__(self):
        self.neighbors = defaultdict(set)
        self.vertices = list()

    def add_edge(self, start, end, distance):
        self.neighbors[start].add((end, distance))
        self.neighbors[end].add((start, distance))


def dijkstra(graph, start):
    # value to represent infinity
    infinity = object()
    # distances
    distances = OrderedDict()
    for vertex in graph.vertices:
        distances[vertex] = infinity
    distances[start] = 0

    # XXX: create trampoline
    trampoline = list()

    def compute(current):
        # XXX: global variables are used
        for neighbor, distance in graph.neighbors[current]:
            # replace distance with the shortest distance
            new = distances[current] + distance
            if (distances[neighbor] is infinity or distances[neighbor] > new):  # noqa
                distances[neighbor] = new
                trampoline.append(neighbor)

    # boostrap
    trampoline.append(start)
    # ignite trampoline
    while trampoline:
        vertex = trampoline.pop(0)
        compute(vertex)

    # remove start node
    distances = list(distances.values())
    distances.pop(start - 1)
    return map(lambda x: -1 if x is infinity else x, distances)


T = int(input())


for _ in range(T):
    graph = Graph()

    N, M = map(int, input().split())
    for name in range(1, N + 1):
        graph.vertices.append(name)

    for _ in range(M):
        start, end, distance = map(int, input().split())
        graph.add_edge(start, end, distance)

    S = int(input())
    print(' '.join(map(str, dijkstra(graph, S))))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python