[잡다한코딩] 플로이드워셜 알고리즘 짜보기

http://hmjo.tistory.com/195

옛날 코드 보니깐 추억이 새록새록.

블로그에 코드가 잘못 되었다고 댓글이 달려서 오랜만에 복습을 했다.

일단 그림이 잘못 되어 있던 것을 좀 고치고.

코드는 문제가 없는데..ㅋㅋㅋㅋ 코드 짜 놓은게 ..

거의 한 천만년전 C98 코드 같아서 다시 짜봤다.

예전에 경로 추적도 이해 안되서 빼먹고 막 짰던거 같은데 ㅋㅋㅋ

VS2015 기준 C++11

소스

#include <iostream>
#include <vector>
#include <stack>
 
using Elems = std::vector<int>;
using CostTable = std::vector<Elems>;
using ViaTable = std::vector<Elems>;
using PathTable = std::vector<Elems>;
 
const int VERTEX = 4;
const int INF = 0xFFFFFF;
const int NIL = -0xFFFFFF;
 
void PrintTable(const std::vector<Elems>&);
void PrintPath(const PathTable&);
void DoFloyd(const ViaTable&, CostTable&, PathTable&);
 
int main()
{
    ViaTable viaTable;
    viaTable.reserve(VERTEX);
    viaTable.push_back(Elems({ 0,3,INF,INF }));
    viaTable.push_back(Elems({ INF,0,12,6 }));
    viaTable.push_back(Elems({ INF,5,0,7 }));
    viaTable.push_back(Elems({ 2,9,4,0 }));
 
    PrintTable(viaTable);
 
    CostTable costTable = viaTable;
 
    PathTable pathTable;
    pathTable.reserve(VERTEX);
    pathTable.push_back(Elems({ NIL,0,NIL,3 }));
    pathTable.push_back(Elems({ 0,NIL,1,1 }));
    pathTable.push_back(Elems({ NIL,2,NIL,2 }));
    pathTable.push_back(Elems({ 3,3,3,NIL }));
 
    DoFloyd(viaTable, costTable, pathTable);
 
    PrintTable(costTable);
    PrintTable(pathTable);
    PrintPath(pathTable);
 
    return 0;
}
 
void PrintTable(const std::vector<Elems>& someTable)
{
    for (auto& elems : someTable)
    {
        for (auto& elem : elems)
        {
            if (elem == INF)
            {
                std::cout << "f\t";
            }
            else if (elem == NIL)
            {
                std::cout << "n\t";
            }
            else
            {
                std::cout << elem << "\t";
            }
        }
 
        std::cout << std::endl;
    }
 
    std::cout << std::endl;
}
 
void PrintPath(const PathTable& path)
{
    for (size_t i = 0; i < VERTEX; i++)
    {
        for (size_t j = 0; j < VERTEX; j++)
        {
            if (path[i][j] == NIL)
            {
                continue;
            }
 
            int prev = j;
            std::stack<int> temp;
 
            temp.push(prev);
 
            while (i != path[i][prev])
            {
                if (prev == path[i][prev])
                {
                    break;
                }
 
                prev = path[i][prev];
                temp.push(prev);
            }
 
            std::cout << i << " to " << j << " path = " << i;
 
            while (!temp.empty())
            {
                std::cout << "->" << temp.top();
                temp.pop();
            }
 
            std::cout << std::endl;
        }
    }
}
 
void DoFloyd(const ViaTable& via, CostTable& cost, PathTable& path)
{
    for (size_t k = 0; k < VERTEX; k++)
    {
        for (size_t i = 0; i < VERTEX; i++)
        {
            for (size_t j = 0; j < VERTEX; j++)
            {
                if (cost[i][j] > cost[i][k] + cost[k][j])
                {
                    cost[i][j] = cost[i][k] + cost[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

결과

이 그래프를 바탕으로 테스트를 했는데..

path 초기 테이블에 순환 구조인 경우 1 <-> 3은 서로 같은 직전 path가 되기 때문에

path 최종 테이블의 결과값이 다르게 되고 자칫 잘못하면 path 추적에서 무한루프가 생길 수 있다.

prev == path[i][prev] 같다면 break를 살포시 밟아주긴 했다....

여튼 뭐 일단은 버그 없이 잘 돌아가니깐 여기서 마무리!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!