<s> from heapq import heappop , heappush <EOL> def dijkstra ( graph , weight , source = <NUM_LIT:0> , target = None ) : <EOL> """<STR_LIT>""" <EOL> n = len ( graph ) <EOL> assert all ( weight [ u ] [ v ] >= <NUM_LIT:0> for u in range ( n ) for v in graph [ u ] ) <EOL> prec = [ None ] * n <EOL> black = [ False ] * n <EOL> dist = [ float ( '<STR_LIT>' ) ] * n <EOL> dist [ source ] = <NUM_LIT:0> <EOL> heap = [ ( <NUM_LIT:0> , source ) ] <EOL> while heap : <EOL> dist_node , node = heappop ( heap ) <EOL> if not black [ node ] : <EOL> black [ node ] = True <EOL> if node == target : <EOL> break <EOL> for neighbor in graph [ node ] : <EOL> dist_neighbor = dist_node + weight [ node ] [ neighbor ] <EOL> if dist_neighbor < dist [ neighbor ] : <EOL> dist [ neighbor ] = dist_neighbor <EOL> prec [ neighbor ] = node <EOL> heappush ( heap , ( dist_neighbor , neighbor ) ) <EOL> return dist , prec <EOL> from tryalgo . our_heap import OurHeap <EOL> def dijkstra_update_heap ( graph , weight , source = <NUM_LIT:0> , target = None ) : <EOL> """<STR_LIT>""" <EOL> n = len ( graph ) <EOL> assert all ( weight [ u ] [ v ] >= <NUM_LIT:0> for u in range ( n ) for v in graph [ u ] ) <EOL> prec = [ None ] * n <EOL> dist = [ float ( '<STR_LIT>' ) ] * n <EOL> dist [ source ] = <NUM_LIT:0> <EOL> heap = OurHeap ( [ ( dist [ node ] , node ) for node in range ( n ) ] ) <EOL> while heap : <EOL> dist_node , node = heap . pop ( ) <EOL> if node == target : <EOL> break <EOL> for neighbor in graph [ node ] : <EOL> old = dist [ neighbor ] <EOL> new = dist_node + weight [ node ] [ neighbor ] <EOL> if new < old : <EOL> dist [ neighbor ] = new <EOL> prec [ neighbor ] = node <EOL> heap . update ( ( old , neighbor ) , ( new , neighbor ) ) <EOL> return dist , prec </s>
