플로이드 워셜

모든 정점 간의 최소 비용 한꺼번에 계산.

 

• 모든 정점에 대해서 2차원 배열로 비용 테이블 제작.
• 서로 비 연결 비용은 INF로 설정.
• 출발지 a, 도착지 b 가 있을 때, 비용이 k를 경유해서 가는 비용보다 비싸면 경유했을 때 비용으로 갱신.
  • 순환 순서는. 먼저 경유 노드를 고르고, 나머지 모든 경로에 대해 경유 노드를 거칠 때 비용을 비교하여 갱신

 

int a[4][4] = {
        { 0, 5, INF, 8 },
        { 7, 0, 9, INF },
        { 2, INF, 0, 4 },
        { INF, INF, 3, 0 }
    };

    //k=거쳐가는 노드
    for (int k = 0; k < 4; ++k)
    {
        //i = 출발 노드
        for (int i = 0; i < 4; ++i)
        {
            if (k == i)
                continue;
            //j = 도착 노드
            for (int j = 0; j < 4; ++j)
            {
                if (k == j)
                    continue;

                if (a[i][j] > a[i][k] + a[k][j])
                    a[i][j] = a[i][k] + a[k][j];
            }
        }
    }

    //결과 출력
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            printf("%3d ", a[i][j]);
        }
        printf("\n");
    }