[LeetCode] #743: Network Delay Time

Problem:

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

---

Process:

Objective: Return the time it takes for all the n nodes to receive the signal. In other words, return the longest time to reach a node from the source node.

Constraints:
1. 1 <= k <= n <= 100
2. 1 <= times.length <= 6000
3. times[i].length == 3
4. 1 <= ui, vi <= n
5. ui != vi
6. 0 <= wi <= 100
7. All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Edge Cases:
1. When there is a unreachable node
2. When there is a cycle in the graph

Few things to keep in mind:
1. The graph cannot be empty
2. There are unreachable nodes

---

Solution:

Attmept #1: Using the Bellman-Ford Algorithm

• Time Complexity: O($V*E$) which is $n*times$.length (at worst case it can be $n^3$)
• Space Complexity: O(n)

Logic behind this decision:
Bellman-Ford Algorithm finds the shortest path to all the nodes from the source node. All the conditions were met for me to use the Bellman-Ford Algorithm:

1. It is a directed, weighted graph
2. There are non-negative weight, which means that there would not be any negative weight cycles in the graph.

How it works:
1. We will initialize the distances list with positive infinite float value.
2. We will loop through all the edges to update the shortest path to reach certain nodes. If distances[u] > distance[v] + weight, the pre-existing distance distances[u] will be replaced. This is called the relaxation.
3. We will go through the relaxation process n-1 times.

def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        distances = [float("inf")] * (n)
        distances[k-1] = 0
        
        for _ in range(n-1):
            for u,v,w in times:
                if distances[u-1] != float("inf") and distances[u-1] + w < distances[v-1]:
                    distances[v-1] = distances[u-1] + w

                    
        if float("inf") in distances:
            return -1
        else:
            return max(distances)

Limitations:

1. This algorithm takes too long. This makes us start wondering if we could use other algorithms to reduce the time.

---

Attempt #2: Using Dijkstra's SP Algorithm

• Time Complexity: O($E + V*logE$)?? - Should be faster than attempt #1
• Space Complexity: O(V+E)

Logic behind this decision:
We can use Dijkstra's SP Algorithm until when we get the distance to all of the nodes. Since all the graphs are non-negative, the algorithm should not have any problem.

How is works:
1. We will initialize the distances list with positive infinite float value.
2. We will convert the times list as a graph dictionary through using the listToDict function.
3. We will iterate through nodes in nodes_to_visit starting from the start node.

• update the distance to node if the new distance to the node is smaller than the original distance.
• add neighbors into nodes_to_visit if those nodes are not visited yet. We will be using min-heap to push the nodes, since we want to greedily visit the nodes that will has the shortest distance from the starting node.

4. We will return -1 if there are any float("inf") in distances, which means that some of the nodes are not visited. Else, we will be returning the max value from the distances list.

def listToDict(self, times):
        times_dict = defaultdict(list)
        for edge in times:
            u,v,w = edge
            times_dict[u].append((w,v))
        
        return times_dict
        
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        distances = [float("inf")] * (n)
        
        # O(E)
        graph_dict = self.listToDict(times)
        nodes_to_visit = [(0,k)]
        
        while nodes_to_visit:
            w, u = heapq.heappop(nodes_to_visit)
            if distances[u-1] > w:
                distances[u-1] = w
            
            for neighbor in graph_dict[u]:
                w2, v = neighbor
                if distances[v-1] == float("inf"): 
                    heapq.heappush(nodes_to_visit, (w+w2, v))
            
        if float("inf") in distances:
            return -1
        else:
            return max(distances)

---

LeetCode Question #743