HackerRank Dijkstra: Shortest Reach 2 problem solution

In this HackerRank Dijkstra: Shortest Reach 2 problem solution, we have 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.

Function 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

HackerRank Dijkstra: Shortest Reach 2 problem solution in Python.

from heapq import heappush, heappop
import heapq
for _ in range(int(input())):
    N,M = map(int, input().split())
    g = [[] for _ in range(N)]
    for _ in range(M):
        x,y,r = map(int,input().split())
        x,y = x-1,y-1
        g[x].append((r,y))
        g[y].append((r,x))
    S = int(input()) - 1
    paths = [-1]*N
    visited = [False]*N
    visited[S] = True
    cd = 0
    q = [(cd,S)]
    while q:
        d,c = heappop(q)
        for r,n in g[c]:
            nd = d+r
            if not visited[n]:
                visited[n] = True
                heappush(q, (nd,n))
                paths[n] = nd
            else:
                if paths[n] > nd:
                    index = q.index((paths[n],n))
                    q[index] = (nd,n)
                    heapq._siftdown(q, 0, index)
                    paths[n] = nd
                
                
                
    paths = paths[:S] + paths[S+1:]
    print(" ".join(map(str, paths)))
    

Dijkstra: Shortest Reach 2 problem solution in Java.

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

public class Solution {

    private static class Vertex {
        private final int id;
        private boolean visited;

        private Vertex(final int id) {
            this.id = id;
            visited = false;
        }

        public int getId() {
            return id;
        }

        public boolean isVisited() {
            return visited;
        }

        public void markVisited() {
            visited = true;
        }

        @Override
        public boolean equals(final Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;

            final Vertex vertex = (Vertex) o;

            if (id != vertex.id)
                return false;
            return visited == vertex.visited;

        }

        @Override
        public int hashCode() {
            int result = id;
            result = 31 * result + (visited ? 1 : 0);
            return result;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Vertex{");
            sb.append("id=").append(id);
            sb.append(", visited=").append(visited);
            sb.append('}');
            return sb.toString();
        }
    }

    private static class Edge {
        private final Vertex vertex;
        private final int weight;

        private Edge(final Vertex vertex, final int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        public Vertex getVertex() {
            return vertex;
        }

        public int getWeight() {
            return weight;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Edge{");
            sb.append("vertex=").append(vertex);
            sb.append(", weight=").append(weight);
            sb.append('}');
            return sb.toString();
        }
    }

    public static void main(String[] args) throws IOException {

        final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        final int testCases = Integer.parseInt(reader.readLine());
        for (int i = 0; i < testCases; i++) {
            final String[] nAndM = reader.readLine().split(" ");
            final int n = Integer.parseInt(nAndM[0]);
            final int m = Integer.parseInt(nAndM[1]);
            final Map<Vertex, List<Edge>> graph = new HashMap<>(n);
            final int[] distances = new int[n + 1];
            Arrays.fill(distances, Integer.MAX_VALUE);

            for (int j = 0; j < m; j++) {
                final String[] edgeDef = reader.readLine().split(" ");
                final int x = Integer.parseInt(edgeDef[0]);
                final int y = Integer.parseInt(edgeDef[1]);
                final int r = Integer.parseInt(edgeDef[2]);

                final Vertex v1 = new Vertex(x);
                final Vertex v2 = new Vertex(y);
                if (!graph.containsKey(v1)) {
                    graph.put(v1, new ArrayList<>());
                }
                if (!graph.containsKey(v2)) {
                    graph.put(v2, new ArrayList<>());
                }
                graph.get(v1).add(new Edge(v2, r));
                graph.get(v2).add(new Edge(v1, r));
            }
            final int start = Integer.parseInt(reader.readLine());
            distances[start] = 0;
            final Queue<Vertex> traversalQueue = new PriorityQueue<>((o1, o2) -> {
                return Integer.compare(distances[o1.getId()], distances[o2.getId()]);
            });
            traversalQueue.add(new Vertex(start));
            while (!traversalQueue.isEmpty()) {
                process(traversalQueue.poll(), graph, distances, traversalQueue);
            }
            printDistances(start, distances);
        }

        reader.close();
    }

    private static void process(final Vertex currentV, final Map<Vertex, List<Edge>> graph, final int[] distances,
            final Queue<Vertex> nextToProcess) {
        if (graph.containsKey(currentV)) {
            final List<Edge> edges = graph.get(currentV);
            edges.stream().forEach(e -> {
                final int distanceToNeighbor = e.getWeight() + distances[currentV.getId()];
                final Vertex neighbor = e.getVertex();
                if (distances[neighbor.getId()] > distanceToNeighbor) {
                    distances[neighbor.getId()] = distanceToNeighbor;
                }
                if (!neighbor.isVisited()) {
                    nextToProcess.add(neighbor);
                }
            });
        }
        currentV.markVisited();
    }

    private static void printDistances(final int start, final int[] distances) {
        final StringBuilder result = new StringBuilder();
        for (int i = 1; i < distances.length; i++) {
            if (i == start) {
                continue;
            }
            result.append(distances[i] == Integer.MAX_VALUE ? -1 : distances[i]);
            result.append(i < distances.length - 1 ? " " : "");
        }
        System.out.println(result.toString().trim());
    }

}

Problem solution in C++.

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

struct vcity {
    int city_id;
    int dist;
    bool operator<(vcity a) const {
        return dist > a.dist;
    }
};

struct edge {
    int dest;
    int length;
};

vector<edge> graph[10000];
priority_queue<vcity> expanded;
int dist[10001];
void setup(int N, int M) {
    for (int i = 0; i <= N; i++) {
        dist[i] = -1;
        graph[i].clear();
    }
    
    while(!expanded.empty()) {
        expanded.pop();
    }
}
int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        int N, M;
        cin >> N >> M;
        setup(N, M);
        for (int i = 0; i < M; i++) {
            edge tmp;
            int source;
            cin >> source >> tmp.dest >> tmp.length;
            graph[source].push_back(tmp);
            edge tmp2;
            tmp2.dest = source;
            tmp2.length = tmp.length;
            graph[tmp.dest].push_back(tmp2);
        }
        
