LeetCode 3123 - Find Edges in Shortest Paths

The problem gives us an undirected weighted graph with n nodes and m edges. Each edge connects two nodes and has a positive weight. We need to determine which edges belong to at least one shortest path from node 0 to node n - 1.

leetcodeharddepth-first-searchbreadth-first-searchgraph-theoryheap-(priority-queue)shortest-path

LeetCode Problem 3123

Difficulty: 🔴 Hard
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Shortest Path

Solution

LeetCode 3123 - Find Edges in Shortest Paths

Problem Understanding

The problem gives us an undirected weighted graph with n nodes and m edges. Each edge connects two nodes and has a positive weight. We need to determine which edges belong to at least one shortest path from node 0 to node n - 1.

The important detail is that we are not looking for just one shortest path. There may be many shortest paths with the same minimum total distance. An edge should be marked as true if it appears in at least one of those shortest paths.

The input graph is represented as an edge list:

edges[i] = [ai, bi, wi]

This means there is an undirected edge between ai and bi with weight wi.

The output is a boolean array of length m, where:

  • answer[i] = true means edge i participates in at least one shortest path from 0 to n - 1
  • answer[i] = false means it never appears in any shortest path

The graph may not be connected, which means there may be no path from node 0 to node n - 1. In that case, every answer is false because no shortest path exists.

The constraints are large:

  • Up to 5 * 10^4 nodes
  • Up to 5 * 10^4 edges

These limits immediately rule out expensive graph algorithms such as all-pairs shortest paths or repeated recomputation for every edge. Since all weights are positive, Dijkstra's algorithm is the natural candidate for shortest path computation.

Several edge cases are important:

  • The destination node may be unreachable
  • Multiple shortest paths may exist
  • An edge may connect nodes that are individually reachable but still not belong to any shortest path
  • The graph can contain cycles
  • The shortest path may revisit regions through different equal-cost routes

A correct solution must efficiently identify every edge that satisfies the shortest path condition.

Approaches

Brute Force Approach

A brute-force solution would examine every edge independently.

For each edge, we could force that edge to appear in a path from 0 to n - 1 and check whether the resulting path length equals the true shortest distance.

One possible implementation would:

  1. Compute the shortest distance from 0 to n - 1
  2. For every edge (u, v, w):
  • Compute shortest path from 0 to u
  • Add edge weight w
  • Compute shortest path from v to n - 1
  • Also try the reverse direction because the graph is undirected
  • Check whether either total equals the shortest distance

The issue is that this requires repeated shortest path computations. Running Dijkstra once costs O((V + E) log V). Repeating it for every edge becomes far too expensive.

With up to 5 * 10^4 edges, this approach is completely impractical.

Key Insight

The key observation is that an edge belongs to some shortest path if and only if it satisfies the shortest path distance equation.

Suppose:

  • distFromStart[x] is the shortest distance from node 0 to node x
  • distFromEnd[x] is the shortest distance from node n - 1 to node x
  • shortest = distFromStart[n - 1]

For an edge (u, v, w) to lie on a shortest path, one of these must hold:

distFromStart[u] + w + distFromEnd[v] == shortest

or

distFromStart[v] + w + distFromEnd[u] == shortest

Why does this work?

If the first equation holds, then:

  • We can travel optimally from 0 to u
  • Use edge (u, v)
  • Then travel optimally from v to n - 1

The total distance equals the shortest possible distance, so this edge appears in a shortest path.

This means we only need:

  • One Dijkstra from the source
  • One Dijkstra from the destination
  • A linear scan over all edges

That is efficient enough for the constraints.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(E × (V + E) log V) O(V + E) Runs shortest path repeatedly for each edge
Optimal O((V + E) log V) O(V + E) Two Dijkstra runs plus one edge scan

Algorithm Walkthrough

Step 1: Build the Adjacency List

Convert the edge list into an adjacency list because Dijkstra's algorithm works efficiently with adjacency lists.

For every edge:

[u, v, w]

store:

u -> (v, w)
v -> (u, w)

