PreviousNext
Coding/Graphs and trees

Shortest path weighted graph

Write codeMedium35 minGoogle and Uber style

Your task

Given a directed weighted graph with n nodes (0..n-1) and edges as [u, v, w] with w >= 0, return the length of the shortest path from node src to node dst. If dst is unreachable from src, return -1. There may be multiple edges between the same pair; use the one giving the shorter total. Self-loops may appear and should be ignored as they never help.

Examples

dijkstra_shortest(n: int, edges: list[list[int]], src: int, dst: int) -> int
Example 1
Inputdijkstra_shortest(5, [[0, 1, 4], [0, 2, 1], [2, 1, 1], [1, 3, 1], [3, 4, 3]], 0, 4)
Output6