HackerRank Breadth-First Search: Shortest Reach problem solution

In this HackerRank Breadth-First Search: Shortest Reach problem solution Consider an undirected graph where each edge weighs 6 units. Each of the nodes is labeled consecutively from 1 to n.

You will be given a number of queries. For each query, you will be given a list of edges describing an undirected graph. After you create a representation of the graph, you must determine and report the shortest distance to each of the other nodes from a given starting position using the breadth-first search algorithm (BFS). Return an array of distances from the start node in node number order. If a node is unreachable, return -1 for that node.

Problem solution in Python.

def bfs_paths(graph, start, goal):
queue = [(start,[start])]
while queue:
v, path = queue.pop(0)
for next in graph[v] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))

def shortest_path(graph, start, goal):
if len(graph[start])==0 or len(graph[goal])==0:
return -1
try:
return 6*(len(next(bfs_paths(graph, start, goal)))-1)
except StopIteration:
return -1

t = int(input())

for tt in range(t):
ret = []
n,m = map(int, input().split())
graph = dict((i,set()) for i in range(1,n+1))
for mm in range(m):
s,d = map(int, input().split())
start = int(input())

for a in list(x for x in range(1,n+1) if x != start):
ret.append(shortest_path(graph, start, a))
print(' '.join(map(str, ret)))

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

static void bfs(Vector<Vector<Integer>> g, int s) {

int n = g.size();

int[] dist = new int[g.size()];

for (int i = 0; i < n; i++) {
dist[i] = n;
}

dist[s] = 0;

boolean[] used = new boolean[g.size()];
Arrays.fill(used, false);

Vector<Integer> queue = new Vector<>();

used[s] = true;

for (int i = 0; i < queue.size(); i++) {
queue.get(i);

int v = queue.get(i);

for (int u : g.get(v)) {
if (!used[u]) {
used[u] = true;
dist[u] = dist[v] + 1;
}
}
}

for (int i = 0; i < dist.length; i++) {
if (dist[i] != 0) {
if (dist[i] == n) {
System.out.print(-1 + " ");
} else {
System.out.print((dist[i] * 6) + " ");
}
}
}

}

public static void main(String[] args) {

Vector<Vector<Integer>> g = new Vector<Vector<Integer>>();

Scanner in = new Scanner(System.in);

int t = in.nextInt();

for (int i = 0; i < t; i++) {
int n = in.nextInt();

for (int c = 0; c < n; c++) {
}

int m = in.nextInt();
for (int k = 0; k < m; k++) {
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
}

int s = in.nextInt() - 1;
bfs(g,s);
g.clear();
System.out.println();
}

}
}

{"mode":"full","isActive":false}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include<limits>
using namespace std;

struct entity
{
int node;
int weight;
};

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T, N , M, from, to, s;
entity e, e1;
cin >> T;
for(int i= 0; i < T; i++)
{
cin >> N >> M;
vector<vector<int>> aList(N);
vector<int> output(N,numeric_limits<int>::max());
vector<int> finished(N, -1);
vector<int>::iterator it;
for(int i = 0 ; i < M; i++)
{
cin >> from >> to;
it = find (aList[from-1].begin(), aList[from-1].end(), to -1);
if (it == aList[from-1].end())
{
aList[from-1].push_back(to - 1);
aList[to-1].push_back(from - 1);
}
}
cin >> s;
output[s-1] = 0;
//     cout << s << endl;
queue<entity> myqueue;
/*      for(int i = 0 ; i < N; i++)
{
cout << i << "\t";
for(int j = 0; j < aList[i].size(); j++)
{
cout << aList[i][j] << " ";
}
cout << endl;
}*/
for(int v : aList[s-1])
{
// cout << v;
e.node = v;
e.weight = 6;
myqueue.push(e);

}
finished[s-1] = 1;
while (!myqueue.empty())
{

e = myqueue.front();
//cout << e.node << " " << e.weight << endl;
if (e.weight < output[e.node])
{
output[e.node] = e.weight;
}
finished[e.node] = 1;
myqueue.pop();
for(int v: aList[e.node])
{
if(finished[v] != 1)
{
e1.node = v;
e1.weight = 6 + e.weight;
myqueue.push(e1);
}
}
}
for( int i = 0 ; i < output.size() ;  i++)
{
if(i!= s-1)
{
if( output[i]!= numeric_limits<int>::max())
cout << output[i] << " ";
else
cout << -1 << " ";
}
}
cout << endl;
}
return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void solve();
void BFS(int, int a[][1000], int);

typedef struct LLNode{
struct LLNode *next;
int val;
}Node;

typedef struct Queue{
Node *tail;
int length;
}que,queue;

int enqueue(que *q, int val);
int dequeue(que *q);
int isEmpty(que *q);

/*
* RETURN
* -1 -> failed to enqueue
*  0 -> successfully enqueued
*/
int enqueue(que *q, int val){

Node *newNode = (Node *)malloc(sizeof(Node));
if(!newNode)
return -1;
newNode->next = NULL;
newNode->val= val;
if(isEmpty(q)){
q->tail = newNode;
q->length++;
} else {
q->tail->next = newNode;
q->tail = newNode;
q->length++;
}
return 0;
}

int dequeue(que *q){
if(isEmpty(q))
return -1;

free(tmp);
q->length--;
return ret;
}

int isEmpty(que *q){
return 1;
else
return 0;
}

void BFS(int st, int adj[][1000],int len){
int i;
que *q = (que *)malloc(sizeof(q));
q->length = 0;
q->tail = NULL;
enqueue(q,st);
int *dist = (int *)malloc(sizeof(int)*len);
for(i=0;i<len;i++)
dist[i] = -1;
dist[st] = 0;
while(!isEmpty(q)){
int v = dequeue(q);
for(i=0;i<len;i++){
if(dist[i] != -1 && dist[v] + 6 < dist[i]){
dist[i] = dist[v] + 6;
enqueue(q,i);
}
else if(dist[i] == -1){
dist[i] = dist[v] + 6;
enqueue(q,i);
}
}
}
}
for(i=0;i<len;i++){
if(i != st){
printf("%d ",dist[i]);
}
}
free(dist);
free(q);
}

int main() {

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int i,T = 0;
scanf("%d",&T);
for(i = 0; i<T;i++){
int st,i,N,M,x,y;
scanf("%d",&N);
scanf("%d",&M);
int adj[1000][1000] = {0};// = (int **)calloc(N*N,(sizeof(int)));
for(i=0;i<M;i++){
scanf("%d",&x);
scanf("%d",&y);
}
scanf("%d",&st);