Floyd

Floyd Algorithm (Floyd/Warshall)

This is used to find the shortest path value between the arcs of a directed and valued graph

• Complexity => Θ(n3)

   //Copy of the valued matrix
   NEW_VALUED_MATRIX = INITIAL_VALUED_MATRIX
   
    //In the copy. Loop through all the mediatory nodes
    for(INTERMEDIARY_NODE = 1,2,...,NUMBER_OF_NODES)
      
        // Loop through each pair of nodes
      
        // Loop through all the source nodes
        for(SOURCE_NODE = 1,2,...,NUMBER_OF_NODES)
            
            // Loop through all the destination nodes
            for(DESTINATION_NODE = 1,2,...,NUMBER_OF_NODES)
                // Assign shortest Path to intermediary node
                NEW_VALUED_MATRIX[SOURCE_NODE, DESTINATION_NODE] = 
                    Min( NEW_VALUED_MATRIX[SOURCE_NODE, DESTINATION_NODE], 
                        NEW_VALUED_MATRIX[SOURCE_NODE,INTERMEDIARY_NODE] + 
                        NEW_VALUED_MATRIX[INTERMEDIARY_NODE,DESTINATION_NODE]))
                   
    return NEW_VALUED_MATRIX

[https://www.youtube.com/watch?v=Qdt5WJVkPbY](Floyd-Warshall On Youtube)