Network Delay Time


  • 0

    Click here to see the full article post


  • 0
    H

    the note says 1 <= w <= 100
    but i wa with the input

    [[3,5,78],[2,1,1],[1,3,0],[4,3,59],[5,3,85],[5,2,22],[2,4,23],[1,4,43],[4,5,75],[5,1,15],[1,5,91],[4,1,16],[3,2,98],[3,4,22],[5,4,31],[1,2,0],[2,5,4],[4,2,51],[3,1,36],[2,3,59]]
    5
    5

    [1,3,0] ???????
    [1,2,0] ???????


  • 0
    S

    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 👍

    Thanks @awice


  • 0

    Time complexity of Heap implementation should be O(ElogN), where E is the number of edges and N is the number of nodes.
    Reference: https://stackoverflow.com/questions/26547816/understanding-time-complexity-calculation-for-dijkstra-algorithm


  • 0
    R

    @awice ,
    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
    (2,1,3)
    (2,5,2)
    (2,3,9)
    (3,4,1)
    (1,3,3)
    (5,3,3)

    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?

    thanks.


  • 0
    Y

    @awice ,

    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.

    Thanks


  • 0

    @yingdi you are right, I will correct it


  • 0
    D

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.