Solve the Second Shortest Path problem

by Using BFS or Dijkstra algorithm

We know that for Single Source Shortest Path(SSSP) problem, we can

• solve it by using BFS if no weights or equal weights during each exploration.
• solve by using Dijkstra if the graph has positive unequal weights.

For the problem in this article, we can use modified BFS and Dijkstra to solve the second shortest path problem.

2045. Second Minimum Time to Reach Destination

This problem is the 4th question of the leetcode 263 weekly contest problem. In this article, I will introduce the BFS based and Dijkstra based solutions.

BFS with max visit constrains

Since for this problem, the weights are equal, we can think about solve the problem by using the BFS. Basic steps:

1. Using the BFS to traverse the graph. The difference to the standard BFS is one node can be visited multiple times. (You can think we should ignore the seen information)
2. If we first reach the target node, we should not stop (in the standard SSSP problem, we stop here). What we should do is keep on exploring the graph until the second shortest path is found for the target node.
3. If we don’t set a constraints of the visit times for each node, we will get TLE, as the graph size can be increased exponentially. We can apply an unproved trick by set an upper bound for the maximum visiting time for each node, then the problem can be solved.

Reference code can be found here.

using PII = pair<int, int>;
int seen[10010];
class Solution {
    public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        memset(seen, 0, sizeof seen);
        vector<PII> thisLevel;
        int minCost = INT_MAX;
        thisLevel.emplace_back(1, 0);
        vector<vector<int>> graph(n + 1);
        for (auto e: edges){
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        seen[1]++;
        int newcost;
        const int MAX_VISIT = 70;
        // BFS with depth constraints for each node.
        while (thisLevel.size()){
            vector<PII> nextLevel;
            for (auto [node, cost]: thisLevel){
                for (auto nei : graph[node]){
                    // comment this line will get TLE.
                    if (seen[nei] > MAX_VISIT)continue;
                    seen[nei]++;
                    newcost = cost + time;
                    // red
                    if ((cost / change) % 2 == 1){
                        newcost += change - (cost % change); 
                    } 
                    if (nei == n ){
                        if (minCost!= INT_MAX && newcost > minCost){
                            return newcost;
                        } else {
                            minCost = newcost;
                        }
                    } 
                    nextLevel.emplace_back(nei, newcost);   
                }
            }
thisLevel = nextLevel;
        }
        return 0;
    }
};

If you are not satisfied with this BFS solution, we can move forward for a Dijkstra based solution.

runtime

Runtime: 1693 ms, faster than 5.50% of C++ online submissions forSecond Minimum Time to Reach Destination.
Memory Usage: 362 MB, less than 5.07% of C++ online submissions forSecond Minimum Time to Reach Destination.

Dijkstra based solution

The idea is pretty simple:

• In the standard Dijkstra algorithm, we maintain one priority_queue and one distance array for the shortest path.
• For this problem, we maintain two distance arrays, one for the shortest path and one for the second shortest path.

Reference code[1]

using PII = pair<int, int>;
class Solution {
    public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        vector<int> dis(n+1, INT_MAX), dis2(n+1, INT_MAX);
        vector<vector<int>> graph(n + 1);
        for (auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        dis[1] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> pq;
        pq.emplace(0, 1);
        while (pq.size()) {
            auto [cost, node] = pq.top();pq.pop();
            if (dis2[node] < cost) continue;
            for (auto nei: graph[node]) {
                int new_cost = cost + time;
                // red
                if ((cost / change) % 2 == 1){
                    new_cost += change - (cost % change);
                }
                if (dis[nei] > new_cost){
                    dis2[nei] = dis[nei];
                    dis[nei] = new_cost;
                    pq.emplace(new_cost, nei);
                } else if (new_cost > dis[nei] && new_cost < dis2[nei] ) {
                    dis2[nei] = new_cost;
                    pq.emplace(new_cost, nei);
                }
            }
        }
        return dis2[n];
    }
};

runtime

Runtime: 1280 ms, faster than 22.84% of C++ online submissions for Second Minimum Time to Reach Destination.
Memory Usage: 181.6 MB, less than 74.34% of C++ online submissions for Second Minimum Time to Reach Destination.

Optimized BFS solution

Since the weight are equal for each exploration, the priority queue is not necessary (a regular queue can already make the front element has the smallest weight). Simply replace the priority_queue to queue, we can achieve a faster solution.

using PII = pair<int, int>;
class Solution {
    public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        vector<int> dis(n+1, INT_MAX), dis2(n+1, INT_MAX);
        vector<vector<int>> graph(n + 1);
        for (auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        dis[1] = 0;
        queue<PII> Q;
        Q.emplace(0, 1);
        while (Q.size()) {
            auto [cost, node] = Q.front();Q.pop();
            for (auto nei: graph[node]) {
                int new_cost = cost + time;
                // red
                if ((cost / change) % 2 == 1){
                    new_cost += change - (cost % change);
                }
                if (dis[nei] > new_cost){
                    dis2[nei] = dis[nei];
                    dis[nei] = new_cost;
                    Q.emplace(new_cost, nei);
                } else if (new_cost > dis[nei] && new_cost < dis2[nei] ) {
                    dis2[nei] = new_cost;
                    Q.emplace(new_cost, nei);
                }
            }
        }
        return dis2[n];
    }
};

runtime

Runtime: 544 ms, faster than 92.53% of C++ online submissions forSecond Minimum Time to Reach Destination.
Memory Usage: 182 MB, less than 73.56% of C++ online submissions for Second Minimum Time to Reach Destination.

python version

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        dis, dis2 = [float("inf")]*(n+1), [float("inf")]*(n+1)
        graph = collections.defaultdict(list)
        for u, v in  edges:
            graph[u].append(v)
            graph[v].append(u)
        dis[1] = 0
        Q = deque()
        Q.append((0, 1))
        while Q:
            cost, node = Q.popleft()
            for nei in graph[node]:
                new_cost = cost + time;
                # red signal
                if (cost // change) % 2 == 1:
                    new_cost += change - (cost % change)
                # update two distances.
                if dis[nei] > new_cost:
                    dis2[nei], dis[nei]  = dis[nei], new_cost;
                    Q.append((new_cost, nei))
                elif new_cost > dis[nei] and new_cost < dis2[nei]:
                    dis2[nei] = new_cost
                    Q.append((new_cost, nei))
        return dis2[n]

Reference

[1] submission from MaskRay