Floyd-Warshall Algorithm

This is another shortest path algorithm and this will work with negative routes too (But NOT negative cycles). But this will take more time than the Dijkstra's shortest path algorithm. See the wikipedia articles for more information.



To get the shortest path from node 1 to node 3 you'd have to find what route is shorter ( 1 to 3 straight or 1 to 2 to 3). Like that you'd have to calculate the graph using 3 loops.

Now here's the C++ code for this program

#include <iostream>

using namespace std;

int N, E;
int graph[100][100];
int start, end;


int main(){
       cin >> N >> E;
       for(int i = 0; i < N; i++){
               for(int j = 0; j < N; j++){
                       graph[i][j] = 9999; // Equal to NO path
                       if(i == j) graph[i][j] == 0; // No distance from a node to that same node
               }
       }

       for(int i = 0; i < E; i++){
               int x, y, d;
               cin >> x >> y >> d;
               graph[x-1][y-1] = graph[y-1][x-1] = d;
       }
       for(int k = 0; k < N; k++){
               for(int i = 0; i < N; i++){
                       for(int j = 0; j < N; j++){
                               graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);
                       }
               }
       }
       while(true){ // Prints out the shortest distances between nodes until the program is terminated
               cin >> start >> end;
               cout << graph[start-1][end-1] << endl;
       }
       return 0;
}

Read More...

Summary only...

If you have any ideas or comments please tell me.