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.

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)))
    

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