Table of Contents
Dijkstra: Shortest Reach 2 – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class node{
public:
int val;
int dis;
int vis ;
int add;
long int edist;
node *next;
node(int n, node *ptr, long int edist){
val = n;
this->edist = edist;
dis = -1;
vis = 0;
add = 0;
next = ptr;
}
};
void breadth(node **adj,node *queue,node *last,long int *dist){
if(queue!=NULL){
node *temp = adj[queue->val];
while(temp!=NULL){
if(dist[temp->val]==-1 || dist[temp->val] > dist[queue->val]+temp->edist){
dist[temp->val] = dist[queue->val] + temp->edist;
node *ptr = new node(temp->val, NULL, 0);
last->next = ptr;
last = ptr;
}
temp = temp->next;
}
queue = queue->next;
/*
cout<<"queue\n";
temp = queue;
while(temp !=NULL){
cout<<temp->val+1<<" ";
temp = temp->next;
}
cout<<endl;
*/
breadth(adj,queue,last,dist);
}
}
int main() {
long int t;
cin>>t;
while(t--){
long int n,m;
cin>>n;
node *adj[n];
for(long int i=0;i<n;i++){
adj[i] = NULL;
}
cin>>m;
for(long int i=0;i<m;i++){
long int x, y, z;
cin>>x>>y>>z;
node *ptr = new node(x-1,adj[y-1],z);
adj[y-1] = ptr;
ptr = new node(y-1,adj[x-1],z);
adj[x-1] = ptr;
}
/* cout<<"printing queue"<<endl;
for(long int i=0;i<n;i++){
node *ptr = adj[i];
while(ptr!=NULL){
cout<<ptr->val+1<<" + " <<ptr->edist<<" ";
ptr = ptr->next;
}
cout<<endl;
}
*/
long int s;
cin>>s;
s = s-1;
node *queue, *last;
node *ptr = new node(s,NULL,0);
long int dist[n];
for(long int i=0;i<=n;i++)
dist[i] = -1;
dist[s] = 0;
queue = ptr;
last = ptr;
breadth(adj,queue,last, dist);
for(long int i=0;i<n;i++){
if(i!=s){
cout<<dist[i]<<" ";
}
}
cout<<endl;
}
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Node implements Comparable<Node>{
int val, cost;
Node(int val, int cost){
this.val = val; this.cost = cost;
}
public int compareTo(Node x){
return Integer.compare(this.cost, x.cost);
}
}
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int n = sc.nextInt(), m = sc.nextInt();
ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>(n+1);
for(int i=0; i<n+1; i++)adj.add(new ArrayList<Node>(n+1));
while(m-- > 0){
int x = sc.nextInt(), y = sc.nextInt(), cost = sc.nextInt();
adj.get(x).add(new Node(y, cost));
adj.get(y).add(new Node(x, cost));
}
int s = sc.nextInt();
djikstra(s, adj, n);
}
}
static void djikstra(int s, ArrayList<ArrayList<Node>> adj, int n){
int[] dist = new int[n+1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[s] = 0;
PriorityQueue<Node> pq = new PriorityQueue<Node>();
pq.add(new Node(s, 0));
while(pq.size() > 0){
Node curr = pq.peek(); pq.remove();
int currN = curr.val;
Iterator<Node> it = adj.get(currN).iterator();
while(it.hasNext()){
Node temp = it.next();
if(dist[temp.val] > dist[currN] + temp.cost){
pq.add(new Node(temp.val, dist[currN]+temp.cost));
dist[temp.val] = dist[currN] + temp.cost;
}
}
}
for(int i=1; i<dist.length; i++){
if(i!=s){
System.out.print(((dist[i] == Integer.MAX_VALUE)?-1:dist[i]) + " ");
}
}
System.out.println();
}
}
Python 3 Dijkstra: Shortest Reach 2 HackerRank Solution
import heapq
def find(V,N,S):
dist=[-1 for x in range(N)]
visited=[False for x in range(N)]
Q=[(0,S)] #use a priority queue
dist[S]=0
while Q:
mindist,minv=heapq.heappop(Q)
if not visited[minv]:
for x in V[minv]:
if dist[x] == -1: dist[x]=mindist+V[minv][x]
else: dist[x]=min(dist[x],mindist+V[minv][x])
heapq.heappush(Q,(dist[x],x))
visited[minv]=True
del dist[S]
for x in dist: print(x,end=' ')
print()
def update(V,X,Y,R):
if Y not in V[X]: V[X][Y]=R
else: V[X][Y]=min(V[X][Y],R)
T=int(input())
for _ in range(T):
N,M=(int(x) for x in input().split())
V=[dict() for x in range(N)]
for i in range(M):
X,Y,R=(int(x) for x in input().split())
X,Y=X-1,Y-1
update(V,X,Y,R)
update(V,Y,X,R)
find(V,N,int(input())-1)
Python 2 Dijkstra: Shortest Reach 2 HackerRank Solution
def killdoubles(l):
i=0
a=l[i]
ll=[a]
while i<len(l):
if a!=l[i]:
a=l[i]
ll.append(a)
i+=1
return ll
def argminnonmarque(l,m):
mini=min([l[i] for i in range(len(l)) if not(m[i])])
for i in range(len(l)):
if ((l[i]==mini) & (not(m[i]))):
break
return i
def subs(a,l):
i=0
dont=False
while i<len(l):
if l[i][0]==a[0]:
if l[i][1]>a[1]:
break
dont=True
i+=1
ll=[list(k) for k in l]
if i<len(l):
ll[i]=a
elif not(dont):
ll.append(a)
return ll
def solve(n,m,r,s):
G=[[] for _ in range(n+1)]
for [i,j,w] in r:
G[i]=subs([j,w],G[i])
G[j]=subs([i,w],G[j])
infinity=1+sum([r[i][2] for i in range(m)])
for debut in [s]:
marque=[False for _ in range(n+1)]
labels=[infinity for _ in range(n+1)]
labels[debut]=0
while marque!=[True for _ in range(n+1)]:
a=argminnonmarque(labels,marque)
marque[a]=True
for [b,w] in G[a]:
if not(marque[b]):
labels[b]=min(labels[b],labels[a]+w)
for i in range(n+1):
if labels[i]==infinity:
labels[i]=-1
st=""
for i in (labels[1:s]+labels[s+1:]):
st+=str(i)+" "
return st
T=int(raw_input())
for _ in range(T):
[n,m]=map(int,raw_input().strip().split())
r=[]
for _ in range(m):
r.append(map(int,raw_input().strip().split()))
s=int(raw_input())
print(solve(n,m,r,s))
C Dijkstra: Shortest Reach 2 HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define FROM 0
#define TO 1
#define LENGTH 2
#define DISTANCE 0
#define STATUS 1
#define SPENT 0
#define PENDING 1
int edge[3000*(3000-1)/2+1][3]; // [edge][FROM/TO/LENGTH]
int main() {
int cases, nodes, edges, origin, active, neighbor, i;
unsigned int mindist;
int node[3000+1][2]; // [node][DISTANCE/STATUS]
scanf("%d", &cases);
while(cases--){
scanf("%d %d", &nodes, &edges);
for(i=1; i <= edges; i++){
scanf("%d %d %d", &edge[i][FROM], &edge[i][TO], &edge[i][LENGTH]);
}
for(i=1; i <= nodes; i++){
node[i][DISTANCE] = -1; //infinity
node[i][STATUS] = PENDING;
}
scanf("%d", &origin);
active = origin;
node[origin][DISTANCE] = 0;
while(active){
for(i=1; i<=edges; i++){
if(edge[i][FROM]==active){
neighbor = edge[i][TO];
}
else if(edge[i][TO]==active){ //test graph is actually undirected
neighbor = edge[i][FROM];
}
else continue;
if(node[neighbor][DISTANCE] == -1){
node[neighbor][DISTANCE] = node[active][DISTANCE] + edge[i][LENGTH];
}
else if( node[neighbor][DISTANCE] > node[active][DISTANCE] + edge[i][LENGTH] ){
node[neighbor][DISTANCE] = node[active][DISTANCE] + edge[i][LENGTH];
}
}
node[active][STATUS] = SPENT;
active = 0;
mindist = -1; //unsigned
for(i=1; i <= nodes; i++){ //activate closest unchecked node
if( node[i][STATUS] == PENDING && node[i][DISTANCE] < mindist ){
mindist = node[i][DISTANCE];
active = i;
}
}
}
for(i=1; i<=nodes; i++){
if(i!=origin)printf("%i ", node[i][DISTANCE]);
}
printf("\n");
}
return 0;
}
Leave a comment below
