Find Edges in Shortest Paths - Practice Coding Problems

Find Edges in Shortest Paths - Problem

You are given an undirected weighted graph of n nodes numbered from 0 to n - 1. The graph consists of m edges represented by a 2D array edges, where edges[i] = [a_i, b_i, w_i] indicates that there is an edge between nodes a_i and b_i with weight w_i.

Consider all the shortest paths from node 0 to node n - 1 in the graph. You need to find a boolean array answer where answer[i] is true if the edge edges[i] is part of at least one shortest path. Otherwise, answer[i] is false.

Return the array answer.

Note: The graph may not be connected.

Input & Output

Example 1 — Basic Graph

$ Input: n = 4, edges = [[0,1,1],[1,3,2],[0,2,4],[2,3,1]]

› Output: [true,true,false,false]

💡 Note: Shortest path from 0 to 3 has distance 3. Path 0→1→3 uses edges [0,1,1] and [1,3,2]. Alternative path 0→2→3 has distance 5, so edges [0,2,4] and [2,3,1] are not on shortest paths.

Example 2 — Multiple Shortest Paths

$ Input: n = 4, edges = [[0,1,1],[1,3,1],[0,2,1],[2,3,1]]

› Output: [true,true,true,true]

💡 Note: Two shortest paths exist: 0→1→3 (distance 2) and 0→2→3 (distance 2). All edges participate in at least one shortest path.

Example 3 — Disconnected Graph

$ Input: n = 3, edges = [[0,1,1]]

› Output: [false]

💡 Note: No path exists from 0 to 2, so no edge can be part of a shortest path from 0 to n-1.

Constraints

2 ≤ n ≤ 1000
1 ≤ edges.length ≤ 5000
edges[i] = [a_i, b_i, w_i]
0 ≤ a_i, b_i < n
a_i ≠ b_i
1 ≤ w_i ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Weighted undirected graph with start node 0 and end node n-1

Find Shortest Paths

Use Dijkstra to compute shortest distances from both ends

Mark Valid Edges

Edge is valid if dist[0→u] + weight + dist[v→n-1] equals total shortest distance

Key Takeaway

🎯 Key Insight: An edge lies on a shortest path if the total distance through it equals the shortest path distance

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use Dijkstra's algorithm twice: once from the source and once from the destination. An edge is on a shortest path if the distance through that edge equals the shortest path distance. Best approach is Dijkstra with bidirectional check. Time: O((V + E) log V), Space: O(V + E)

Common Approaches

Approach	Time	Space	Notes
✓ Dijkstra with Path Reconstruction	O((V + E) log V)	O(V + E)	Use Dijkstra to find shortest distance, then check each edge
All Paths Enumeration	O(2^n)	O(2^n)	Find all possible paths and check which edges appear in shortest ones

Dijkstra with Path Reconstruction — Algorithm Steps

Step 1: Run Dijkstra from source (0) to get shortest distances from 0
Step 2: Run Dijkstra from destination (n-1) to get distances to n-1
Step 3: For each edge (u,v,w), check if dist0[u] + w + distn[v] equals shortest total distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Forward Dijkstra

Compute shortest distances from node 0 to all nodes

Backward Dijkstra

Compute shortest distances from node n-1 to all nodes

Edge Verification

For each edge, check if it lies on any shortest path

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>

#define MAX_NODES 1000
#define MAX_EDGES 10000

typedef struct {
    int to;
    int weight;
    int idx;
} Edge;

typedef struct {
    int node;
    int dist;
} HeapItem;

typedef struct {
    HeapItem items[MAX_NODES * 10];
    int size;
} MinHeap;

Edge graph[MAX_NODES][MAX_NODES];
int graphSize[MAX_NODES];

void heapPush(MinHeap* h, int node, int dist) {
    int pos = h->size++;
    h->items[pos].node = node;
    h->items[pos].dist = dist;
    
    while (pos > 0) {
        int parent = (pos - 1) / 2;
        if (h->items[parent].dist <= h->items[pos].dist) break;
        
        HeapItem temp = h->items[parent];
        h->items[parent] = h->items[pos];
        h->items[pos] = temp;
        pos = parent;
    }
}

HeapItem heapPop(MinHeap* h) {
    HeapItem result = h->items[0];
    h->items[0] = h->items[--h->size];
    
    int pos = 0;
    while (true) {
        int left = 2 * pos + 1;
        int right = 2 * pos + 2;
        int smallest = pos;
        
        if (left < h->size && h->items[left].dist < h->items[smallest].dist) {
            smallest = left;
        }
        if (right < h->size && h->items[right].dist < h->items[smallest].dist) {
            smallest = right;
        }
        
        if (smallest == pos) break;
        
        HeapItem temp = h->items[pos];
        h->items[pos] = h->items[smallest];
        h->items[smallest] = temp;
        pos = smallest;
    }
    
    return result;
}

void dijkstra(int start, int* dist, int n) {
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
    }
    dist[start] = 0;
    
    MinHeap heap = {0};
    heapPush(&heap, start, 0);
    
    while (heap.size > 0) {
        HeapItem current = heapPop(&heap);
        int u = current.node, d = current.dist;
        
        if (d > dist[u]) continue;
        
        for (int i = 0; i < graphSize[u]; i++) {
            Edge e = graph[u][i];
            int v = e.to, w = e.weight;
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                heapPush(&heap, v, dist[v]);
            }
        }
    }
}

bool* solution(int n, int edges[][3], int edgeCount) {
    bool* result = (bool*)calloc(edgeCount, sizeof(bool));
    
    if (n <= 1) return result;
    
    memset(graphSize, 0, sizeof(graphSize));
    
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        
        graph[u][graphSize[u]].to = v;
        graph[u][graphSize[u]].weight = w;
        graph[u][graphSize[u]].idx = i;
        graphSize[u]++;
        
        graph[v][graphSize[v]].to = u;
        graph[v][graphSize[v]].weight = w;
        graph[v][graphSize[v]].idx = i;
        graphSize[v]++;
    }
    
    int distFrom0[MAX_NODES], distToN1[MAX_NODES];
    dijkstra(0, distFrom0, n);
    dijkstra(n - 1, distToN1, n);
    
    int shortestPathDist = distFrom0[n - 1];
    
    if (shortestPathDist == INT_MAX) {
        return result;
    }
    
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        
        long long path1 = (long long)distFrom0[u] + w + distToN1[v];
        long long path2 = (long long)distFrom0[v] + w + distToN1[u];
        
        result[i] = (path1 == shortestPathDist) || (path2 == shortestPathDist);
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int edges[MAX_EDGES][3];
    int edgeCount = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        while (*ptr && *ptr != ']' && edgeCount < MAX_EDGES) {
            if (*ptr == '[') {
                ptr++;
                sscanf(ptr, "%d,%d,%d", &edges[edgeCount][0], &edges[edgeCount][1], &edges[edgeCount][2]);
                edgeCount++;
                while (*ptr && *ptr != ']') ptr++;
                if (*ptr) ptr++;
            } else {
                ptr++;
            }
        }
    }
    
    bool* result = solution(n, edges, edgeCount);
    
    printf("[");
    for (int i = 0; i < edgeCount; i++) {
        printf("%s", result[i] ? "true" : "false");
        if (i < edgeCount - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((V + E) log V)

Two Dijkstra runs, each taking O((V + E) log V) using priority queue

⚡ Linearithmic

Space Complexity

O(V + E)

Distance arrays, priority queue, and adjacency list storage

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dijkstra with Path Reconstruction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler