Compute Single-Source Shortest Paths Solution
Problem Statement
You are given a directed, weighted graph represented by `n` vertices, labeled from `0` to `n-1`, and a list of `edges`. Each `edge` is given as a triplet `[u, v, weight]`, indicating a directed edge from vertex `u` to vertex `v` with a non-negative `weight`. You are also given an integer `source`, representing the starting vertex. Your task is to find the shortest distance from the `source` vertex to all other vertices in the graph. The shortest distance to a vertex is the minimum sum of edge weights along any path from the `source` to that vertex. If a vertex is unreachable from the `source`, its distance should be considered `-1`. Return an array `distances` of size `n`, where `distances[i]` is the shortest distance from `source` to vertex `i`.
Examples
Constraints
- `1 <= n <= 100`
- `0 <= edges.length <= n * (n - 1)`
- `0 <= u, v < n`, `u != v`
- `0 <= weight <= 1000`
- `0 <= source < n`
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
import heapq
def solve():
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
adj = [[] for _ in range(n)]
for _ in range(m):
u, v, weight = map(int, sys.stdin.readline().split())
adj[u].append((v, weight))
source = int(sys.stdin.readline())
distances = [float('inf')] * n
distances[source] = 0
pq = [(0, source)] # (distance, vertex)
while pq:
dist, u = heapq.heappop(pq)
# If we found a shorter path to u already, skip
if dist > distances[u]:
continue
for v, weight in adj[u]:
if distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
heapq.heappush(pq, (distances[v], v))
# Convert float('inf') to -1 for unreachable vertices
result = []
for d in distances:
if d == float('inf'):
result.append(-1)
else:
result.append(int(d)) # Ensure integer output
print(result)
solve()