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.

HackerRank Breadth-First Search: Shortest Reach 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())
        graph[s].add(d)
        graph[d].add(s)
    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)))

Breadth-First Search: Shortest Reach 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<>();

        queue.add(s);
        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;
                    queue.add(u);
                }
            }
        }

        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++) {
                g.add(new Vector<>());
            }

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

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

    }
}

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;
}

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 *head;
    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->head = newNode;
        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;
    
    int ret = q->head->val;
    Node *tmp = q->head;
    q->head = q->head->next;
    free(tmp);
    q->length--;
    return ret;
}

int isEmpty(que *q){
    if(q->head == NULL)
    return 1;
    else
        return 0;
}

void BFS(int st, int adj[][1000],int len){
    int i;
    que *q = (que *)malloc(sizeof(q));
    q->head = NULL;
    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(adj[v][i] == 1 || adj[i][v] == 1){
                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);
	        adj[x-1][y-1] = 1;
	    }
	    scanf("%d",&st);
	    BFS(st-1,adj,N);
        printf("n");
    }
    return 0;
}