Dijkstra Shortest Path

Given a directed, weighted graph with n nodes labeled 0 to n-1, and an edge list edges where each edge is [u, v, w] representing an edge from u to v with weight w (w > 0), return the shortest distance from src to every node.

If a node is unreachable, return -1 for that node.

Function signature

func DijkstraShortestPath(n int, edges [][]int, src int) []int

Examples

Example 1:

Input: n = 5,
       edges = [[0,1,2],[0,2,5],[1,2,1],[1,3,2],[2,3,1],[3,4,3]],
       src = 0
Output: [0,2,3,4,7]

Example 2:

Input: n = 3, edges = [[0,1,4]], src = 0
Output: [0,4,-1]

Constraints

• 1 <= n <= 10^5
• 0 <= edges.length <= 2*10^5
• 0 <= u, v < n
• 1 <= w <= 10^6

Hints

1. Build an adjacency list and use a min-heap (priority queue).
2. Standard Dijkstra: pop the smallest distance, relax neighbors.
3. Ignore outdated heap entries (if distance > current best).

Notes

• All weights are positive, so Dijkstra is valid.
• The graph is directed; add both directions if you want undirected behavior.