Find the Shortest Distance in a Weighted Undirected Graph

Problem Statement

You are given an undirected graph represented by a list of edges, where each edge [u, v, w] indicates a path between node u and node v with weight w. Your task is to find the shortest path distance between a starting node start and an ending node end.

If there is no path between the two nodes, return -1.

Function Signature

def shortest_path(n, edges, start, end) -> int:

Constraints

• n: Number of nodes, indexed from 0 to n-1 (1 <= n <= 10^5).
• edges: A list of lists, where each inner list contains [u, v, w] (0 <= u, v < n, 1 <= w <= 1000).
• edges can contain up to 2 * 10^5 elements.

Examples

Example 1: Input: n = 3, edges = [[0, 1, 5], [1, 2, 2], [0, 2, 10]], start = 0, end = 2 Output: 7 Explanation: The path 0 -> 1 -> 2 has weight 5 + 2 = 7, which is shorter than the direct edge 0 -> 2 with weight 10.

Example 2: Input: n = 4, edges = [[0, 1, 1]], start = 0, end = 3 Output: -1 Explanation: There is no path between node 0 and node 3.

Edge Cases

• Start node equals end node (distance should be 0).
• Disconnected graph components.
• Graphs with multiple edges between the same two nodes (keep the one with the minimum weight).