Shortest Path Coding | Dataford Interview Questions

Shortest Path Coding

EasyPython

Problem

PayPal Checkout services are represented as a directed graph, where each edge connects two services and has a nonnegative processing cost. Given a source service and a destination service, return the minimum total cost and the corresponding route.

Implement Dijkstra's algorithm with a min-heap. The route must include the source and destination in order. If the destination cannot be reached, return [-1, []].

Formal Specification

Implement shortest_path(n, edges, source, target).

n is an integer representing nodes numbered from 0 through n - 1.
edges is a list of [from_node, to_node, cost] records representing directed edges.
source and target are integer node identifiers.
Return [minimum_cost, path], where minimum_cost is an integer and path is a list of node identifiers.
If multiple minimum-cost paths exist, returning any one of them is acceptable.

Constraints

1 <= n <= 100000
0 <= len(edges) <= 200000
0 <= from_node, to_node < n
0 <= cost <= 10^9
Parallel directed edges may exist
All edge costs are nonnegative

Function Signature

def shortest_path(n, edges, source, target):

Implement Dijkstra's algorithm with a min-heap. The route must include the source and destination in order. If the destination cannot be reached, return [-1, []].

Formal Specification

Implement shortest_path(n, edges, source, target).

n is an integer representing nodes numbered from 0 through n - 1.
edges is a list of [from_node, to_node, cost] records representing directed edges.
source and target are integer node identifiers.
Return [minimum_cost, path], where minimum_cost is an integer and path is a list of node identifiers.
If multiple minimum-cost paths exist, returning any one of them is acceptable.