지도를 보면 여러 점이 있고 길마다 거리가 다릅니다. 이때 한 점에서 다른 점으로 이동하기 위한 최단 경로는 어떻게 구할 수 있을까요? 다익스트라 알고리즘(Dijkstra Algorithm)으로 구할 수 있습니다. 오늘은 C++로 다익스트라 알고리즘을 구현해 보겠습니다.
목차
1. 파일 목록
2. class 상속 관계
3. 파일 입력
4. ★★다익스트라 알고리즘
5. ★출발 지점으로부터 도착 지점까지의 최단 경로 및 최단 거리 구하기
6. 나머지는 GitHub repository를 참고하세요.
7. 글 마무리
8. 참고 자료
1. 파일 목록
- .gitignore: x64(folder), *.vcxproj, *.vcxproj.filters, *.vcxproj.user, *.txt, *.o, run을 무시
- Graph.cpp: Graph의 멤버 변수/함수
- Graph.h: 그래프를 위한 class
- LICENSE: MIT License
- ListGraph.cpp: ListGraph의 멤버 변수/함수
- ListGraph.h: list graph를 위한 class
- main.cpp: 콘솔 입출력을 담당하는 main 함수
- makefile: make를 사용하여 빌드하기 위한 파일
- Manager.cpp: Manager의 멤버 변수/함수
- Manager.h: 함수들을 작동시키기 위한 class
- MatrixGraph.cpp: MatrixGraph의 멤버 변수/함수
- MatrixGraph.h: matrix graph를 위한 class
이 글은 일부 코드만 설명합니다. 전체 코드는 https://github.com/sooseongcom/Dijkstra에서 확인하실 수 있습니다.
2. class 상속 관계
ListGraph와 MatrixGraph는 Graph를 상속받습니다.
3. 파일 입력
그래프를 텍스트 파일(*.txt)로 작성합니다. List Graph와 Matrix Graph를 지원하며 양식은 아래와 같습니다.
3.1. List Graph
L
v 0
e 1 2
e 2 5
e 3 1
v 1
e 2 3
e 3 3
v 2
e 1 3
e 5 2
v 3
e 2 4
e 4 1
v 4
e 2 2
e 5 1
v 5
e 5 0
[Line 1]
L은 List Graph라는 뜻입니다.
[Line 2~]
v <from>: vertex를 만들고 선택합니다.e <to> <weight>: 선택된 vertex(<from>)부터<to>까지 연결해 주는 edge를 작성합니다. 거리는<weight>입니다.- 선택된 vertex에서 출발하여 다른 vertex로 가는 edge가 있을 경우 자기 자신으로 가는 edge(거리가 0인 edge)는 생략할 수 있습니다. 다만, 선택된 vertex에서 출발하여 다른 vertex로 가는 edge가 없을 경우 자기 자신으로 가는 edge를 거리 0으로 선언해 주시기 바랍니다(19행 참조).
3.2. Matrix Graph
M
6
0 2 5 1 0 0
0 0 3 3 0 0
0 3 0 0 2 0
0 0 4 0 1 0
0 0 2 0 0 1
0 0 0 0 0 0
[Line 1]
M은 Matrix Graph라는 뜻입니다.
[Line 2]
vertex 개수를 적어 줍니다.
[Line 3~]
Matrix graph를 작성합니다. 열과 열 사이는 공백으로 구분합니다.
4. ★★다익스트라 알고리즘
다익스트라 알고리즘은 출발 지점으로부터 모든 지점까지의 최단 거리를 구하는 알고리즘입니다. 모든 선(edge)은 방향성이 있습니다. 출발 지점(vertex)을 parameter로 입력받는 dijkstra 함수와 vertex에 0을 대입한 예시로 설명 드리겠습니다.
//Graph.cpp Line 12~46
int Graph::dijkstra(int vertex) {
arraysInit(); //Init dist, prev, visited
map<int, int> adjacentEdges;
getAdjacentEdges(vertex, &adjacentEdges);
for (auto iter = adjacentEdges.begin(); iter != adjacentEdges.end(); iter++) {
setVisited(iter->first, false);
setDistance(iter->first, iter->second);
setPrev(iter->first, vertex);
}
setVisited(vertex, true);
setDistance(vertex, 0);
while(1) {
int u = choose(); //choose() returns a value u such that getDistance(u) = minimum getDistance(w) where visited[w]=false
if (u == -1 || getVisited(u) == true) break;
setVisited(u, true);
getAdjacentEdges(u, &adjacentEdges);
for (auto iter = adjacentEdges.begin(); iter != adjacentEdges.end(); iter++) {
if (getVisited(iter->first) == false) {
int u_dist = getDistance(u);
if (getVisited(iter->first) == false && u_dist + iter->second < getDistance(iter->first)) {
setDistance(iter->first, u_dist + iter->second);
setPrev(iter->first, u);
}
}
}
}
return 0;
}
위 코드블록의 행 번호를 기준으로 설명 드리겠습니다.
[Line 3]
dist와 prev는 int형 배열, visited는 bool형 배열입니다.
dist의 모든 원소를 MAX(적당히 큰 숫자. 저는 0xfffffff로 했습니다.)로, visited의 모든 원소를 false로, prev의 모든 원소를 false로 초기화합니다. (함수 별도 구현)
[Line 5~6]
adjacentEdges는 연결된 edge를 저장하기 위한 map입니다. key는 vertex 번호이고, value는 거리입니다. getAdjacentEdges 함수를 이용하여 vertex로부터 연결된 edge를 구합니다.(함수 별도 구현)
[Line 8~12]
adjacentEdges에 저장된 정보를 이용하여 dist를 최단 거리로 업데이트하고 0번 vertex와 edge로 연결된 vertex의 prev를 0으로 설정합니다.
그러고 나서 visited[0]=true;를 실행합니다.
[Line 17~33]
choose() 함수를 이용하여 아직 방문하지 않은 vertex 중 가장 가까운 vertex를 선택합니다(함수 별도 구현). 이번에는 3이네요.
visited[3]=true;를 실행합니다.
연결된 vertex는 2와 4가 있네요. 거리를 비교해 보면
2: 5==1+4 ⇒ dist[2]와 prev[2] 유지
4: MAX>1+1 ⇒ dist[4]=2; prev[4]=3;
이렇게 진행됩니다.
모든 vertex를 방문할 때까지 Line 20~38을 계속 반복합니다. 예시를 이어서 보겠습니다.
아직 방문하지 않은 vertex 중 가장 가까운 vertex는 1입니다.
visited[1]=true;를 실행합니다.
연결된 vertex는 2가 있습니다.(3도 있지만 이미 방문했으므로 건너뜀.)
거리를 비교해 보면 5==2+3이므로 dist[2]와 prev[2]를 유지합니다.
아직 방문하지 않은 vertex 중 가장 가까운 vertex는 4입니다.
visited[4]=true;를 실행합니다.
연결된 vertex는 2와 5가 있네요. 거리를 비교해 보면
2: 5>2+2 ⇒ dist[2]=4; prev[2]=4;
5: MAX>2+1 ⇒ dist[5]=3; prev[5]=4;
이렇게 진행됩니다.
아직 방문하지 않은 vertex 중 가장 가까운 vertex는 5입니다.
visited[5]=true;를 실행합니다.
5번 vertex에는 연결된 vertex가 없네요.(2와 4는 역방향입니다.)
아직 방문하지 않은 vertex 중 가장 가까운 vertex는 2입니다.
visited[2]=true;를 실행합니다.
나머지 vertex를 이미 모두 방문하였으므로 더 이상 업데이트할 것이 없습니다.
그 다음 choose() 함수를 호출하면 -1 또는 이미 방문한 vertex를 반환합니다.
19행 if (u == -1 || getVisited(u) == true) break;에 의해 반복문을 탈출하게 됩니다.
5. ★출발 지점으로부터 도착 지점까지의 최단 경로 및 최단 거리 구하기
위의 다익스트라 알고리즘 소스코드를 실행하면 dist, visited, prev를 업데이트할 뿐 최단 경로가 눈에 바로 보이지는 않습니다. 그러나 우리가 궁금한 것은 출발 지점으로부터 도착 지점까지의 최단 경로와 최단 거리입니다. 이것을 구하기 위해서 저는 void Graph::shortestPath(int start, int dest, vector<int>* result) 함수를 만들었습니다.
//Graph.cpp 48~73
void Graph::shortestPath(int start, int dest, vector<int>* result) {
dijkstra(start);
stack<int> path;
int curr = dest;
while (curr != start && curr != -1) {
path.push(curr);
curr = getPrev(curr);
}
if (curr == start) {
path.push(curr);
}
else { //No path
result->clear();
return;
}
while (!path.empty()) {
result->push_back(path.top());
path.pop();
}
return;
}
[Line 3]
dijkstra(start);
먼저 3번 문단의 dijkstra 함수를 호출하여 다익스트라 알고리즘을 수행합니다. parameter에는 start를 넣습니다.
[Line 5]
stack<int> path;
stack을 하나 선언합니다. stack은 후입선출(LIFO) 자료 구조이죠.
다익스트라 알고리즘을 수행하고 나면 prev 배열을 이용하여 이전 vertex를 알 수 있으므로, 도착 지점(dest)에서부터 prev 배열을 타고 이전 vertex로 가면서 stack에 push한 다음, 그 stack의 원소들을 꺼내면 경로가 깔끔하게 나올 것입니다.
[Line 6]
int curr = dest;
현재 위치를 curr로 표현합니다.
초기 curr는 dest(도착 지점)입니다.
[Line 8~11]
curr != start && curr != -1이면 curr를 path에 push하고 curr에는 prev 배열을 이용하여 이전 vertex를 대입합니다. 이것을 반복합니다.
[Line 13~15]
반복문을 탈출했을 때 curr == start라면 curr를 path에 push합니다.
[Line 16~19]
반복문을 탈출했을 때 curr == -1이라면 경로가 없는 것이므로 result를 clear하고 return합니다.
[Line 21~24]
path가 빌 때까지 result에 path.top()를 삽입하고 path를 pop하는 것을 반복합니다.
참고로 console 출력은 Manager.cpp에서 구현했습니다.
//Manager.cpp Line 117~138
void Manager::shortestPath(int start, int end) {
vector<int> path;
int dist = 0; //distance
if (graph == nullptr) {
cout << "Load graph first." << endl;
}
else {
graph->shortestPath(start, end, &path);
if (path.empty() || graph->getDistance(end) >= MAX) {
cout << "X" << endl; //can't go from start to end
}
else {
for (int i = 0; i < path.size(); i++) {
cout << path[i] << ' ';
}
cout << "(" << graph->getDistance(end) << ")" << endl;
}
}
}
[Line 3]
vector<int> path;
경로를 저장할 vector입니다. Graph.cpp 48~73의 result입니다.
[Line 10]
graph->shortestPath(start, dest, &path);
Graph.cpp 48~73의 함수를 호출합니다.
[Line 12~21]
path의 원소들을 출력합니다.
6. 나머지는 GitHub repository를 참고하세요.
이 글에서 설명하지 않은 부분(파일 입력 구현, arraysinit, choose 등)은 제가 GitHub에 올려 둔 소스코드(https://github.com/sooseongcom/Dijkstra)를 참고하시기 바랍니다.
특히 GitHub에 올려 둔 소스코드를 빌드하면 아래와 같은 명령어를 사용할 수 있으니 참고하시기 바랍니다.
load <filepath>: 그래프 파일(.txt)을 불러옵니다.print: 그래프를 출력합니다.shortestPath <start vertex> <destination vertex>:<start vertex>부터<destination vertex>까지 최단 경로를 탐색합니다.
위 이미지는 사용 예시입니다.
7. 글 마무리
제 글을 읽어 주셔서 감사합니다. 다음에 만나요!
8. 참고 자료
1) KWiOS. 2022. “최단경로 - 다익스트라 알고리즘”, KWiOS0101. (2026. 02. 25. 방문). https://kwios0101.tistory.com/71