Dijkstra’s Algorithm and Shortest Path

Dijkstra’s algorithm finds the shortest path from the source node to all other nodes where all edge weights are non-negative by using min-heap.

Key idea in this algorithm is to always keep expanding by using the min edge from the set of explored vertices to unexplored vertices. Note that same node could be added into min-heap many times (depending on the implementation) but when it is picked from the min-heap, its shortest distance is final.

Sample problem: https://neetcode.io/problems/network-delay-time

Code:

from heapq import heappush, heappop

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        minDict = defaultdict(int)
        adj = [[] for _ in range(n+1)]

        for t in times:
            adj[t[0]].append([t[1], t[2]])

        # (weight, node)
        minHeap = [(0, k)]

        while minHeap:
            curW, curNode = heappop(minHeap)

            if curNode in minDict:
                continue
            minDict[curNode] = curW

            for nei, neiW in adj[curNode]:
                if nei not in minDict:
                    heappush(minHeap, (curW+neiW, nei))

        return -1 if len(minDict) != n else max(minDict.values())

Complexity Analysis:

• Runtime Complexity: O(E x log(E)) for the above implementation.
  • With decrease key: O(V x log(V) + E x log(V)) where V x log(V) to delete vertices from the heap and E x log(V) to update values in the heap.
• Space Complexity: O(E+V)

Bellman-Ford Algorithm

Bellman-Ford algorithm updates the distances repeatedly with relaxations. Each relaxation tries to improve the shortest distance to a node by expanding the optimal shortest distances.

Code:

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        dist = [float('inf')] * n
        dist[k - 1] = 0
        for _ in range(n - 1):
            for u, v, w in times:
                if dist[u - 1] + w < dist[v - 1]:
                    dist[v - 1] = dist[u - 1] + w
        max_dist = max(dist)
        return max_dist if max_dist < float('inf') else -1

Complexity Analysis:

• Runtime Complexity: O(V x E)
• Space Complexity: O(E+V)

And here is the optimized version of Bellman-Ford algorithm, also known as Shortest Path Faster Algorithm.

• Only process nodes whose distance was actually improved
• Use queue to propagate distance updates

Code:

class Solution:
    def networkDelayTime(self, times, n, k):
        adj = defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))

        dist = {node: float("inf") for node in range(1, n + 1)}
        q = deque([(k, 0)])
        dist[k] = 0

        while q:
            node, time = q.popleft()
            if dist[node] < time:
                continue
            for nei, w in adj[node]:
                if time + w < dist[nei]:
                    dist[nei] = time + w
                    q.append((nei, time + w))

        res = max(dist.values())
        return res if res < float('inf') else -1

Complexity Analysis:

• Runtime Complexity: O(V x E) in worst case and O(V+E) in average
• Space Complexity: O(E+V)

Cheapest Flights Within K Stops

Problem: https://neetcode.io/problems/cheapest-flight-path

For this problem, Bellman-Ford algorithm fits very well because of the limit on the path length.

Code:

from collections import deque

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        cost = [float('inf')] * n
        cost[src] = 0

        for _ in range(k+1):
            newCost = cost.copy()
            for u, v, price in flights:
                if cost[u] != float('inf'):
                    newCost[v] = min(newCost[v], cost[u] + price)

            cost = newCost

        return -1 if cost[dst] == float('inf') else cost[dst]