Floyd Modified

This is just like the Floyd-Warshall algorithm, but with a twist that enables us to get the sequence of nodes used in the shortest path solution found

• Complexity => Θ(nlogn)

For intermediary node of 0

• Condition 1 => predecessor_source_destination = source if (source, destination) is an existing arc
• Condition 2 => predecessor_source_destination = nil if is equals to infinity or source = destination

For intermediary node greater than 0

• Condition 1 => If source to destination go through intermediary_node, then the predecessor_source_destination equal predecessor_intermediary_destination
• Condition 2 => else the path does not go through intermediary_node

   // 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)

           //Copy of the valued matrix
           NEW_VALUED_MATRIX = INITIAL_VALUED_MATRIX

           if (SOURCE_NODE != DESTINATION_NODE 
               and INITIAL_VALUED_MATRIX[SOURCE_NODE, DESTINATION_NODE] != INFINITY)
                PREDECESSOR_MATRIX[SOURCE_NODE, DESTINATION_NODE] = SOURCE_NODE
           else
                PREDECESSOR_MATRIX[SOURCE_NODE, DESTINATION_NODE] = NIL;
   
    //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)
                temp = NEW_VALUED_MATRIX[SOURCE_NODE,INTERMEDIARY_NODE] + 
                        NEW_VALUED_MATRIX[INTERMEDIARY_NODE,DESTINATION_NODE]

                if (temp < NEW_VALUED_MATRIX[SOURCE_NODE, DESTINATION_NODE])
                     NEW_VALUED_MATRIX[SOURCE_NODE, DESTINATION_NODE] = temp;
                     PREDECESSOR_MATRIX[SOURCE_NODE, DESTINATION_NODE] = 
                          PREDECESSOR_MATRIX[INTERMEDIARY_NODE, DESTINATION_NODE]
                   
    return (NEW_VALUED_MATRIX, PREDECESSOR_MATRIX)

Very nice tutorial from a Stanford professor.

Another cool tutorial to visualize it.