D 'Esopo | Python3 implementation for D 'Esopo-Pape algorithm ; Number of vertices in graph ; Adjacency list of graph ; Queue to store unoperated vertices ; Distance from source vertex ; Status of vertex ; let 0 be the source vertex ; Pop from front of the queue ; scan adjacent vertices of u ; e < - [ weight , vertex ] ; if e [ 1 ] is entering first time in the queue ; Append at back of queue ; Append at front of queue ; Driver Code ; Adjacency matrix of graph
from collections import defaultdict , deque NEW_LINE def desopo ( graph ) : NEW_LINE INDENT v = len ( graph ) NEW_LINE adj = defaultdict ( list ) NEW_LINE for i in range ( v ) : NEW_LINE INDENT for j in range ( i + 1 , v ) : NEW_LINE INDENT if graph [ i ] [ j ] != 0 : NEW_LINE INDENT adj [ i ] . append ( [ graph [ i ] [ j ] , j ] ) NEW_LINE adj [ j ] . append ( [ graph [ i ] [ j ] , i ] ) NEW_LINE DEDENT DEDENT DEDENT q = deque ( [ ] ) NEW_LINE distance = [ float ( ' inf ' ) ] * v NEW_LINE is_in_queue = [ False ] * v NEW_LINE source = 0 NEW_LINE distance = 0 NEW_LINE q . append ( source ) NEW_LINE is_in_queue = True NEW_LINE while q : NEW_LINE INDENT u = q . popleft ( ) NEW_LINE is_in_queue [ u ] = False NEW_LINE for e in adj [ u ] : NEW_LINE INDENT if distance [ e [ 1 ] ] > distance [ u ] + e [ 0 ] : NEW_LINE INDENT distance [ e [ 1 ] ] = distance [ u ] + e [ 0 ] NEW_LINE if is_in_queue [ e [ 1 ] ] == False : NEW_LINE INDENT if distance [ e [ 1 ] ] == float ( ' inf ' ) : NEW_LINE INDENT q . append ( e [ 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT q . appendleft ( e [ 1 ] ) NEW_LINE DEDENT is_in_queue [ e [ 1 ] ] = True NEW_LINE DEDENT DEDENT DEDENT DEDENT return distance NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT graph = [ [ 0 , 4 , 0 , 0 , 8 ] , [ 0 , 0 , 8 , 0 , 11 ] , [ 0 , 8 , 0 , 2 , 0 ] , [ 0 , 0 , 2 , 0 , 1 ] , [ 8 , 11 , 0 , 1 , 0 ] ] NEW_LINE print ( desopo ( graph ) ) NEW_LINE DEDENT