# Floyd-Warshall's Algorithm.c

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].
```