Click here to see the full article post
the note says 1 <= w <= 100
but i wa with the input
Your implementation of graph using collections.defaultdict as well as Dijkstras using a subtle change to how heapq is used (I have searched a lot for heapq decrease key operation or some other hack for that a lot). Though it is not as efficient as book describes but it is just brilliant. 👍👍 Keep up 👍
Time complexity of Heap implementation should be O(ElogN), where E is the number of edges and N is the number of nodes.
i am curious about the space complexity of approach#2 heap implementation.
the code always puts the new node into heap and do checking after min pop
consider N=5, K = 2
there are many node 3 in the heap.
although the code ignore the previous pop node
but in the heap, the node is still there?
so, will the space complexity be linear?
I also have a similar question as reiveinfire , we are adding edges to heap every time we visit a new node,which means in the worst case , we may add all edges to heap . and each time we add a new edge to the heap and reorganize the heap it takes O(logE) , since we may add all edges to the heap it could be at least O(ElogE) , and E could be V*V . so I think the code may have time complexity O(ElogE) not O(ElogN).
Or should we remove the edges from the heap if they are not helpful before we add new edges to the heap?
I have not read any books for the algorithm. just not sure where I was wrong.
@yingdi you are right, I will correct it
I like your dijkstra solution since it avoids using decrease-key and still achieves the running-time of O(E log E). Dijkstra does O(E log V), but E is O(V^2) so log V is O(log E) even in the worst case.
The solution seems to have a bug.
With the following input
The minimal delay should be 8, which goes from 1 to 3 to 2 (5 + 3). However, the solution gives 10 ?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.