We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
fromcollectionsimportdequeclassGraph():def__init__(self,node_count):self.nodes={}foriinrange(node_count):self.nodes[i]=[]defconnect(self,a,b):self.nodes[a].append(b)self.nodes[b].append(a)deffind_all_distances(self,label):original_label=labeldistance=0paths={}q=deque([(label,distance,self.nodes[label])])while(q):label,distance,neighbors=q.popleft()iflabelnotinpaths:# Prevent cyclespaths[label]=distanceforneighborinneighbors:q.append((neighbor,distance+6,self.nodes[neighbor]))# Set unreachable nodes to -1 distancefornodeinself.nodes:ifnodenotinpaths:paths[node]=-1delpaths[original_label]# node should not have a path to itselfreturn[paths[node]fornodeinpaths]
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
BFS: Shortest Reach in a Graph
You are viewing a single comment's thread. Return to all comments →
Python 3 solution: