0. 들어가며
- 그래프는 정점의 집합과 정점들을 서로 잇는 에지의 집합으로 구성
- 그래프는 매우 유연한 자료구조
- 객체와 객체 사이의 관계를 표현
- 두 정점 사이에 여러 엣지를 가지기도 하고
- 하나의 엣지에 여러 가중치 부여하기도 하며
- 자신을 가르키는 셀프 엣지도 존재
- 주로 다루는 것은 방향 가중 그래프
1. 그래프 순회 문제
- 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제
- 그래프 탐색 문제로도 불림
1) 너비 우선 탐색 (BFS, Breadth-First Search)
- 시작 정점을 경계에 추가하는 것으로 시작
- 경계는 이전에 방문했던 정점들에 의해 구성
- 현재 경계에 인접한 정점을 반복적으로 탐색
2) 연습 문제 28: BFS 구현하기
#include<string>
#include<vector>
#include<iostream>
#include<set>
#include<map>
#include<queue>
using namespace std;
tmeplate<typename T>
struct Edge
{
unsigned src;
unsigned dst;
T weight;
};
template<typename T>
class Graph
{
public:
Graph(unsigned N) : V(N) {}
auto vertices() const { return V; }
auto& edges() const { return edge_list; }
auto edges(unsigned v) const
{
vector<Edge<T>> edges_from_v;
for(auto& e : edge_list)
{
if(e.src == v)
edges_from_v.emplace_back(e);
}
return edges_from_v;
}
void add_edge(Edge<T>&& e)
{
if(e.src>=1 && e.src<=V && e.dst>=1 && e.dst<=1)
edge_list.emplace_back(e);
else
cerr<<"에러 : 유효 범위를 벗어난 정점! "<<endl;
}
template<typename U>
friend ostream& operator<<(ostream& os, const Graph<U>& G);
private:
unsigned V;
vector<Edge<T>> edge_list;
};
template <typename U>
ostream& operator<<(ostream& os, const Graph<U>& G)
{
for(unsigned i = 1; i < G.vertices() ; i++)
{
os << i <<":\\t";
auto edges = G.edges(i);
for(auto& e : edges)
os<<"{"<<e.dst<<":"<<e.weight<<"},";
os<<endl;
}
return os;
}
template <typename T>
auto create_reference_graph()
{
Graph<T> G(9);
map<unsigned, vector<pair<unsigned, T>>> edge_map;
edge_map[1] = { {2,0}, {5,0} };
edge_map[2] = { {1,0}, {5,0}, {4,0} };
edge_map[3] = { {4,0}, {7,0} };
edge_map[4] = { {2,0}, {3,0}, {5,0}, {6,0}, {8,0} };
edge_map[5] = { {1,0}, {2,0}, {4,0}, {8,0} };
edge_map[6] = { {4,0}, {7,0}, {8,0} };
edge_map[7] = { {3,0}, {6,0} };
edge_map[8] = { {4,0}, {5,0}, {6,0} };
for(auto& i : edge_map)
for(auto& j : i.second)
G.add_edge(Edge<T>{ i.first, j.first, j.second });
return G;
}
template<typename T>
auto breadth_first_search(const Graph<T>& G, unsigned start)
{
queue<unsigned> queue;
set<unsigned> visited;
vector<unsigned> visit_order;
queue.push(start);
while(!queue.empty())
{
auto current_vertex = queue.front();
queue.pop();
if(visited.find(current_vertex) == visited.end())
{
visited.insert(current_vertex);
visit_order.push_back(current_vertex);
for(auto& e : G.edges(current_vertex))
{
if(visited.find(e.dst==visited.end());
queue.push(e.dst);
}
}
}
return visit_order;
}
int main()
{
auto G = create_reference_graph<T>();
cout<<"[입력 그래프]"<<endl;
cout<<G<<endl;
cout<<"[BFS 방문 순서]"<<endl;
auto bfs_visit_order = breadth_first_search(G,1);
for(auto v : bfs_visit_order)
cout<<v<<endl;
}
3) 깊이 탐색 우선 (DFS, Depth-First Search)
- 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식
- BFS와 유사하나 큐 대신 스택을 사용
4) 연습 문제 29: DFS 구현하기
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <stack>
using namespace std;
template <typename T>
struct Edge
{
unsigned src;
unsigned dst;
T weight;
};
template <typename T>
class Graph
{
public:
// N개의 정점으로 구성된 그래프
Graph(unsigned N) : V(N) {}
// 그래프의 정점 개수 반환
auto vertices() const { return V; }
// 전체 에지 리스트 반환
auto& edges() const { return edge_list; }
// 정점 v에서 나가는 모든 에지를 반환
auto edges(unsigned v) const
{
vector<Edge<T>> edges_from_v;
for (auto& e : edge_list)
{
if (e.src == v)
edges_from_v.emplace_back(e);
}
return edges_from_v;
}
void add_edge(Edge<T>&& e)
{
// 에지 양 끝 정점 ID가 유효한지 검사
if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
edge_list.emplace_back(e);
else
cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
}
// 표준 출력 스트림 지원
template <typename U>
friend ostream& operator<< (ostream& os, const Graph<U>& G);
private:
unsigned V; // 정점 개수
vector<Edge<T>> edge_list;
};
template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
for (unsigned i = 1; i < G.vertices(); i++)
{
os << i << ":\\t";
auto edges = G.edges(i);
for (auto& e : edges)
os << "{" << e.dst << ": " << e.weight << "}, ";
os << endl;
}
return os;
}
template <typename T>
auto create_reference_graph()
{
Graph<T> G(9);
map<unsigned, vector<pair<unsigned, T>>> edge_map;
edge_map[1] = { {2, 0}, {5, 0} };
edge_map[2] = { {1, 0}, {5, 0}, {4, 0} };
edge_map[3] = { {4, 0}, {7, 0} };
edge_map[4] = { {2, 0}, {3, 0}, {5, 0}, {6, 0}, {8, 0} };
edge_map[5] = { {1, 0}, {2, 0}, {4, 0}, {8, 0} };
edge_map[6] = { {4, 0}, {7, 0}, {8, 0} };
edge_map[7] = { {3, 0}, {6, 0} };
edge_map[8] = { {4, 0}, {5, 0}, {6, 0} };
for (auto& i : edge_map)
for (auto& j : i.second)
G.add_edge(Edge<T>{ i.first, j.first, j.second });
return G;
}
template <typename T>
auto depth_first_search(const Graph<T>& G, unsigned start)
{
stack<unsigned> stack;
set<unsigned> visited; // 방문한 정점
vector<unsigned> visit_order; // 방문 순서
stack.push(start);
while (!stack.empty())
{
auto current_vertex = stack.top();
stack.pop();
// 현재 정점을 이전에 방문하지 않았다면
if (visited.find(current_vertex) == visited.end())
{
visited.insert(current_vertex);
visit_order.push_back(current_vertex);
for (auto& e : G.edges(current_vertex))
{
// 인접한 정점 중에서 방문하지 않은 정점이 있다면 스택에 추가
if (visited.find(e.dst) == visited.end())
{
stack.push(e.dst);
}
}
}
}
return visit_order;
}
int main()
{
using T = unsigned;
// 그래프 객체 생성
auto G = create_reference_graph<T>();
cout << "[입력 그래프]" << endl;
cout << G << endl;
// 1번 정점부터 DFS 실행 & 방문 순서 출력
cout << "[DFS 방문 순서]" << endl;
auto dfs_visit_order = depth_first_search(G, 1);
for (auto v : dfs_visit_order)
cout << v << endl;
}
5) 실습 문제 13: 이분 그래프 판별하기
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <stack>
using namespace std;
template <typename T>
struct Edge
{
unsigned src;
unsigned dst;
T weight;
};
template <typename T>
class Graph
{
public:
// N개의 정점으로 구성된 그래프
Graph(unsigned N) : V(N) {}
// 그래프의 정점 개수 반환
auto vertices() const { return V; }
// 전체 에지 리스트 반환
auto& edges() const { return edge_list; }
// 정점 v에서 나가는 모든 에지를 반환
auto edges(unsigned v) const
{
vector<Edge<T>> edges_from_v;
for (auto& e : edge_list)
{
if (e.src == v)
edges_from_v.emplace_back(e);
}
return edges_from_v;
}
void add_edge(Edge<T>&& e)
{
// 에지 양 끝 정점 ID가 유효한지 검사
if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
edge_list.emplace_back(e);
else
cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
}
// 표준 출력 스트림 지원
template <typename U>
friend ostream& operator<< (ostream& os, const Graph<U>& G);
private:
unsigned V; // 정점 개수
vector<Edge<T>> edge_list;
};
template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
for (unsigned i = 1; i < G.vertices(); i++)
{
os << i << ":\\t";
auto edges = G.edges(i);
for (auto& e : edges)
os << "{" << e.dst << ": " << e.weight << "}, ";
os << endl;
}
return os;
}
template <typename T>
auto create_bipartite_reference_graph()
{
Graph<T> G(10);
map<unsigned, vector<pair<unsigned, T>>> edge_map;
edge_map[1] = { {2, 0} };
edge_map[2] = { {1, 0}, {3, 0} , {8, 0} };
edge_map[3] = { {2, 0}, {4, 0} };
edge_map[4] = { {3, 0}, {6, 0} };
edge_map[5] = { {7, 0}, {9, 0} };
edge_map[6] = { {4, 0} };
edge_map[7] = { {5, 0} };
edge_map[8] = { {2, 0}, {9, 0} };
edge_map[9] = { {5, 0}, {8, 0} };
for (auto& i : edge_map)
for (auto& j : i.second)
G.add_edge(Edge<T>{ i.first, j.first, j.second });
return G;
}
template <typename T>
auto bipartite_check(const Graph<T>& G)
{
stack<unsigned> stack;
set<unsigned> visited; // 방문한 정점
stack.push(1); // 1번 정점부터 시작
enum class colors { NONE, BLACK, RED };
colors current_color { colors::BLACK }; // 다음 정점에 칠할 색상
vector<colors> vertex_colors(G.vertices(), colors::NONE);
while (!stack.empty())
{
auto current_vertex = stack.top();
stack.pop();
// 현재 정점을 이전에 방문하지 않았다면
if (visited.find(current_vertex) == visited.end())
{
visited.insert(current_vertex);
vertex_colors[current_vertex] = current_color;
if (current_color == colors::RED)
{
cout << current_vertex << "번 정점: 빨간색" << endl;
current_color = colors::BLACK;
}
else
{
cout << current_vertex << "번 정점: 검정색" << endl;
current_color = colors::RED;
}
// 인접한 정점 중에서 방문하지 않은 정점이 있다면 스택에 추가
for (auto e : G.edges(current_vertex))
if (visited.find(e.dst) == visited.end())
stack.push(e.dst);
}
// 현재 정점이 이미 방문한 정점이고,
// 현재 칠할 색상과 같은 색상이 칠해져 있다면 이분 그래프가 아님.
else if (vertex_colors[current_vertex] != colors::NONE &&
vertex_colors[current_vertex] != current_color)
return false;
}
// 모든 정점에 색상이 칠해졌으면 이분 그래프가 맞음
return true;
}
int main()
{
using T = unsigned;
// 그래프 객체 생성
auto BG = create_bipartite_reference_graph<T>();
cout << "[입력 그래프]" << endl;
cout << BG << endl;
if (bipartite_check<T>(BG))
cout << endl << "이분 그래프가 맞습니다." << endl;
else
cout << endl << "이분 그래프가 아닙니다." << endl;
}
2. 프림의 최소 신장 트리 알고리즘
1) 최소 신장 트리 알고리즘
- 정점 집합 V와 가중치를 갖는 에지 집합 E로 구성된 그래프 G = <V,E>가 주어질 때, 모든 정점을 연결하고 연결된 가중치 합이 최소인 트리 T를 구하시오
- 프림 알고리즘은 BFS와 유사하게 경계를 설정하고 이 경계서 가장 가중치가 적은 에지를 선택
- 이를 반복적으로 탐색
2) 연습 문제 30: 프림 알고리즘 구현하기
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <limits>
using namespace std;
template <typename T>
struct Edge
{
unsigned src;
unsigned dst;
T weight;
};
template <typename T>
class Graph
{
public:
// N개의 정점으로 구성된 그래프
Graph(unsigned N) : V(N) {}
// 그래프의 정점 개수 반환
auto vertices() const { return V; }
// 전체 에지 리스트 반환
auto& edges() const { return edge_list; }
// 정점 v에서 나가는 모든 에지를 반환
auto edges(unsigned v) const
{
vector<Edge<T>> edges_from_v;
for (auto& e : edge_list)
{
if (e.src == v)
edges_from_v.emplace_back(e);
}
return edges_from_v;
}
void add_edge(Edge<T>&& e)
{
// 에지 양 끝 정점 ID가 유효한지 검사
if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
edge_list.emplace_back(e);
else
cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
}
// 표준 출력 스트림 지원
template <typename U>
friend ostream& operator<< (ostream& os, const Graph<U>& G);
private:
unsigned V; // 정점 개수
vector<Edge<T>> edge_list;
};
template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
for (unsigned i = 1; i < G.vertices(); i++)
{
os << i << ":\\t";
auto edges = G.edges(i);
for (auto& e : edges)
os << "{" << e.dst << ": " << e.weight << "}, ";
os << endl;
}
return os;
}
template <typename T>
auto create_reference_graph()
{
Graph<T> G(9);
map<unsigned, vector<pair<unsigned, T>>> edge_map;
edge_map[1] = { {2, 2}, {5, 3} };
edge_map[2] = { {1, 2}, {5, 5}, {4, 1} };
edge_map[3] = { {4, 2}, {7, 3} };
edge_map[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} };
edge_map[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} };
edge_map[6] = { {4, 4}, {7, 4}, {8, 1} };
edge_map[7] = { {3, 3}, {6, 4} };
edge_map[8] = { {4, 5}, {5, 3}, {6, 1} };
for (auto& i : edge_map)
for (auto& j : i.second)
G.add_edge(Edge<T>{ i.first, j.first, j.second });
return G;
}
template <typename T>
struct Label
{
unsigned ID;
T distance;
// Label 객체 비교는 거리(distance) 값을 이용
inline bool operator> (const Label<T>& l) const
{
return this->distance > l.distance;
}
};
template <typename T>
auto prim_MST(const Graph<T>& G, unsigned src)
{
// 최소 힙
priority_queue<Label<T>, vector<Label<T>>, greater<Label<T>>> heap;
// 모든 정점에서 거리 값을 최대로 설정
vector<T> distance(G.vertices(), numeric_limits<T>::max());
set<unsigned> visited; // 방문한 정점
vector<unsigned> MST; // 최소 신장 트리
heap.emplace(Label<T>{src, 0});
while (!heap.empty())
{
auto current_vertex = heap.top();
heap.pop();
// 현재 정점을 이전에 방문하지 않았다면
if (visited.find(current_vertex.ID) == visited.end())
{
MST.push_back(current_vertex.ID);
for (auto& e : G.edges(current_vertex.ID))
{
auto neighbor = e.dst;
auto new_distance = e.weight;
// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
// 힙에 추가하고, 거리 값을 업데이트함.
if (new_distance < distance[neighbor])
{
heap.emplace(Label<T>{neighbor, new_distance});
distance[neighbor] = new_distance;
}
}
visited.insert(current_vertex.ID);
}
}
return MST;
}
int main()
{
using T = unsigned;
// 그래프 객체 생성
auto G = create_reference_graph<T>();
cout << "[입력 그래프]" << endl;
cout << G << endl;
auto MST = prim_MST<T>(G, 1);
cout << "[최소 신장 트리]" << endl;
for (auto v : MST)
cout << v << endl;
cout << endl;
}
3. 다익스트라 최단 경로 알고리즘
1) 다익스트라 알고리즘
- 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘
2) 연습 문제 31: 다익스트라 알고리즘 구현하기
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <limits>
#include <algorithm>
using namespace std;
template <typename T>
struct Edge
{
unsigned src;
unsigned dst;
T weight;
};
template <typename T>
class Graph
{
public:
// N개의 정점으로 구성된 그래프
Graph(unsigned N) : V(N) {}
// 그래프의 정점 개수 반환
auto vertices() const { return V; }
// 전체 에지 리스트 반환
auto& edges() const { return edge_list; }
// 정점 v에서 나가는 모든 에지를 반환
auto edges(unsigned v) const
{
vector<Edge<T>> edges_from_v;
for (auto& e : edge_list)
{
if (e.src == v)
edges_from_v.emplace_back(e);
}
return edges_from_v;
}
void add_edge(Edge<T>&& e)
{
// 에지 양 끝 정점 ID가 유효한지 검사
if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
edge_list.emplace_back(e);
else
cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
}
// 표준 출력 스트림 지원
template <typename U>
friend ostream& operator<< (ostream& os, const Graph<U>& G);
private:
unsigned V; // 정점 개수
vector<Edge<T>> edge_list;
};
template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
for (unsigned i = 1; i < G.vertices(); i++)
{
os << i << ":\\t";
auto edges = G.edges(i);
for (auto& e : edges)
os << "{" << e.dst << ": " << e.weight << "}, ";
os << endl;
}
return os;
}
template <typename T>
auto create_reference_graph()
{
Graph<T> G(9);
map<unsigned, vector<pair<unsigned, T>>> edge_map;
edge_map[1] = { {2, 2}, {5, 3} };
edge_map[2] = { {1, 2}, {5, 5}, {4, 1} };
edge_map[3] = { {4, 2}, {7, 3} };
edge_map[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} };
edge_map[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} };
edge_map[6] = { {4, 4}, {7, 4}, {8, 1} };
edge_map[7] = { {3, 3}, {6, 4} };
edge_map[8] = { {4, 5}, {5, 3}, {6, 1} };
for (auto& i : edge_map)
for (auto& j : i.second)
G.add_edge(Edge<T>{ i.first, j.first, j.second });
return G;
}
template <typename T>
struct Label
{
unsigned ID;
T distance;
// Label 객체 비교는 거리(distance) 값을 이용
inline bool operator> (const Label<T>& l) const
{
return this->distance > l.distance;
}
};
template <typename T>
auto dijkstra_shortest_path(const Graph<T>& G, unsigned src, unsigned dst)
{
// 최소 힙
priority_queue<Label<T>, vector<Label<T>>, greater<Label<T>>> heap;
// 모든 정점에서 거리 값을 최대로 설정
vector<T> distance(G.vertices(), numeric_limits<T>::max());
set<unsigned> visited; // 방문한 정점
vector<unsigned> parent(G.vertices()); // 이동 경로를 기억을 위한 벡터
heap.emplace(Label<T>{src, 0});
parent[src] = src;
while (!heap.empty())
{
auto current_vertex = heap.top();
heap.pop();
// 목적지 정점에 도착했다면 종료
if (current_vertex.ID == dst)
{
cout << current_vertex.ID << "번 정점(목적 정점)에 도착!" << endl;
break;
}
// 현재 정점을 이전에 방문하지 않았다면
if (visited.find(current_vertex.ID) == visited.end())
{
cout << current_vertex.ID << "번 정점에 안착!" << endl;
// 현재 정점과 연결된 모든 에지에 대해
for (auto& e : G.edges(current_vertex.ID))
{
auto neighbor = e.dst;
auto new_distance = current_vertex.distance + e.weight;
// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
// 힙에 추가하고, 거리 값을 업데이트함.
if (new_distance < distance[neighbor])
{
heap.emplace(Label<T>{neighbor, new_distance});
parent[neighbor] = current_vertex.ID;
distance[neighbor] = new_distance;
}
}
visited.insert(current_vertex.ID);
}
}
// 백트래킹 방식으로 시작 정점부터 목적 정점까지의 경로 구성
vector<unsigned> shortest_path;
auto current_vertex = dst;
while (current_vertex != src)
{
shortest_path.push_back(current_vertex);
current_vertex = parent[current_vertex];
}
shortest_path.push_back(src);
reverse(shortest_path.begin(), shortest_path.end());
return shortest_path;
}
int main()
{
using T = unsigned;
// 그래프 객체 생성
auto G = create_reference_graph<T>();
cout << "[입력 그래프]" << endl;
cout << G << endl;
auto shortest_path = dijkstra_shortest_path<T>(G, 1, 6);
cout << endl << "[1번과 6번 정점 사이의 최단 경로]" << endl;
for (auto v : shortest_path)
cout << v << " ";
cout << endl;
}
3) 실습 문제 14: 뉴욕에서 최단 경로 찾기
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <limits>
#include <queue>
#include <fstream>
#include <sstream>
#include <algorithm>
using namespace std;
template <typename T>
struct Edge
{
unsigned src;
unsigned dst;
T weight;
};
template <typename T>
class Graph
{
public:
// N개의 정점으로 구성된 그래프
Graph(unsigned N) : V(N) {}
// 그래프의 정점 개수 반환
auto vertices() const { return V; }
// 전체 에지 리스트 반환
auto& edges() const { return edge_list; }
// 정점 v에서 나가는 모든 에지를 반환
auto edges(unsigned v) const
{
vector<Edge<T>> edges_from_v;
for (auto& e : edge_list)
{
if (e.src == v)
edges_from_v.emplace_back(e);
}
return edges_from_v;
}
void add_edge(Edge<T>&& e)
{
// 에지 양 끝 정점 ID가 유효한지 검사
if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
edge_list.emplace_back(e);
else
cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
}
// 표준 출력 스트림 지원
template <typename U>
friend ostream& operator<< (ostream& os, const Graph<U>& G);
private:
unsigned V; // 정점 개수
vector<Edge<T>> edge_list;
};
template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
for (unsigned i = 1; i < G.vertices(); i++)
{
os << i << ":\\t";
auto edges = G.edges(i);
for (auto& e : edges)
os << "{" << e.dst << ": " << e.weight << "}, ";
os << endl;
}
return os;
}
template <typename T>
auto read_graph_from_file()
{
ifstream infile("USA-road-d.NY.gr");
unsigned num_vertices, num_edges;
string line;
// 'p'로 시작하는 문제 설명 행 읽기
// p <num_vertices> <num_edges>
while (getline(infile, line))
{
if (line[0] == 'p')
{
istringstream iss(line);
char p;
string sp;
iss >> p >> sp >> num_vertices >> num_edges;
cout << "정점 개수: " << num_vertices << endl;
cout << "에지 개수: " << num_edges << endl;
break;
}
}
Graph<T> G(num_vertices + 1);
// 'a'로 시작하는 에지 표현 행 읽기
// a <source_vertex> <destination_vertex> <weight>
while (getline(infile, line))
{
if (line[0] == 'a')
{
istringstream iss(line);
char p;
unsigned source_vertex, dest_vertex;
T weight;
iss >> p >> source_vertex >> dest_vertex >> weight;
G.add_edge(Edge<T>{source_vertex, dest_vertex, weight});
}
}
infile.close();
return G;
}
template <typename T>
struct Label
{
unsigned ID;
T distance;
// Label 객체 비교는 거리(distance) 값을 이용
inline bool operator> (const Label<T>& l) const
{
return this->distance > l.distance;
}
};
template <typename T>
auto dijkstra_shortest_path(const Graph<T>& G, unsigned src, unsigned dst)
{
// 최소 힙
priority_queue<Label<T>, vector<Label<T>>, greater<Label<T>>> heap;
// 모든 정점에서 거리 값을 최대로 설정
vector<T> distance(G.vertices(), numeric_limits<T>::max());
set<unsigned> visited; // 방문한 정점
vector<unsigned> parent(G.vertices()); // 이동 경로를 기억을 위한 벡터
heap.emplace(Label<T>{src, 0});
parent[src] = src;
while (!heap.empty())
{
auto current_vertex = heap.top();
heap.pop();
// 목적지 정점에 도착했다면 종료
if (current_vertex.ID == dst)
{
//cout << current_vertex.ID << "번 정점(목적 정점)에 도착!" << endl;
break;
}
// 현재 정점을 이전에 방문하지 않았다면
if (visited.find(current_vertex.ID) == visited.end())
{
//cout << current_vertex.ID << "번 정점에 안착!" << endl;
// 현재 정점과 연결된 모든 에지에 대해
for (auto& e : G.edges(current_vertex.ID))
{
auto neighbor = e.dst;
auto new_distance = current_vertex.distance + e.weight;
// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
// 힙에 추가하고, 거리 값을 업데이트함.
if (new_distance < distance[neighbor])
{
heap.emplace(Label<T>{neighbor, new_distance});
parent[neighbor] = current_vertex.ID;
distance[neighbor] = new_distance;
}
}
visited.insert(current_vertex.ID);
}
}
// 백트래킹 방식으로 시작 정점부터 목적 정점까지의 경로 구성
vector<unsigned> shortest_path;
auto current_vertex = dst;
while (current_vertex != src)
{
shortest_path.push_back(current_vertex);
current_vertex = parent[current_vertex];
}
shortest_path.push_back(src);
reverse(shortest_path.begin(), shortest_path.end());
return shortest_path;
}
int main()
{
using T = unsigned;
// 파일로부터 그래프 객체 생성
auto G = read_graph_from_file<T>();
unsigned src_id = 913;
unsigned dst_id = 542;
auto shortest_path = dijkstra_shortest_path<T>(G, src_id, dst_id);
cout << endl << "[" << src_id << " 정점에서 " << dst_id << " 정점까지의 최단 경로]" << endl;
for (auto v : shortest_path)
cout << v << " ";
cout << endl;
}
