Python modified Dijkstra / hybrid SPFA
This is sort of like Dijkstra on fees, with times "along for the ride". Typically, Dijkstra stores the result for node u as it pops the next item off the min he
This is sort of like Dijkstra on fees, with times "along for the ride". Typically, Dijkstra stores the result for node u as it pops the next item off the min heap, and then never returns to the same node. In this case, there are three changes:\n\n1. We only care about the shortest edge between two vertices in the graph, so when building the graph always take the min weight edge.\n2. Normally, Dijkstra only adds a neighbor v of the current node u to the queue if u hasn\'t been processed before (this is also why Dijkstra can\'t handle negative edge weights). However, in our case we have two changes: first, we re-process the node u if the new time is an improvement over the existing time; second, we only add a neighbor if its new_time is within the time constraint.\n3. Normally, Dijkstra is SSSP and we would need to store intermediate fee values in something like a dictionary. However, this is shortest path between two nodes. Hence, we can use the heap to store our result (which will be the popped fee when u == n - 1).\n\nThe algorithm we end up with feels like a hybrid between Dijkstra and SPFA (shortest path faster algorithm, a modified Bellman-Ford). It\'s like Dijkstra in that we\'re using a heap (and adding an early exit condition because we don\'t care about all destinations). But it\'s like SPFA in that we only add vertices to the heap if they can contribute to the solution (which means new_time <= maxTime for this problem).\n\n```py\nclass Solution:\n    def minCost(self, maxTime: int, edges: List[List[int]], fees: List[int]) -> int:\n        n = len(fees)\n        \n        g = collections.defaultdict(lambda: collections.defaultdict(lambda: float(\'inf\')))\n        for u, v, w in edges:\n            g[u][v] = min(g[u][v], w)\n            g[v][u] = min(g[v][u], w)\n        \n        times = {}\n        \n        h = [(fees[0], 0, 0)]\n        while h:\n            fee, time, u = heapq.heappop(h)\n\n            if u == n - 1:\n                return fee\n            \n            if u not in times or time < times[u]:\n                times[u] = time\n                for v in g[u]:\n                    new_time = time + g[u][v]\n                    if new_time <= maxTime:\n                        heapq.heappush(h, (fee + fees[v], new_time, v))\n        \n        return -1\n```\n\nNow, let\'s look at the time and space complexity. Typically, min-heap Dijkstra has a time complexity of O(E + V log V), because we process each edge at most twice and each vertex at most once (where V log V comes from popping V vertices off the heap). And space complexity of O(V + E) (the max size of the heap), which becomes O(E) for connected graphs\n\nThe time and space complexity of this problem are a little trickier to calculate. Intuitively, it feels psuedo-polynomial because the number of times we relax an edge depends on maxTime (the larger maxTime, the more times we can potentially relax an edge). \n\nI\'d like to see some others weigh in, but my thoughts are:\n\nGiven that edge weights are at least 1, we can process each vertex O(maxTime) times. This is because you can have simple paths (paths with no repeated edges) of length up to maxTime. So we could process a vertex for a path of length 1 and weight maxTime with fee x, then a path of length 2 and weight maxTime - 1 with fee x, etc. Each time we process the vertex, we put it on the heap. So it seems the heap can end up as O(E * maxSize) size and the time complexity can become O(E * maxTime + (V * maxTime) * log(V * maxTime)).\n\n
[]