Shortest path in a directed graph by Dijkstraâ €™ s algorithm | Python3 implementation to find the shortest path in a directed graph from source vertex to the destination vertex ; Class of the node ; Adjacency list that shows the vertexNumber of child vertex and the weight of the edge ; Function to add the child for the given node ; Function to find the distance of the node from the given source vertex to the destination vertex ; Stores distance of each vertex from source vertex ; bool array that shows whether the vertex ' i ' is visited or not ; Set of vertices that has a parent ( one or more ) marked as visited ; Mark current as visited ; Inserting into the visited vertex ; Condition to check the distance is correct and update it if it is minimum from the previous computed distance ; The new current ; Loop to update the distance of the vertices of the graph ; Function to print the path from the source vertex to the destination vertex ; Condition to check if there is no path between the vertices ; Driver Code ; Loop to create the nodes ; Creating directed weighted edges ; Loop to print the distance of every node from source vertex
class Pair : NEW_LINE INDENT def __init__ ( self , first , second ) : NEW_LINE INDENT self . first = first NEW_LINE self . second = second NEW_LINE DEDENT DEDENT infi = 1000000000 ; NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , vertexNumber ) : NEW_LINE INDENT self . vertexNumber = vertexNumber NEW_LINE self . children = [ ] NEW_LINE DEDENT def Add_child ( self , vNumber , length ) : NEW_LINE INDENT p = Pair ( vNumber , length ) ; NEW_LINE self . children . append ( p ) ; NEW_LINE DEDENT DEDENT def dijkstraDist ( g , s , path ) : NEW_LINE INDENT dist = [ infi for i in range ( len ( g ) ) ] NEW_LINE visited = [ False for i in range ( len ( g ) ) ] NEW_LINE for i in range ( len ( g ) ) : NEW_LINE INDENT path [ i ] = - 1 NEW_LINE DEDENT dist [ s ] = 0 ; NEW_LINE path [ s ] = - 1 ; NEW_LINE current = s ; NEW_LINE sett = set ( ) NEW_LINE while ( True ) : NEW_LINE INDENT visited [ current ] = True ; NEW_LINE for i in range ( len ( g [ current ] . children ) ) : NEW_LINE INDENT v = g [ current ] . children [ i ] . first ; NEW_LINE if ( visited [ v ] ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT sett . add ( v ) ; NEW_LINE alt = dist [ current ] + g [ current ] . children [ i ] . second ; NEW_LINE if ( alt < dist [ v ] ) : NEW_LINE INDENT dist [ v ] = alt ; NEW_LINE path [ v ] = current ; NEW_LINE DEDENT DEDENT if current in sett : NEW_LINE INDENT sett . remove ( current ) ; NEW_LINE DEDENT if ( len ( sett ) == 0 ) : NEW_LINE INDENT break ; NEW_LINE DEDENT minDist = infi ; NEW_LINE index = 0 ; NEW_LINE for a in sett : NEW_LINE INDENT if ( dist [ a ] < minDist ) : NEW_LINE INDENT minDist = dist [ a ] ; NEW_LINE index = a ; NEW_LINE DEDENT DEDENT current = index ; NEW_LINE DEDENT return dist ; NEW_LINE DEDENT def printPath ( path , i , s ) : NEW_LINE INDENT if ( i != s ) : NEW_LINE INDENT if ( path [ i ] == - 1 ) : NEW_LINE INDENT print ( " Path ▁ not ▁ found ! ! " ) ; NEW_LINE return ; NEW_LINE DEDENT printPath ( path , path [ i ] , s ) ; NEW_LINE print ( path [ i ] + " ▁ " ) ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT v = [ ] NEW_LINE n = 4 NEW_LINE s = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT a = Node ( i ) ; NEW_LINE v . append ( a ) ; NEW_LINE DEDENT v [ 0 ] . Add_child ( 1 , 1 ) ; NEW_LINE v [ 0 ] . Add_child ( 2 , 4 ) ; NEW_LINE v [ 1 ] . Add_child ( 2 , 2 ) ; NEW_LINE v [ 1 ] . Add_child ( 3 , 6 ) ; NEW_LINE v [ 2 ] . Add_child ( 3 , 3 ) ; NEW_LINE path = [ 0 for i in range ( len ( v ) ) ] ; NEW_LINE dist = dijkstraDist ( v , s , path ) ; NEW_LINE for i in range ( len ( dist ) ) : NEW_LINE INDENT if ( dist [ i ] == infi ) : NEW_LINE INDENT print ( " { 0 } ▁ and ▁ { 1 } ▁ are ▁ not ▁ " + " connected " . format ( i , s ) ) ; NEW_LINE continue ; NEW_LINE DEDENT print ( " Distance ▁ of ▁ { } th ▁ vertex ▁ from ▁ source ▁ vertex ▁ { } ▁ is : ▁ { } " . format ( i , s , dist [ i ] ) ) ; NEW_LINE DEDENT DEDENT