다익스트라(Dijkstra) 알고리즘 - 힙사용하지 않을 경우

1. 소스 코드

아래 블로그에 관련 내용은 잘 정리되어 있어서 따라 해 보았다.

메뉴를 만들어서 각 단계별로 동작을 확인하는 메뉴로 각 단계별 동작을 확인하였다.

좀 더 수식적으로 접근하는 블로그를 보았던 것 같은데, 수식적으로 각 단계별로 최소값을 노드로 선택해서 이동 시

출발 노드에서 각 노드간 길이가 최소가 되는지 의문이긴 하다. 수식으로 증명하는 부분을 봤으면 한다.

http://hsp1116.tistory.com/42

#include <iostream> #include <vector> #include <tuple> #include <limits> #include <iomanip> #include <bitset> #define INF 0x1FFFFFFF enum { G_EDGE = 0, G_WEIGHT } GRAPH_TUPLE_INDEX; enum { R_WEIGHT = 0, R_PREV_IDX, R_VISIT } RESULT_TUPLE_INDEX; int N = 5; int g_menu_choice; int getArraryIndex(int idx) { if(idx > N) { std::cout << "out of range" << std::endl; return -1; } return idx - 1; } void loadInitData(std::vector<std::vector<std::tuple<int,int>>> &G, std::vector<std::tuple<int,int,bool>> &R) { std::vector<std::tuple<int,int,int>> edgeInfo = { std::make_tuple(getArraryIndex(1), getArraryIndex(3), 6), std::make_tuple(getArraryIndex(1), getArraryIndex(4), 3), std::make_tuple(getArraryIndex(2), getArraryIndex(1), 3), std::make_tuple(getArraryIndex(3), getArraryIndex(4), 2), std::make_tuple(getArraryIndex(4), getArraryIndex(2), 1), std::make_tuple(getArraryIndex(4), getArraryIndex(3), 1), std::make_tuple(getArraryIndex(5), getArraryIndex(2), 4), std::make_tuple(getArraryIndex(5), getArraryIndex(4), 2), }; for(auto v : edgeInfo) { int vertex = std::get<0>(v); int edge = std::get<1>(v); int weight = std::get<2>(v); G[vertex].emplace_back(edge, weight); } for(int i = 0; i < N; i++) { // weight, previous idx, isvisited R.emplace_back(INF, -1, false); } } void printGraph(const std::vector<std::vector<std::tuple<int,int>>> &G) { for(int i = 0; i < N; i++) { std::printf("Vertex : [%d] ", i+1); for(auto e : G[i]) { int index = std::get<G_EDGE>(e); std::printf("-> %d", index+1); } std::cout << std::endl; } std::cout << std::endl; } int getMinIdx(const std::vector<std::tuple<int,int,bool>> &R) { int mIdx = -1; int min = INF; for(int i = 0; i < R.size(); i++) { if(std::get<R_VISIT>(R[i]) == false) { if(std::get<R_WEIGHT>(R[i]) < min) { min = std::get<R_WEIGHT>(R[i]); mIdx = i; } } } return mIdx; } void dijkstra(int sIdx, const std::vector<std::vector<std::tuple<int,int>>> &G, std::vector<std::tuple<int,int,bool>> &R, std::vector<std::vector<int>> &IRS) { int mIdx; std::get<0>(R[sIdx]) = 0; while( (mIdx = getMinIdx(R)) != -1) { std::vector<int> tv; std::get<2>(R[mIdx]) = true; for(auto &c : R) { tv.emplace_back(std::get<0>(c)); } IRS.emplace_back(tv); for(auto &t : G[mIdx]) { int edge = std::get<G_EDGE>(t); int weight = std::get<G_WEIGHT>(t); if( std::get<R_WEIGHT>(R[edge]) >= weight + std::get<R_WEIGHT>(R[mIdx]) ) { std::get<R_WEIGHT>(R[edge]) = weight + std::get<R_WEIGHT>(R[mIdx]); std::get<R_PREV_IDX>(R[edge]) = mIdx; } } } } void printResult(const std::vector<std::tuple<int,int,bool>> &R) { for(auto &c : R) { std::printf("%d ", std::get<R_WEIGHT>(c)); } std::cout << std::endl; } void printIntermediatResult(const std::vector<std::vector<int>> &IRS) { int idx = 1; for(auto &v : IRS) { std::printf("%2d] ", idx++); for(auto &c : v) { if(c == INF) std::printf("INF "); else std::printf("%3d ", c); } std::cout << std::endl; } std::cout << std::endl; } void printPaths(int sIdx, const std::vector<std::tuple<int,int,bool>> &R) { for(int i = 0; i < R.size(); i++) { int pIdx = i; std::printf("%d 까지 경로(distance = %d) : ", i+1, std::get<R_WEIGHT>(R[i])); while(1) { if(pIdx == sIdx) { std::printf("%d ", pIdx+1); break; } std::printf("%d <- ", pIdx+1); pIdx = std::get<R_PREV_IDX>(R[pIdx]); } std::cout << std::endl; } } bool select_menu() { std::cout << "=====================================================" << std::endl; std::cout << "1. Display Graph " << std::endl; std::cout << "2. Display Final Result " << std::endl; std::cout << "3. Display Intermediate Result " << std::endl; std::cout << "4. Display Paths " << std::endl; std::cout << "0. Exit " << std::endl; std::cout << "=====================================================" << std::endl; std::cout << " >> "; std::cin >> g_menu_choice; std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); std::cout << std::endl; if (std::cin.fail() == true) { std::cout << "invalid input .. " << std::endl; std::cin.clear(); std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); return false; } return true; } int main() { int sIdx; std::vector<std::vector<std::tuple<int,int>>> G(N); std::vector<std::tuple<int,int,bool>> R; std::vector<std::vector<int>> IRS; // intermediate results #if 0 std::cout << " number of vertex >> "; std::cin >> N; std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); std::cout << std::endl; sIdx = getArraryIndex(5); G.resize(N); #else sIdx = getArraryIndex(5); #endif loadInitData(G, R); dijkstra(sIdx, G, R, IRS); while (1) { if (select_menu() == false) { continue; } switch (g_menu_choice) { case 0: return 0; break; case 1: printGraph(G); break; case 2: printResult(R); break; case 3: printIntermediatResult(IRS); break; case 4: printPaths(sIdx, R); break; } } return 0; }

