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