Given a weighted undirected graph with V vertices (0 .. V-1) and edges edges[i] = [u, v, w] (non-negative w), return the vertices of a minimum-weight path from source 0 to target V-1, in order. If several minimum-weight paths exist, choosing the smallest predecessor at each vertex makes the path deterministic. Return [-1] if V-1 is unreachable.
Input: V = 4, edges = [[0,1,1],[1,2,1],[0,2,2],[2,3,1]] Output: [0, 2, 3] 0→2→3 has weight 3; 2's smaller predecessor 0 is chosen over 1.
Input: V = 4, edges = [[0,1,2],[2,3,3]] Output: [-1] Vertex 3 is unreachable from 0.
- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - 1 <= w <= 10^9 - no negative weights
Finding the shortest distance is Dijkstra; printing the path just adds a parent pointer. Whenever you relax an edge u → v that improves dist[v], record parent[v] = u. After Dijkstra finishes, walk parents backward from the target to the source and reverse.
To make the answer unique when multiple shortest paths exist, break ties toward the smaller predecessor: on an equal-distance relaxation, keep parent[v] as the smaller of the candidates. Because every predecessor on a shortest path settles strictly before v (weights are positive), this rule is order-independent — the array-scan and min-heap versions produce the same path.
“Which path if several are shortest?”
The one built by taking the smaller predecessor on ties.
“If the target is unreachable?”
Return [-1].
I run Dijkstra while recording a parent for each vertex, then reconstruct by walking parents from the target back to the source.
On equal-distance ties I keep the smaller predecessor so the path is deterministic.
Worked example — V = 4, edges [[0,1,1],[1,2,1],[0,2,2],[2,3,1]]
dist = [0,1,2,3]; parents: 1<-0, 2<-1 (or 0; pick smaller 0), 3<-2 0->... 2's smaller predecessor is 0 -> path 0 -> 2 -> 3
Records the shortest-path tree.
From target to source, then reverse.
Makes the path unique and order-independent.
| Dijkstra scan + parent | Dijkstra heap + parent | |
|---|---|---|
| Find closest | linear scan | min-heap |
| Time | O(V²) | O((V+E) log V) |
| Path | parent pointers | parent pointers |
Both reconstruct the same path from the same parent tree. Full code is in the Approaches selector below.
Key takeaway
Run Dijkstra, recording a parent per vertex (smaller predecessor on ties). Walk parents from V-1 back to 0 and reverse. Return [-1] if unreachable.
on relaxing u->v to a better dist: parent[v]=u reconstruct: target -> ... -> source via parents, reversed
