Untitled

/*
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]);
 */