BackmediumDesign

Optimal Route Calculation Solution

Problem Statement

Given a weighted graph represented as an adjacency list, find the minimum cost path from a specified source node to all other nodes in the graph.

Example 1
Input
{"graph":{"nodes":["A","B","C","D"],"edges":[{"from":"A","to":"B","cost":5},{"from":"A","to":"C","cost":2},{"from":"B","to":"D","cost":1},{"from":"C","to":"D","cost":3}]},"source":"A"}
Output
{"A":0,"B":5,"C":2,"D":5}

Explanation: The minimum cost path from node 'A' to node 'B' is A -> B with a cost of 5. The minimum cost path from node 'A' to node 'C' is A -> C with a cost of 2. The minimum cost path from node 'A' to node 'D' is A -> C -> D with a cost of 5.

Example 2
Input
{"graph":{"nodes":["E","F","G"],"edges":[{"from":"E","to":"F","cost":1},{"from":"F","to":"G","cost":4},{"from":"E","to":"G","cost":3}]},"source":"E"}
Output
{"E":0,"F":1,"G":3}

Explanation: The minimum cost path from node 'E' to node 'F' is E -> F with a cost of 1. The minimum cost path from node 'E' to node 'G' is E -> G with a cost of 3. The path E -> F -> G has a cost of 5, but the direct path E -> G is indeed cheaper.

Constraints

  • The graph may contain cycles.
  • The graph may contain self-loops.
  • All edge costs are non-negative.
  • The graph is represented as an adjacency list.
  • The source node is guaranteed to exist in the graph.

More Design Problems

Efficient Minimum Value TrackerhardOptimal Placement of Dominant EntitieshardOptimal Route Calculationmedium
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free