Second Minimum Time To Reach Destination - Leetcode Solution

The Second Minimum Time to Reach Destination problem on LeetCode asks us to find the second minimum time to reach a destination node in a directed, acyclic graph. Here is a detailed solution:

Firstly, we need to understand the problem statement and the constraints given in the problem. The problem statement says that we are given a directed, acyclic graph with non-negative edge weights and we need to find the second minimum time to reach a given destination node from the source node.

The constraints are as follows:

• The graph has n nodes numbered from 0 to n-1.
• The source node is node 0 and the destination node is node n-1.
• We can only travel along the edges of the graph.
• The graph is guaranteed to be acyclic.

One way to approach this problem is to modify Dijkstra's algorithm, which is a shortest path algorithm that can be used to find the shortest path from a source node to all other nodes in a weighted graph. The basic idea of Dijkstra's algorithm is to keep track of the shortest distances from the source node to all other nodes and continually update these distances as we explore more nodes.

To modify Dijkstra's algorithm for this problem, we need to keep track of not only the shortest time to reach each node, but also the second shortest time. To do this, we can maintain two arrays, dist and dist2, where dist[i] represents the shortest time to reach node i from the source, and dist2[i] represents the second shortest time to reach node i from the source.

The initial values of both arrays should be infinity, except for dist[0] which should be 0 since the source node has a distance of 0 from itself. We can use a priority queue to store the nodes that we need to explore, sorted by their shortest distance from the source node.

Then we can start exploring the graph from the source node, using Dijkstra's algorithm. For each node that we explore, we can update its shortest and second shortest distances based on the edges that lead to its neighbors. For example, if we explore node u and find an edge (u, v) with weight w, we can update the distances of node v as follows:

• If dist[v] > dist[u] + w, we update dist[v] = dist[u] + w.
• If dist[v] < dist[u] + w and dist2[v] > dist[u] + w, we update dist2[v] = dist[u] + w.

Note that when we update the second shortest distance of node v, we only update it if it is larger than the new shortest distance. This ensures that the second shortest distance is always greater than or equal to the shortest distance.

We continue exploring the graph until we reach the destination node. At this point, dist[n-1] will give us the shortest time to reach the destination, and dist2[n-1] will give us the second shortest time.

Finally, we can return dist2[n-1] if it is not infinity (meaning there exists a second shortest path), or -1 if it is infinity (meaning there is no second shortest path).

Here is the Python code for the modified Dijkstra's algorithm:

import heapq

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]]) -> int:
        # Initialize arrays
        dist = [float('inf') for _ in range(n)]
        dist2 = [float('inf') for _ in range(n)]
        dist[0] = 0
        
        # Create adjacency list
        adj = [[] for _ in range(n)]
        for u, v, w in edges:
            adj[u].append((v, w))
        
        # Create priority queue
        pq = [(0, 0)]  # (distance, node)
        
        while pq:
            # Pop node with smallest distance
            d, u = heapq.heappop(pq)
            
            # Update distances of neighbors
            for v, w in adj[u]:
                if dist[v] > dist[u] + w:
                    dist[v], dist2[v] = dist[u] + w, dist[v]
                    heapq.heappush(pq, (dist[v], v))
                elif dist[v] < dist[u] + w and dist2[v] > dist[u] + w:
                    dist2[v] = dist[u] + w
                    heapq.heappush(pq, (dist2[v], v))
        
        # Return second shortest distance
        return dist2[n-1] if dist2[n-1] < float('inf') else -1

This solution has a time complexity of O(ElogV) where E is the number of edges and V is the number of vertices in the graph. This is because we use a priority queue to store the nodes, which has a cost of O(logV) for each insertion and deletion, and we explore each edge once. The space complexity is also O(V) because we need to store arrays of size V for dist and dist2.

1