Since the graph is undirected, both directions are required.

Step 2: Run Dijkstra from Node 0

Compute the shortest distance from node 0 to every other node.

Store the result in:

distFromStart

We use a min-heap priority queue because edge weights are positive.

This gives us the minimum cost to reach every node from the source.

Step 3: Run Dijkstra from Node n - 1

Now run Dijkstra again, this time starting from node n - 1.

Store the result in:

distFromEnd

This gives us the minimum cost from every node to the destination.

Because the graph is undirected, running Dijkstra backward is equivalent to computing distances to the destination.

Step 4: Determine the Global Shortest Distance

The shortest path from 0 to n - 1 is:

shortest = distFromStart[n - 1]

If this value is infinity, the destination is unreachable. In that case, return an array of all false.

Step 5: Check Every Edge

For each edge (u, v, w):

Check whether:

distFromStart[u] + w + distFromEnd[v] == shortest

or:

distFromStart[v] + w + distFromEnd[u] == shortest

If either condition holds, the edge belongs to at least one shortest path.

Why it works

Dijkstra guarantees that distFromStart[x] and distFromEnd[x] are optimal shortest distances.

If an edge satisfies:

distFromStart[u] + w + distFromEnd[v] == shortest

then there exists:

  • An optimal path from 0 to u
  • The edge (u, v)
  • An optimal path from v to n - 1

Combining them creates a complete shortest path containing that edge.

Conversely, if an edge belongs to a shortest path, then splitting that path around the edge must satisfy exactly this equation. Therefore the condition is both necessary and sufficient.

Python Solution

from typing import List
import heapq

class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        graph = [[] for _ in range(n)]

        for idx, (u, v, w) in enumerate(edges):
            graph[u].append((v, w))
            graph[v].append((u, w))

        def dijkstra(start: int) -> List[int]:
            INF = float('inf')
            dist = [INF] * n
            dist[start] = 0

            min_heap = [(0, start)]

            while min_heap:
                current_dist, node = heapq.heappop(min_heap)

                if current_dist > dist[node]:
                    continue

                for neighbor, weight in graph[node]:
                    new_dist = current_dist + weight

                    if new_dist < dist[neighbor]:
                        dist[neighbor] = new_dist
                        heapq.heappush(min_heap, (new_dist, neighbor))

            return dist

        dist_from_start = dijkstra(0)
        dist_from_end = dijkstra(n - 1)

        shortest_path = dist_from_start[n - 1]

        if shortest_path == float('inf'):
            return [False] * len(edges)

        answer = []

        for u, v, w in edges:
            in_shortest_path = (
                dist_from_start[u] + w + dist_from_end[v] == shortest_path
                or
                dist_from_start[v] + w + dist_from_end[u] == shortest_path
            )

            answer.append(in_shortest_path)

        return answer

The implementation begins by constructing an adjacency list. Each node stores its neighboring nodes and corresponding edge weights. This representation allows Dijkstra's algorithm to efficiently traverse only connected edges.

The dijkstra helper function computes shortest distances from a given starting node. The algorithm uses a min-heap priority queue where each entry contains the current distance and node index.

When a node is extracted from the heap, we skip outdated entries using:

if current_dist > dist[node]:
    continue

This optimization avoids unnecessary work caused by stale heap entries.

For each neighboring edge, we compute a candidate distance. If it improves the known shortest distance, we update the distance array and push the new state into the heap.

After running Dijkstra twice, once from node 0 and once from node n - 1, we know the optimal distance from both directions.

Finally, each edge is checked against the shortest path equation. If either direction satisfies the condition, the edge is part of at least one shortest path.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type Edge struct {
	to     int
	weight int
}

type State struct {
	dist int
	node int
}

