Floyd-Warshall Algorithm

While Dijkstra's algorithm finds the shortest path between a root node and other vertices, the Floyd-Warshall algorithm is for finding the shortest path between all the pairs of vertices. 

Floyd-Warshall Algorithm

                        

The Floyd-Warshall algorithm uses the dynamic programming approach to solve the problem and it works both for directed and undirected weighted graphs.

The time complexity of the Floyd-Warshall algorithm is O(N^3) while there are three loops iterate over all the nodes.

 Also, the space complexity of the Floyd-Warshall algorithm is N^2 since it requires a 2D array or list to save the shortest paths.

Here are simple steps for the Floyd-Warshall algorithm.

1. Create a 2D array (NxN) and fill it with an infinite number. 
2. As you get inputs (connections and weights), replace numbers at the position (i,j).
3. Create three loops that go from 1 to the number of nodes. 
4. more out for loop will be the midpoint and the second for loop will be the starting node. Lastly, the most inner loop with being the target node.
5. If a path from a starting node to a target node is greater than the sum of a starting node to a midpoint and a mid to a target node, then replace the path weight with the smaller weight.

Down below is a simple implementation of the Floyd-Warshall algorithm.

####################################################

bool FloydWarshall(int iWantedNode) {

for (int loop = 1; loop <= iNodeNum; loop++) {

iResultSaveArray[loop][loop] = 0;

for (int i = 1; i <= iNodeNum; i++) {

for (int j = 1; j <= iNodeNum; j++) {

if (i == loop || i == j)continue;

int iCurrentNode = i;

int iTo = j;

if (iResultSaveArray[iCurrentNode][iTo] >     iResultSaveArray[iCurrentNode][loop] + iResultSaveArray[loop][iTo]) {

iResultSaveArray[iCurrentNode][iTo] = iResultSaveArray[iCurrentNode][loop] + iResultSaveArray[loop][iTo];

}

}

}

}

for (int i = 1; i <= iNodeNum; i++) {

for (int j = 1; j <= iNodeNum; j++) {

if (iResultSaveArray[i][j] != INF) {

cout << iResultSaveArray[i][j] << " ";

}

else {

cout << 0 << " ";

}

}

cout << "\n";

}

return false;

}

####################################################

References:

https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/

https://www.programiz.com/dsa/floyd-warshall-algorithm

https://www.gatevidyalay.com/floyd-warshall-algorithm-shortest-path-algorithm/