LC-2642 Hard LeetCode

2642. Design Graph With Shortest Path Calculator

Graph Design Heap (Priority Queue) Shortest Path

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 64% Topics: Graph, Design, Heap (Priority Queue), Shortest Path

Reading material

Graphs 16 min Design (Data Structures) 14 min Heaps & Priority Queues 13 min

Reference solution (spoiler · python)

# Time:  ctor:         O(|V| + |E|)
#        addEdge:      O(1)
#        shortestPath: O((|E| + |V|) * log|V|) = O(|E| * log|V|)
# Space: O(|E| + |V|) = O(|E|)

import heapq


# dijkstra's algorithm
class Graph(object):

    def __init__(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        """
        self.__adj = [[] for _ in xrange(n)]
        for edge in edges:
            self.addEdge(edge)

    def addEdge(self, edge):
        """
        :type edge: List[int]
        :rtype: None
        """
        u, v, w = edge
        self.__adj[u].append((v, w))

    def shortestPath(self, node1, node2):
        """
        :type node1: int
        :type node2: int
        :rtype: int
        """
        def dijkstra(adj, start, target):
            best = [float("inf")]*len(adj)
            best[start] = 0
            min_heap = [(best[start], start)]
            while min_heap:
                curr, u = heapq.heappop(min_heap)
                if curr > best[u]:
                    continue
                for v, w in adj[u]:                
                    if not (curr+w < best[v]):
                        continue
                    best[v] = curr+w
                    heapq.heappush(min_heap, (best[v], v))
            return best[target] if best[target] != float("inf") else -1

        return dijkstra(self.__adj, node1, node2)

Solution from kamyu104/LeetCode-Solutions · MIT