Find Edges in Shortest Paths

Shortest Path, Dijkstra’s algorithm, Backtracking

Original Link

Solution

In this problem, we should find the shortest path from 0 to n-1 and all edges that can be used as the shortest path.

If you track all the paths while getting the shortest path, this problem seems complicated. We are not sure the current path is the shortest path until we reach the Node n-1.

However, we know that Dijkstra’s algorithm returns the shortest path to all nodes from the starting node. It means that if we get all shortest paths from Node 0 to all nodes, then we can detect the edge from that node is used as the shortest path by comparing the dist[currentNode] + cost == dist[targetNode].

For example,

• The shortest path to Node 1 costs 5.

• And the shortest path to Node 2 costs 7.

• Then, if the edge connecting Node 1 and Node 2 costs 2, it can be used as the shortest path to Node 2.

  • If it costs more than 2, it must not be the shortest path because there is another way to get to Node 2.

We should iterate from the destination to determine whether the edge can be used. We wouldn’t know the following possible nodes from the start. If we find the possible nodes from the destination, we can get all possible edges to those nodes similarly.

class Solution {
public:
    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
        // Step 1: Build the graph as an adjacency list
        unordered_map<int, vector<pair<int, int>>> graph;
        for (int i = 0; i < edges.size(); ++i) {
            int u = edges[i][0], v = edges[i][1];
            graph[u].push_back({v, i}); // Store {neighbor, edge index}
            graph[v].push_back({u, i});
        }

        // Step 2: Use Dijkstra's algorithm to find shortest distances from node 0
        vector<int> dist(n, 1e9);  // Initialize distances with a large value
        dist[0] = 0;
        
        // Min-heap (priority queue) for Dijkstra's algorithm
        priority_queue<pair<int, int>> pq;
        pq.push({0, 0});  // {distance, node}

        while (!pq.empty()) {
            auto current = pq.top();
            pq.pop();
            int d = -current.first;  // Convert back to positive distance
            int node = current.second;

            // Ignore outdated distances (optimization)
            if (dist[node] < d) continue;

            // Explore neighbors
            for (auto &neighborData : graph[node]) {
                int neighbor = neighborData.first;
                int edgeIndex = neighborData.second;
                int cost = edges[edgeIndex][2];  // Edge weight

                // Relaxation step: Update shortest distance if a better path is found
                if (dist[neighbor] > d + cost) {
                    dist[neighbor] = d + cost;
                    pq.push({-dist[neighbor], neighbor});  // Push with negative for min-heap behavior
                }
            }
        }

        // Step 3: Backtrack from node n-1 to find edges used in shortest paths
        vector<bool> answer(edges.size(), false);
        vector<bool> seen(n, false);
        
        queue<int> q;
        q.push(n - 1);
        seen[n - 1] = true;

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            // Traverse backwards to find shortest path edges
            for (auto &neighborData : graph[node]) {
                int neighbor = neighborData.first;
                int edgeIndex = neighborData.second;
                int cost = edges[edgeIndex][2];

                // If the edge belongs to a shortest path
                if (dist[neighbor] + cost == dist[node]) {
                    answer[edgeIndex] = true;
                    if (!seen[neighbor]) {
                        seen[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
        }

        return answer;
    }
};

Time Complexity Analysis

• Graph Construction: O(m), where m is the number of edges.

• Dijkstra’s Algorithm: O((n + m) log n), since each node and edge are processed at most once in a priority queue.

• Backtracking using BFS: O(n + m), since each node and edge are visited once.

Overall Complexity: O((n + m) log n), which is efficient for large graphs.