[Floyd] 플로이드 알고리즘

[Floyd] 플로이드 알고리즘

(graph 최단거리 알고리즘)

#include <stdio.h>
 
#define SIZE    101
#define INF        1000
 
int graph[SIZE][SIZE];
int floyd[SIZE][SIZE];
 
void init() {
    int i, j;
 
    for (i = 0; i < SIZE; i++) {
        for (j = 0; j < SIZE; j++) {
            graph[i][j] = floyd[i][j] = INF;
        }
    }
}
 
void dofloyd(int n)
{
    int i, j, k;
 
    // copy graph to floyd
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            floyd[i][j] = graph[i][j];
        }
    }
 
    for (k = 1; k <= n; k++) {
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (floyd[i][k] + floyd[k][j] < floyd[i][j]) {
                    floyd[i][j] = floyd[i][k] + floyd[k][j];
                }
            }
        }
    }
}
 
int main()
{
    int n, m;
    int i;
    int from, to;
 
    scanf("%d %d", &n, &m);
 
    init();
 
    for (i = 0; i < m; i++) {
 
        scanf("%d %d", &from, &to);
 
        graph[from][from] = graph[to][to] = 0;
        graph[from][to] = graph[to][from] = 1;
    }
 
    dofloyd(n);
 
    return 0;
}