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