다익스트라 알고리즘은 N개의 노드를 가진 그래프가 주어졌을때 특정 노드를 시작 노드로 잡고, 시작 노드부터 N개의 노드 까지(시작 노드를 포함한)의 모든 경로중 최소 비용의 경로를 찾아내는 알고리즘이다.순서는 대략 이러하다.
1. 방문하지 않은 노드중 최소 비용을 가진 노드를 선택한다.
( 방문 했다함은 해당 노드는 완벽한 최단 거리가 구해졌다는 의미이다. )
( 여기서 최소 비용은 현재 판단했을때의 최소 비용을 의미한다. 이 비용은
추후 바뀔수가 있다 )
2. 선택한 노드를 방문한것으로 기록한다.
3. 방문중인 노드( 선택한 노드 )의 인접한 노드들에 대한 비용을 산출한다.
( 방문중인 노드가 가진 최단비용(v_cost) 과 인접한 노드(adjNode) 와의 간선에 대한 가중치(weight)를 더해 비용을 산출한다, 즉 adjNode's cost = v_cost + weight )
4. 만약 3번 과정중 인접한 노드의 비용이 이미 산출되있다면, 새로 산출한 비용과 비교해보고 만약 더 작다면 인접 노드의 비용을 새로 산출한 비용으로 바꾸고 경로도 새로운 경로로 바꾼다.( 방문 노드를 경유하는 경로를 의미한다 )
순서는 대략 이러한데, 사실 순서보다는 최소 비용을 가진 노드를 선택하고 확장해가는 이런 탐욕법이 왜 작동하는가를 아는게 더 중요하다. a, b, c란 세개의 노드로 그 이유를 이해해보자.
* 다익스트라 알고리즘에서 모든 가중치는 양수이다.
a 노드는 최단 경로와 최단 경로의 따른 비용 k가 구해진 상태이다. 즉 비용 k는 더이상 낮아 질수 없음을 보장하는 상태이다( 이하 보장된 노드라 하겠다 ). 그 상태에서 보다시피 b, c 노드로 갈수있는 각각 가중치 4와 2를 가진 두개의 경로가있다. 그럼 여기서 한번 생각을 해보자. a 의 인접한 노드인 b와 c가 가진 k+4, k+2란 값이 과연 a의 k값처럼 더이상 낮아질수 없는 값이며 b와 c가 보장된 노드인지를 판단할수있을까? 를 말이다. 우선 c 노드부터 한번 봐보자. c 노드는 k+2의 값을 가진다. 그럼 여기서 우리가 판단해야될것은 K+2가 K+4와 임의의 가중치 t를 더한값 보다 더 작은가이다. (왜냐하면 a에서 c로 갈수있는 길은 a->c 제외하면 a->b->c 밖에 없기때문이다. ) 즉 K+2 < K+4+t 인가 말인데, 수식에서 보다시피 당연히 성립한다. t값을 알던 모르던 K+4+t는 무조건 K+2 보다 작을수 없다. 즉 a->c의 경로가 c의 최단 경로이며 곧 c 의 k+2가 더이상 낮아질수 없는 비용이된다. 다시말해 k란 보장된 노드를 알면 우리는 c도 보장된 노드임을 알수가있다는 것이다. 하지만 여기서 반대로 b노드에 대해, K+4 < K+2+t 를 한번 생각해보자. 이는 보장되는가? 아니다. t 값이 어떤 값이냐에 따라 다르다. 그렇기 때문에 위 순서에서 4번처럼 이경우에는 t값에 따른 비교를 해보아야만 한다. 비교해 더 적은 비용쪽으로 바꾼다, 그다음 보장된 노드인 c부터 위 과정을 반복하면 언젠가는 N개의 노드에 대해 모든 최단비용을 구할수가있다는게 다익스트라 알고리즘이다.
■ 구현
#include <iostream>
#include <memory>
#include <limits>
#include <list>
using namespace std;
typedef unsigned int COST;
const int NODECNT = 5;
struct Node
{
COST cost = UINT_MAX;
list<int> path;
};
void Dijkstra(int startNodeId, Node nodeList[], int edgeMap[][NODECNT]);
void PrintNode(int nodeId, const Node& node);
int main()
{
/* 그래프 자료구조를
대체하기 위한 변수들.*/
Node nodeList[NODECNT];
int edgeMap[NODECNT][NODECNT] = {};
edgeMap[0][1] = 5;
edgeMap[0][2] = 10;
edgeMap[1][2] = 3;
edgeMap[1][3] = 2;
edgeMap[1][4] = 9;
edgeMap[2][1] = 2;
edgeMap[2][4] = 1;
edgeMap[3][0] = 7;
edgeMap[3][4] = 6;
edgeMap[4][3] = 4;
Dijkstra(0, nodeList, edgeMap);
for (int i = 0; i < NODECNT; ++i)
{
PrintNode(i, nodeList[i]);
}
return 0;
}
void Dijkstra(int startNodeId, Node nodeList[], int edgeMap[][NODECNT])
{
bool visitedNodes[NODECNT] = {};
int unvisitedCnt = NODECNT;
nodeList[startNodeId].cost = 0;
nodeList[startNodeId].path.push_back(startNodeId);
int bestNodeId = startNodeId;
while (unvisitedCnt)
{
// 방문하지 않은 노드중 최소 비용을 가진 노드 구하기
for (int i = 0; i < NODECNT; ++i)
{
if (visitedNodes[i])
continue;
if (nodeList[bestNodeId].cost > nodeList[i].cost)
{
bestNodeId = i;
}
}
// 노드 방문 처리
visitedNodes[bestNodeId] = true;
unvisitedCnt--;
int tempBestNodeId = bestNodeId;
// 방문 노드의 인접한 노드들에 대한 비용 업데이트
for (int i = 0; i < NODECNT; ++i)
{
if (edgeMap[bestNodeId][i] == 0)
continue;
if (visitedNodes[i])
continue;
COST tempCost = nodeList[bestNodeId].cost + edgeMap[bestNodeId][i];
if (tempCost < nodeList[i].cost)
{
nodeList[i].cost = tempCost;
nodeList[i].path.clear();
for (auto& nodeId : nodeList[bestNodeId].path)
{
nodeList[i].path.push_back(nodeId);
}
nodeList[i].path.push_back(i);
}
/* 인접한 노드중 임의의 노드를 bestid로 선택함.
다음 루프에서 비용 비교연산할때 쓰기 위해서*/
tempBestNodeId = i;
}
bestNodeId = tempBestNodeId;
}
}
void PrintNode(int nodeId, const Node& node)
{
cout << "==" << nodeId << "node's cost : " << node.cost<< endl;
cout << "==" << nodeId << "node's path ==" << endl;
for (auto& id : node.path)
{
cout << id <<endl;
}
}
|
그래프를 따로 만들기는 귀찮아서 대충 노드와 간선정보를 담은 배열을 선언해서 활용했다.
그래프는 위 그림과 같이 구성했다. 내 코드에서는 s =0 , y = 1, t = 2, z = 3, x = 4 이다.
( 출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/26/dijkstra/ )
■ 소스코드
Downloading Dijkstra_vs2015_project
그래프는 위 그림과 같이 구성했다. 내 코드에서는 s =0 , y = 1, t = 2, z = 3, x = 4 이다.
( 출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/26/dijkstra/ )
■ 소스코드
Downloading Dijkstra_vs2015_project
댓글 없음:
댓글 쓰기