BinarySearch 0993 Shortest Path in a Graph

Problem statement

https://binarysearch.com/problems/Shortest-Path-in-a-Graph/

Solution

Classical Dijkstra here.

Complexity

It is O(E log E + n) for time and O(n + E) for space.

Code

class Solution:
    def solve(self, edges, start, end):
        def Dijkstra(graph, beg, end):
            q, t = [(0, beg)], {}
            while q:
                time, node = heappop(q)
                if node not in t:
                    t[node] = time
                    for v, w in graph[node]:
                        heappush(q, (time + w, v))
            return t.get(end, -1)

        G = defaultdict(list)
        for x, y, w in edges:
            G[x] += [(y, w)]

        return Dijkstra(G, start, end)