What's the time complexity of the following code, heapq library

57 Views Asked by At

I wanted to do the complexity analysis of this algorithm, however I don't know the complexity of heap. I would think it could be O(V + E log E) but I don't know.

def dijkstra(start, goal, graph):
    queue = []
    heappush(queue, (0, start))
    cost_visited = {start: 0}
    visited = {start: None}

    while queue:
        cur_cost, cur_node = heappop(queue) 
        if cur_node == goal:
            break

        next_nodes = graph[cur_node]
        for next_node in next_nodes:
            neigh_cost, neigh_node = next_node
            new_cost = cost_visited[cur_node] + neigh_cost

            if neigh_node not in cost_visited or new_cost < cost_visited[neigh_node]:
                heappush(queue, (new_cost, neigh_node))
                cost_visited[neigh_node] = new_cost
                visited[neigh_node] = cur_node
                

    return visited

I don't know where to find the complexity of the methods

0

There are 0 best solutions below