#include<iostream> #include<algorithm> #include<vector> #include<queue> #include <list> using namespace std; struct Vertex { }; vector<Vertex> vertices; vector<vector<int>> adajacent; // 인접행렬 void CreateGraph() { vertices.resize(6); adajacent = vector<vector<int>>(6, vector<int>(6, -1)); adajacent[0][1] = 15; adajacent[0][3] = 35; adajacent[1][0] = 15; adajacent[1][2] = 5; adajacent[1][3] = 10; adajacent[3][4] = 5; adajacent[5][4] = 5; } void dijkstra(int here) { struct VertexCost { int vertex; int cost; }; list<VertexCost> discovered; // 발견목록, Queue로는 구현할수 없음. 물론 우선순위 큐로 구현할 수 있긴한데 나중 얘기 vector<int> best(6, INT32_MAX); // 각 정점별로 지금까지 발견한 최소 거리 vector<int> parent(6, -1); discovered.push_back(VertexCost{here,0}); best[here] = 0; parent[here] = here; while (discovered.empty() == false) { // queue에다가 front pop 해서 했겠지만, // 발견한 정점이 여러개 있겠지만 그 중에서 가장 좋은 후보를 찾는다. list<VertexCost>::iterator bestIt; int bestCost = INT32_MAX; for (auto it = discovered.begin(); it != discovered.end(); it++) { const int vertex = it->vertex; const int cost = it->cost; if (bestCost > cost) { bestCost = cost; bestIt = it; } } int cost = bestIt->cost; here = bestIt->vertex; //제일 좋은 후보를 찾은 다음에 팝 하는 것 처럼 삭제. discovered.erase(bestIt); //방문? 더 짧은 경로를 뒤늦게 찾았다면 스킵 if (best[here] < cost) continue; //방문! for (int i = 0; i < adajacent[here].size(); i++) { if (adajacent[here][i] == -1) continue; //더 좋은 경로를 과거에 찾았으면 스킵 int nextCost = best[here] + adajacent[here][i]; if (nextCost >= best[i]) continue; best[i] = nextCost; parent[i] = here; discovered.push_back(VertexCost{i,nextCost}); } } } int main() { CreateGraph(); dijkstra(0); }
while (discovered.empty() == false) { // queue에다가 front pop 해서 했겠지만, // 발견한 정점이 여러개 있겠지만 그 중에서 가장 좋은 후보를 찾는다. list<VertexCost>::iterator bestIt; int bestCost = INT32_MAX; for (auto it = discovered.begin(); it != discovered.end(); it++) { const int vertex = it->vertex; const int cost = it->cost; if (bestCost > cost) { bestCost = cost; bestIt = it; } } int cost = bestIt->cost; here = bestIt->vertex; //제일 좋은 후보를 찾은 다음에 팝 하는 것 처럼 삭제. discovered.erase(bestIt);
이부분 느림 , 우선순위 큐로 구현해야 함.
우선순위큐로 구현.
중요사항 우선순위큐를 사용하기 위해선, 현재 구조가 struct이다 보니 오퍼레이터를 따로 만들어줘야 했음.
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include <list> using namespace std; struct Vertex { }; vector<Vertex> vertices; vector<vector<int>> adajacent; // 인접행렬 void CreateGraph() { vertices.resize(6); adajacent = vector<vector<int>>(6, vector<int>(6, -1)); adajacent[0][1] = 15; adajacent[0][3] = 35; adajacent[1][0] = 15; adajacent[1][2] = 5; adajacent[1][3] = 10; adajacent[3][4] = 5; adajacent[5][4] = 5; } void dijkstra(int here) { struct VertexCost { int vertex; int cost; bool operator<(const VertexCost& rtn) const { return this->cost < rtn.cost; } bool operator>(const VertexCost& rtn) const { return this->cost > rtn.cost; } bool operator==(const VertexCost& rtn) const { return this->cost == rtn.cost; } }; priority_queue<VertexCost> discovered; // 발견목록, Queue로는 구현할수 없음. 물론 우선순위 큐로 구현할 수 있긴한데 나중 얘기 vector<int> best(6, INT32_MAX); // 각 정점별로 지금까지 발견한 최소 거리 vector<int> parent(6, -1); discovered.push(VertexCost{here,0}); best[here] = 0; parent[here] = here; while (discovered.empty() == false) { int cost = discovered.top().cost; here = discovered.top().vertex; discovered.pop(); //방문? 더 짧은 경로를 뒤늦게 찾았다면 스킵 if (best[here] < cost) continue; //방문! for (int i = 0; i < adajacent[here].size(); i++) { if (adajacent[here][i] == -1) continue; //더 좋은 경로를 과거에 찾았으면 스킵 int nextCost = best[here] + adajacent[here][i]; if (nextCost >= best[i]) continue; best[i] = nextCost; parent[i] = here; discovered.push(VertexCost{ i,nextCost }); } } int a = 3; } int main() { CreateGraph(); dijkstra(0); }