All Pairs Shortest Path (Floyd–Warshall)

Floyd Warshall একটা গ্রাফের প্রতিটা নোড থেকে প্রতিটা নোডের দূরত্ব বের করে। খুব সহজ। এখনি নেটে সার্চ দাও। একবার দেখলেই পেরে যাবে। :)

#define MAX 100
#define INF (1<<30) // 2^30

int dis[MAX][MAX]; // distance

void floyd_warshall()
{
    for(int i=0;i<MAX;i++)
    {
        for(int j=0;j<MAX;j++)
        {
            if(i==j) dis[i][j] = 0; // distance from a node to itself is 0
            else dis[i][j] = INF; // initially distance from node i to j is INF
        }
    }

    /*

    here construct the graph with distance
    If a connection exists between node 2 and 5 with distance 8, update

    dis[2][5] = 8;
    dis[5][2] = 8;

    */
    
// ****************  Floyd Warshall *******************
    for(int k=0;k<MAX;k++)
    {
        for(int i=0;i<MAX;i++)
        {
            for(int j=0;j<MAX;j++)
            {
                dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    return ;
}

Problem

UVA - 821, 341, 534, 10048, 544