Given a directed, weighted graph with non-negative edge weights, return the minimum
total weight of a path from start to target, or -1 if unreachable.
minPath(graph, start, target)
Each Edge has a To string and a Weight int. Use Dijkstra's algorithm.
Input format: edges | start | target, edges as a,b,w triples (a → b with weight
w).
edges a,b,1 b,c,2 a,c,5, start a, target c // → 3 (a→b→c)
edges a,b,1, start a, target z // → -1
With unweighted graphs, fewest-edges and cheapest-path are the same thing, so BFS suffices. Here edges have different weights, so fewest hops isn't necessarily cheapest — a two-hop path with small weights can beat a one-hop path with a large weight. You need an algorithm that accounts for accumulated cost, not hop count.
Maintain a best-known cost for every node, 0 for the source, infinity elsewhere. The central claim: among all not-yet-finalized nodes, the one with the smallest tentative distance right now already has its true shortest distance. Any other path to it would pass through some other unfinalized node, but every unfinalized node currently has a distance at least as large, and non-negative weights mean continuing along any path only adds cost, never subtracts. So no detour through a currently-more-expensive node could end up cheaper. This only holds because weights are non-negative — negative edges break the argument, which is why Bellman-Ford exists for those graphs.
Always finalizing the currently-cheapest reachable node ensures you never finalize before discovering a cheaper route — any cheaper alternative would pass through a node that's even cheaper still, which would have been finalized first. This greedy strategy, run to completion, produces exact shortest distances to every reachable node.
def min_path(graph, start, target):
dist = {node: float("inf") for node in graph}
dist[start] = 0
visited = set()
while True:
# Pick the unvisited node with the smallest tentative distance.
cur = ""
best = float("inf")
for node in dist:
if node not in visited and dist[node] < best:
best = dist[node]
cur = node
if cur == "":
break
visited.add(cur)
for to, weight in graph.get(cur, []):
nd = dist[cur] + weight
if nd < dist.get(to, float("inf")):
dist[to] = nd
d = dist.get(target)
return d if d is not None and d < float("inf") else -1
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.