Medium · Graphs

Find Shortest Path with Dijkstra's

Given an undirected graph with n nodes and weighted edges [u, v, w] (w ≥ 0), passed to the solution as adjacency lists of (next, weight) pairs, and a source node src, return dist where dist[i] is the length of the shortest path from src to node i (2⁶³ − 1 for unreachable nodes); an example's target only picks the route the animation traces.

Examples

Example 1

{
  "n": 6,
  "edges": [
    [0, 1, 2],
    [0, 5, 10],
    [1, 2, 2],
    [1, 4, 5],
    [2, 3, 1],
    [3, 5, 3],
    [4, 5, 1],
    [2, 4, 6]
  ],
  "src": 0,
  "target": 5,
  "pos": [
    [36, 140],
    [105, 48],
    [175, 48],
    [250, 48],
    [210, 248],
    [330, 140]
  ]
}

Output: dist [0, 2, 4, 5, 7, 8]

Example 2

{
  "n": 5,
  "edges": [
    [4, 2, 1],
    [2, 0, 1],
    [4, 1, 6],
    [2, 1, 4],
    [0, 3, 1],
    [1, 3, 1],
    [2, 3, 5]
  ],
  "src": 4,
  "target": 1,
  "pos": [
    [308, 44],
    [110, 242],
    [176, 44],
    [242, 242],
    [44, 44]
  ]
}

Output: dist [2, 4, 1, 3, 0]

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.