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

2017. 1. 7. 15:57엘키스공간/엘키스코딩공방

728x90
728x90

http://hmjo.tistory.com/195


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


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

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

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

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

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


VS2015 기준 C++11


소스


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#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,}));
    viaTable.push_back(Elems({ INF,5,0,}));
    viaTable.push_back(Elems({ 2,9,4,}));
 
    PrintTable(viaTable);
 
    CostTable costTable = viaTable;
 
    PathTable pathTable;
    pathTable.reserve(VERTEX);
    pathTable.push_back(Elems({ NIL,0,NIL,}));
    pathTable.push_back(Elems({ 0,NIL,1,}));
    pathTable.push_back(Elems({ NIL,2,NIL,}));
    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;
                }
            }
        }
    }
}
cs


결과





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

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

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

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

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

728x90
반응형