type MinHeap []State

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].dist < h[j].dist
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(State))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func dijkstra(start int, graph [][]Edge) []int {
	n := len(graph)

	dist := make([]int, n)

	for i := 0; i < n; i++ {
		dist[i] = math.MaxInt64
	}

	dist[start] = 0

	minHeap := &MinHeap{}
	heap.Init(minHeap)

	heap.Push(minHeap, State{dist: 0, node: start})

	for minHeap.Len() > 0 {
		current := heap.Pop(minHeap).(State)

		if current.dist > dist[current.node] {
			continue
		}

		for _, edge := range graph[current.node] {
			newDist := current.dist + edge.weight

			if newDist < dist[edge.to] {
				dist[edge.to] = newDist
				heap.Push(minHeap, State{
					dist: newDist,
					node: edge.to,
				})
			}
		}
	}

	return dist
}

func findAnswer(n int, edges [][]int) []bool {
	graph := make([][]Edge, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]
		w := edge[2]

		graph[u] = append(graph[u], Edge{to: v, weight: w})
		graph[v] = append(graph[v], Edge{to: u, weight: w})
	}

	distFromStart := dijkstra(0, graph)
	distFromEnd := dijkstra(n-1, graph)

	shortestPath := distFromStart[n-1]

	answer := make([]bool, len(edges))

	if shortestPath == math.MaxInt64 {
		return answer
	}

	for i, edge := range edges {
		u := edge[0]
		v := edge[1]
		w := edge[2]

		if distFromStart[u]+w+distFromEnd[v] == shortestPath ||
			distFromStart[v]+w+distFromEnd[u] == shortestPath {
			answer[i] = true
		}
	}

	return answer
}

The Go implementation follows the same algorithmic structure as the Python version, but Go requires explicit heap implementation using the container/heap package.

A custom MinHeap type implements the heap interface methods:

  • Len
  • Less
  • Swap
  • Push
  • Pop

Distances are initialized using math.MaxInt64 to represent infinity.

Slices are used for adjacency lists and distance arrays. Since Go does not have Python's built-in priority queue, we explicitly maintain heap operations through the standard library heap interface.

Worked Examples

Example 1

Input:

n = 6

edges = [
    [0,1,4],
    [0,2,1],
    [1,3,2],
    [1,4,3],
    [1,5,1],
    [2,3,1],
    [3,5,3],
    [4,5,2]
]

Step 1: Dijkstra from Node 0

Final distances:

Node Distance from 0
0 0
1 4
2 1
3 2
4 7
5 5

So:

shortest = 5

Step 2: Dijkstra from Node 5

Node Distance to 5
0 5
1 1
2 4
3 3
4 2
5 0

Step 3: Check Every Edge

Edge Formula Result In Shortest Path
(0,1,4) 0 + 4 + 1 = 5 True
(0,2,1) 0 + 1 + 4 = 5 True
(1,3,2) 2 + 2 + 1 = 5 True
(1,4,3) 4 + 3 + 2 = 9 False
(1,5,1) 4 + 1 + 0 = 5 True
(2,3,1) 1 + 1 + 3 = 5 True
(3,5,3) 2 + 3 + 0 = 5 True
(4,5,2) 7 + 2 + 0 = 9 False

Final answer:

[true, true, true, false, true, true, true, false]

Example 2

Input:

n = 4

edges = [
    [2,0,1],
    [0,1,1],
    [0,3,4],
    [3,2,2]
]

Step 1: Dijkstra from Node 0

Node Distance
0 0
1 1
2 1
3 3

Shortest path length:

3

Step 2: Dijkstra from Node 3

Node Distance
0 3
1 4
2 2
3 0

Step 3: Evaluate Edges

Edge Formula Result
(2,0,1) 0 + 1 + 2 = 3 True
(0,1,1) 0 + 1 + 4 = 5 False
(0,3,4) 0 + 4 + 0 = 4 False
(3,2,2) 1 + 2 + 0 = 3 True

Final answer:

[true, false, false, true]

Complexity Analysis

Measure Complexity Explanation
Time O((V + E) log V) Two Dijkstra runs dominate the complexity
Space O(V + E) Adjacency list, heap, and distance arrays