2. 실행 결과

각 메뉴별 실행 결과.

heesoon.kim@LGEBIDRNDPT04:~/personal/test4$ ./test

=====================================================

1. Display Graph

2. Display Final Result

3. Display Intermediate Result

4. Display Paths

0. Exit

=====================================================

 >> 1

Vertex : [1] -> 3-> 4

Vertex : [2] -> 1

Vertex : [3] -> 4

Vertex : [4] -> 2-> 3

Vertex : [5] -> 2-> 4

=====================================================

1. Display Graph

2. Display Final Result

3. Display Intermediate Result

4. Display Paths

0. Exit

=====================================================

 >> 2

6 3 3 2 0

=====================================================

1. Display Graph

2. Display Final Result

3. Display Intermediate Result

4. Display Paths

0. Exit

=====================================================

 >> 3

 1] INF INF INF INF   0

 2] INF   4 INF   2   0

 3] INF   3   3   2   0

 4]   6   3   3   2   0

 5]   6   3   3   2   0

=====================================================

1. Display Graph

2. Display Final Result

3. Display Intermediate Result

4. Display Paths

0. Exit

=====================================================

 >> 4

1 까지 경로(distance = 6) : 1 <- 2 <- 4 <- 5

2 까지 경로(distance = 3) : 2 <- 4 <- 5

3 까지 경로(distance = 3) : 3 <- 4 <- 5

4 까지 경로(distance = 2) : 4 <- 5

5 까지 경로(distance = 0) : 5

=====================================================

1. Display Graph

2. Display Final Result

3. Display Intermediate Result

4. Display Paths

0. Exit

=====================================================

 >>