# Untitled

unknown
plain_text
a year ago
1.9 kB
20
Indexable
Never
```/*
Time: O(n^3)
Space: O(n^2)
*/
//http://www.shafaetsplanet.com/?p=1927
#define MAX         1000
#define INF         1000000000

int dis[MAX][MAX];
int next[MAX][MAX];

int edges,vertices;

void floyd_warshall()
{
memset(dis, INF, sizeof(dis));
int u,v,cost;
for( int i = 0 ; i<edges ; i++ )
{
scanf("%d %d %d", &u, &v, &cost);
dis[u][v]=cost;
}

for( int i = 0 ; i<vertices ; i++ )
{
for( int j = 0 ; j<vertices ; j++ )
{
next[i][j]= j;
}
}

//Main Algo

for( int k = 0 ; k < vertices ; k++ )
{
for( int i = 0 ; i<vertices ; i++ )
{
for( int j = 0 ; j<vertices ; j++ )
{
if( dis[i][k]+dis[k][j]<dis[i][j] )
{
dis[i][j] = dis[i][k]+dis[k][j];
next[i][j] = next[i][k];
}
}
}
}

//End of Main algo

void find_path( int src , int dest , vector<int>& path)
{
path.push_back(src)

int u = src
while(u != dest )
{
u = next[u][dest];
path.push_back(u);
}
}
}

//by  next[i][j] value I can find the next node of i
//which we need to pass through when going from i to j
//Example:
// Let the path is i->k1->k2->j then,
// next[i][j] == k1 ; next[k1][j] == k2 ; next[k2][j] == j
//initially all next[i][j] = j then we update the matrix according to the path.

// Transitive closure: if there is a direct/indirect path between i to j. input dis[u][v] = 1 if path else 0 (no need to assign cost)
/*
for(int k = 0; k < vertices; ++k)
for(int i = 0; i < vertices; ++i)
for(int j = 0; j < vertices; ++j)
dis[i][j] = dis[i][j] | (dis[i][k] & dis[k][j]);
*/
```