Single-Source Shortest Path with Negative Edges

Given a directed graph that may contain negative edge weights but no negative cycle reachable from the source, return the shortest distance from the source to the target. Pattern focus: Relaxation. This is the classic setting where repeated edge relaxation is needed because Dijkstra is not safe with negative edges.

Input Format

n = node count, edges = directed weighted edges [u, v, w], source = start node, target = destination node

Output Format

shortest distance from source to target, or -1

Constraints

  • 1 <= n <= 10^4
  • 1 <= edges.length <= 2 * 10^4
  • Weights may be negative.

Examples

Example 1:

Input:

n = 5
edges = [[0,1,4],[0,2,5],[1,2,-2],[2,3,3],[1,3,4]]
source = 0
target = 3

Output:

5

Explanation:

The path 0 -> 1 -> 2 -> 3 uses the negative edge to get a smaller total.

Example 2:

Input:

n = 4
edges = [[0,1,2],[1,2,2]]
source = 0
target = 3

Output:

-1

Explanation:

The destination is unreachable.

Example 3:

Input:

n = 3
edges = [[0,1,1],[1,2,-1],[0,2,5]]
source = 0
target = 2

Output:

0

Explanation:

The route through node 1 is cheaper than the direct edge.

Loading...
Single-Source Shortest Path with Negative Edges