[ALGORITHM STUDY] 다익스트라 알고리즘 경로 출력

#include <iostream> #include <fstream> #include <vector> #include <queue> #include <functional> using namespace std; #define PAIR pair<int,pair<int, vector<int>>> //pair<거리,pair<index,경로 저장>>> int node_count; vector<vector<pair<int, int>>> graph; vector<int> result_path; void dikstra(int start, int end) { priority_queue <PAIR, vector <PAIR>, greater <PAIR>> cache; //거리가 최소인 것부터 정렬 vector<int> visited = vector<int>(node_count + 1, 0); //visited vector<int> road = vector<int>(node_count + 1, INT_MAX); //최소 경로 - 최대 값으로 저장해놓음 vector<int> way; //경로 임시 저장 visited[start] = 1; way.push_back(start); cache.push(make_pair(0, make_pair(start, way))); while (!cache.empty()) { int distance = cache.top().first; int start_index = cache.top().second.first; way = cache.top().second.second; cache.pop(); visited[start_index] = 1; for (int j = 0; j < graph[start_index].size(); j++) { int dest_index = graph[start_index][j].first; int dest_dist = graph[start_index][j].second; if (visited[dest_index] == 0) //visit되지 않았다면 { if (road[dest_index] > dest_dist + distance) //저장되어있는 거리 > 새로 들어온 거리 { road[dest_index] = dest_dist + distance; //갱신 way.push_back(dest_index); //경로 추가 if (dest_index == end) result_path = way; //그 경로가 목표 노드의 번호 -> 결과에 저장 cache.push(make_pair(road[dest_index], make_pair(dest_index, way))); //cache에 저장 way.erase(way.end() - 1); //경로 삭제 } } } } } int main() { ifstream fcin; fcin.open("다익스트라알고리즘경로출력_input.txt"); int for_count, edge_count, start, end, value; fcin >> for_count; while (for_count--) { result_path.clear(); fcin >> node_count >> edge_count; graph = vector<vector<pair<int, int>>>(node_count + 1); while (edge_count--) { fcin >> start >> end >> value; graph[start].push_back(make_pair(end, value)); //유향 그래프 추가 } dikstra(node_count, 1); //다익스트라 for (int j = 0; j < result_path.size(); j++) cout << result_path[j] << " "; cout << endl; } system("pause"); }