Floyd-Warshall's Algorithm.c

From Algorithmist
Jump to navigation Jump to search

This is an implementation of Floyd-Warshall's Algorithm in C.

Implementations[edit]

This is the OOP-friendly version:

Graph floyd_warshall( Graph g ) {
   int i, j, k, N = g.size;
   Graph spg; // All-Pairs Shortest path graph

   for ( i = 0; i < N; i++ )
      for ( j = 0; j < N; j++ )
         set_edge_weight( spg, i, j, edge_weight( g, i, j ) );

   for ( k = 0; k < N; k++ )
      for ( i = 0; i < N; i++ )
         for ( j = 0; j < N; j++ )
            if ( edge_weight( spg, i, j ) > edge_weight( spg, i, k ) + edge_weight( spg, k, j ) )
               set_edge_weight( spg, i, j, edge_weight( spg, i, k ) + edge_weight( spg, k, j ) );

   return spg;
}

This is a short concise version:

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.

   for ( k = 0; k < N; k++ )
      for ( i = 0; i < N; i++ )
         for ( j = 0; j < N; j++ )
            dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );

// Now the shortest distance between i and j will be in dist[i][j].