Week 2 - Learning Weighted Graph Algorithms

Exploring Weighted Graph Algorithms

This week, I spent time learning some of the most important algorithms used on weighted graphs. I studied Dijkstra's Algorithm, Bellman-Ford, and Floyd-Warshall, as well as Prim's and Kruskal's Algorithm.

I'm super proud of the questions that I solved this week on LeetCode. It feels like I'm putting what I'm learning into practice. I'm already feeling better prepared to answer various DFS/BFS problems. I was even able to write a solution to Find the City with the Smallest Number of Neighbours on LeetCode. The solution uses a modified Dijkstra and stops exploring paths that have exceeded the threshold.

LeetCode Challenge: Find the City With the Smallest Number of Neighbors

The problem asks us to find the city that has the smallest number of cities that can be reached through some path with distance at most distanceThreshold. If there are multiple such cities, we need to return the city with the largest number.

This is my solution using a modified Dijkstra's algorithm:

import heapq

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        min_city_dist, max_city = float('inf'), 0
        
        # Build the adjacency list
        adj = [[] for _ in range(n)]
        for u, v, weight in edges:
            adj[u].append((v, weight))
            adj[v].append((u, weight))
            
        # Call Dijkstra's algorithm for each city
        for city in range(n):
            # Get the number of cities that satisfy the distanceThreshold
            num_cities = self.dijkstra(adj, city, n, distanceThreshold)
            
            if num_cities <= min_city_dist: # Found a city with smaller # of cities satisfying the threshold
                min_city_dist = num_cities
                max_city = city
                
        return max_city
    
    def dijkstra(self, adj: List[List[int]], source: int, n: int, distanceThreshold: int) -> int:
        dist = [float('inf')] * n
        dist[source] = 0
        visited = [False] * n
        pq = [(0, source)]
        
        while pq:
            curr_dist, u = heapq.heappop(pq)
            
            # Skip paths that are greater than threshold
            if curr_dist > distanceThreshold:
                continue
                
            # Skip if already visited
            if visited[u]:
                continue
                
            visited[u] = True
            
            # Perform relaxation on each neighbouring edge ONCE
            for v, weight in adj[u]:
                if curr_dist + weight < dist[v]:
                    dist[v] = curr_dist + weight
                    
                    # Only add if neighbouring distance is less than threshold
                    if dist[v] <= distanceThreshold:
                        heapq.heappush(pq, (dist[v], v))
                        
        # Return the number of cities from the source that satisfy the distanceThreshold
        return sum([1 for city, dist_val in enumerate(dist) if city != source and dist_val <= distanceThreshold])

Optimizing for Performance

Although the solution has a time complexity of O((V³) log V), similar to the LeetCode editorial solution, it runs faster due to the early stopping condition.

This solution shines in terms of space complexity. The original LeetCode solution has a space complexity of O(V²), due to the result used to find the shortest path between any two vertices. The space complexity of my solution is O(V + E), for the adjacency list and other auxiliary data structures such as the priority queue.

With my solution, I didn't need a 2D array. I modified Dijkstra's Algorithm to return the number of cities that satisfy the threshold instead of returning all the distances. There was no need for me to store the results in an array—I could directly use the result and compare it to the minimum city found so far.

Key Optimizations in My Solution

1. Early Termination: The algorithm stops exploring paths once they exceed the distance threshold, avoiding unnecessary computations.
2. Efficient Space Usage: Instead of storing all shortest paths in a 2D array, I directly count the number of cities that satisfy the threshold.
3. Optimized Dijkstra Implementation: The implementation uses a priority queue for efficiency and includes a visited array to prevent revisiting nodes.

Looking Ahead

I start trees next week and am excited to continue to learn more and get better at LeetCode! Studying daily has already made me a better programmer, and I feel more prepared for coding interviews.

I'll see you next week!

Until then,
Anjola