What is the time complexity of the following code? I'm implementing Prim's Algorithm with adjacency matrix representation of the graph and priority queue.
from graph import adj_mtx, AP
import heapq as hq
lv, visited, h = float('inf'), {}, [] # O(n), lv stands for 'large_value' used to determine infinite distance, h is the heap
def prims_mst(adj_matrix, src):
hq.heappush(h, (0, (src, None))) # O(logn)
curr_dist = {item.value: lv if item.value != src else 0 for item in AP} # curr_dist stands for current distances from the source
while len(h) != 0:
# print h[0]
curr_nd = hq.heappop(h)[1][0] # first element of the tuple is the value, second is the node # O(1)
visited[curr_nd] = True # O(1)
for nd, dst in enumerate(adj_matrix[src]): # O(n) -> n is the number of nodes
if nd not in visited and curr_dist[nd] > curr_dist[curr_nd] + adj_matrix[curr_nd][nd]:
curr_dist[nd] = curr_dist[curr_nd] + adj_matrix[curr_nd][nd]
hq.heappush(h, (curr_dist[nd], (nd, curr_nd))) # O(logn)
print h
lv
etc? \$\endgroup\$ – Lukasz Salitra Jul 12 '17 at 16:23