The graph contains up to 5 * 10^4 vertices and edges, making adjacency lists the correct representation. Each Dijkstra traversal processes every edge and heap operation costs O(log V). Since we run Dijkstra twice, the overall complexity remains within acceptable limits.

The space complexity comes from:

  • The adjacency list storing all edges
  • Two distance arrays
  • The priority queue used during Dijkstra

Test Cases

from typing import List

class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        import heapq

        graph = [[] for _ in range(n)]

        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        def dijkstra(start):
            dist = [float('inf')] * n
            dist[start] = 0

            heap = [(0, start)]

            while heap:
                d, node = heapq.heappop(heap)

                if d > dist[node]:
                    continue

                for nei, w in graph[node]:
                    nd = d + w

                    if nd < dist[nei]:
                        dist[nei] = nd
                        heapq.heappush(heap, (nd, nei))

            return dist

        dist_start = dijkstra(0)
        dist_end = dijkstra(n - 1)

        shortest = dist_start[n - 1]

        if shortest == float('inf'):
            return [False] * len(edges)

        result = []

        for u, v, w in edges:
            result.append(
                dist_start[u] + w + dist_end[v] == shortest or
                dist_start[v] + w + dist_end[u] == shortest
            )

        return result

sol = Solution()

# Example 1
assert sol.findAnswer(
    6,
    [[0,1,4],[0,2,1],[1,3,2],[1,4,3],
     [1,5,1],[2,3,1],[3,5,3],[4,5,2]]
) == [True, True, True, False, True, True, True, False]

# Example 2
assert sol.findAnswer(
    4,
    [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]
) == [True, False, False, True]

# Single edge graph
assert sol.findAnswer(
    2,
    [[0,1,5]]
) == [True]

# Unreachable destination
assert sol.findAnswer(
    4,
    [[0,1,1],[2,3,1]]
) == [False, False]

# Multiple equal shortest paths
assert sol.findAnswer(
    4,
    [[0,1,1],[1,3,1],[0,2,1],[2,3,1]]
) == [True, True, True, True]

# Extra heavy edge not in shortest path
assert sol.findAnswer(
    3,
    [[0,1,1],[1,2,1],[0,2,10]]
) == [True, True, False]

# Cycle graph
assert sol.findAnswer(
    5,
    [[0,1,1],[1,2,1],[2,3,1],[3,4,1],[0,4,10],[1,3,2]]
) == [True, True, True, True, False, False]

# Equal weights with branching
assert sol.findAnswer(
    5,
    [[0,1,2],[0,2,2],[1,4,2],[2,4,2],[1,2,1]]
) == [True, True, True, True, False]

Test Summary

Test Why
Example 1 Validates multiple shortest paths
Example 2 Validates unique shortest path
Single edge graph Smallest connected graph
Unreachable destination Ensures all false when no path exists
Multiple equal shortest paths Confirms all valid edges are marked
Extra heavy edge Ensures non-optimal edges are excluded
Cycle graph Tests behavior in cyclic structures
Equal weights with branching Validates tie handling

Edge Cases

One important edge case occurs when the destination node is unreachable. In this situation, the shortest distance remains infinity after Dijkstra completes. A buggy implementation might still attempt edge comparisons using infinite values, leading to incorrect results. This implementation explicitly checks for unreachable destinations and immediately returns an array of all false.

Another important case is when multiple shortest paths exist. Many incorrect solutions only reconstruct one shortest path and mark those edges. That approach misses edges belonging to alternative shortest paths with the same total distance. This solution avoids that issue entirely by using the shortest path equality condition, which correctly identifies every valid edge.

Graphs containing cycles are also dangerous. A naive DFS-based shortest path search can repeatedly revisit nodes and become inefficient or incorrect. Dijkstra's algorithm safely handles cycles because it always processes nodes in increasing distance order and ignores stale heap entries.

A final subtle edge case involves undirected edges. Since an edge can be traversed in either direction, both equations must be checked:

distStart[u] + w + distEnd[v]

and

distStart[v] + w + distEnd[u]

Failing to check both directions would incorrectly reject valid shortest path edges.