Find Edges in Shortest Paths

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] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi.

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 that the graph may not be connected.

Example1:
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]]

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

Explanation:

The following are all the shortest paths between nodes 0 and 5:

The path 0 -> 1 -> 5: The sum of weights is 4 + 1 = 5.
The path 0 -> 2 -> 3 -> 5: The sum of weights is 1 + 1 + 3 = 5.
The path 0 -> 2 -> 3 -> 1 -> 5: The sum of weights is 1 + 1 + 2 + 1 = 5.

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

Output: [true,false,false,true]
Copy

import java.util.Arrays;

class Solution {
    public static boolean[]  findAnswer(int n, int[][] edges) {
       boolean[] res = new boolean[edges.length];
        Arrays.fill(res, true);
        return res;
    }

    public static void main(String[] args) {
        boolean test = true;
        int[][] 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}};

        boolean[] ans1 = findAnswer(edges.length, edges);
        test = test && Arrays.equals(ans1, new boolean[]{true,true,true,false,true,true,true,false});


        int[][] edges2 = {{2,0,1},{0,1,1},{0,3,4},{3,2,2}};

        boolean[] ans2 = findAnswer(edges2.length, edges2);
        test = test && Arrays.equals(ans2, new boolean[]{true,true,true,false,true,true,true,false});

        if(test){
            System.out.println("test pass");
        }else {
            System.out.println("Test fail");
        }
    }
}
Copy

Solution

import java.util.*;

class Solution {

    class Edge {
        int node;
        int weight;

        Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    public boolean[] findAnswer(int n, int[][] edges) {
        // Initialize graph as an array of lists
        List<Edge>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(new Edge(edge[1], edge[2]));
            graph[edge[1]].add(new Edge(edge[0], edge[2]));
        }

        // Dijkstra's algorithm to find the shortest path distances
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.offer(new Edge(0, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int currentNode = current.node;
            int currentWeight = current.weight;

            if (currentWeight > dist[currentNode]) continue;

            for (Edge neighbor : graph[currentNode]) {
                int newDist = dist[currentNode] + neighbor.weight;
                if (newDist < dist[neighbor.node]) {
                    dist[neighbor.node] = newDist;
                    pq.offer(new Edge(neighbor.node, newDist));
                }
            }
        }

        // Use a HashSet to track edges that are part of any shortest path
        Set<Long> shortestPathEdges = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n - 1);

        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            for (Edge neighbor : graph[currentNode]) {
                if (dist[currentNode] - neighbor.weight == dist[neighbor.node]) {
                    long edgeKey = encodeEdge(neighbor.node, currentNode);
                    if (!shortestPathEdges.contains(edgeKey)) {
                        shortestPathEdges.add(edgeKey);
                        queue.add(neighbor.node);
                    }
                }
            }
        }

        // Generate the final answer
        boolean[] answer = new boolean[edges.length];
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1];
            long edgeForward = encodeEdge(u, v);
            long edgeBackward = encodeEdge(v, u);
            answer[i] = shortestPathEdges.contains(edgeForward) || shortestPathEdges.contains(edgeBackward);
        }

        return answer;
    }

    private long encodeEdge(int u, int v) {
        return ((long) u << 32) | (v & 0xFFFFFFFFL);
    }

    public static void main(String[] args) {

        Solution solution = new Solution();

        boolean test = true;
        int[][] 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}};

        boolean[] ans1 = solution.findAnswer(6, edges);
        test = test && Arrays.equals(ans1, new boolean[]{true, true, true, false, true, true, true, false});

        int[][] edges2 = {{2, 0, 1}, {0, 1, 1}, {0, 3, 4}, {3, 2, 2}};

        boolean[] ans2 = solution.findAnswer(4, edges2);
        test = test && Arrays.equals(ans2, new boolean[]{true,false,false,true});

        if (test) {
            System.out.println("test pass");
        } else {
            System.out.println("Test fail");
        }
    }
}
Copy

Reference

• leetcode