        int start;
        cin >> start;
        vcity first;
        first.city_id = start;
        first.dist = 0;
        expanded.push(first);
        while (!expanded.empty()) {
            vcity curr = expanded.top();
            expanded.pop();
            if (dist[curr.city_id] == -1) {
                dist[curr.city_id] = curr.dist;
                for (int j = 0; j < graph[curr.city_id].size(); j++) {
                    int city = graph[curr.city_id][j].dest;
                    if (dist[city] == -1) {
                        vcity nxt;
                        nxt.city_id = city;
                        nxt.dist = curr.dist + graph[curr.city_id][j].length;
                        expanded.push(nxt);
                    }
                }
            }
        }
        
        for (int i = 1; i <=  N; i++) {
            if (i != start) {
                cout << dist[i] <<  " ";
            }
        }
        cout << endl;
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void dijkstra(int v, int g[][v], int root) {
    int dist[v], visited[v];
    for(int i = 0; i < v; i++) {
        dist[i] = -1;
        visited[i] = 0;
    }
    dist[root] = 0;
    int min_index = root;
    int min_dist = 0;
    visited[root] = 1;
    while(min_dist != -1) {
        visited[min_index] = 1;
        for(int i = 0; i < v; i++) {
            if(g[min_index][i] > 0) {
                if(visited[i] == 0 && (dist[i] == -1 || (dist[i] > (dist[min_index] + g[min_index][i])))) {
                    dist[i] = dist[min_index] + g[min_index][i];
                } 
            }
        }
        min_dist = -1;
        for(int k = 0; k < v; k++) {
            if(visited[k] == 0) {
                if(min_dist == -1 || (dist[k] != -1 && dist[k] < min_dist)) {
                    min_dist = dist[k];
                    min_index = k;     
                }
            }
        }
    }
    for(int j = 0; j < v; j++) {
        if(j != root) {
            printf("%d ", dist[j]);
        }
    }
    printf("n");
}

int main() {
    int t;
    scanf("%d", &t);
    for(int tc = 0; tc < t; tc++) {
        int v, e;
        scanf("%d %d", &v, &e);
        int g[v][v];
        for(int i = 0; i < v; i++) {
            for(int j = 0; j < v; j++) {
                g[i][j] = 0;
            }
        }
        for(int i = 0; i < e; i++) {
            int v1, v2, w;
            scanf("%d %d %d", &v1, &v2, &w);
            if(g[v1-1][v2-1] == 0 || g[v1-1][v2-1] > w) {
                g[v1-1][v2-1] = w;
                g[v2-1][v1-1] = w;
            }
        }
        int root;
        scanf("%d", &root);
        dijkstra(v, g, (root - 1));
    }   
    return 0;
}