Floyd-Warshall

• เป็น Algorithm หา Shortest Path ให้ทุกสองจุดใดๆ (หมายความว่า สามารถบอก Shortest Path จากจุด u ไป v ได้เลย)
• โดยใช้ Time: O(V^3)
• เก็บเป็น Adjacency Matrix ใช้ Space: O(V^2)
• เริ่มต้นต้องกำหนดให้ระยะทาง dist[u][v] ทุกๆช่องเป็น INF ก่อน (INF คือเสมือนกับว่าไม่มีทางเดินจาก u->v)

/*
    " FLOYD-WARSHALL"
    AUTHOR: ROOS
    DATE: 23/3/2012
*/
#include<stdio.h>
#define N_VERTEX 1000
#define INF 1000000000
int dist[N_VERTEX+5][N_VERTEX+5], nVertex, nEdge;
int main()
{
    int u, v, weight;
    scanf("%d%d",&nVertex,&nEdge);
    //Initial
    for(int i=1; i<=nVertex; i++)
        for(int j=1; j<=nVertex; j++)
            dist[i][j] = INF;
    //Input
    for(int i=1; i<=nEdge; i++)
    {
        scanf("%d%d%d",&u,&v,&weight);
        dist[u][v] = weight;           //not any two edge have same (u,v)
        dist[v][u] = weight;           //not any two edge have same (u,v)
    }
    //Floyd-Warshall O(V^3)
    for(int k=1; k<=nVertex; k++)
        for(int i=1; i<=nVertex; i++)
            for(int j=1; j<=nVertex; j++)
                if(dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
    
    //Show Result
    printf("===== Shortest Path =====\n");
    for(int i=1; i<=nVertex; i++)
        for(int j=1; j<=nVertex; j++)
            printf("from %d\tto %d\t= %d\n",i,j,dist[i][j]);
    scanf(" ");
    return 0;
}
/*
5 5
1 3 5
1 2 3
1 5 9
2 5 2
3 4 1
*/