다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라 알고리즘
1) 탐욕 알고리즘의 활용
2) 최단거리를 구하는 알고리즘
3) 음의 가중치(비용 음수)가 없을때 사용가능
다익스트라 알고리즘 순서
1) 출발점부터 체크 시작
2) '체크하는 노드'와 '연결된 노드'의 비용 업데이트
3) 다음 노드는 '체크하지 않은 노드' 중 '누적 비용'이 제일 낮은 노드를 선택
4) 모든 노드를 다 체크할때까지 반복
다익스트라 알고리즘 코드 보기
#include "stdafx.h"
#include "DijkstraAlgorithm.h"
int main()
{
DijkstraAlgorithm dijkstra(7); //초기화, 최대 노드수는 7
//경로 세팅
dijkstra.Set(0, 1, 2); //0 -> 1 : 비용 2
dijkstra.Set(0, 3, 5); //0 -> 3 : 비용 5
dijkstra.Set(1, 2, 6);
dijkstra.Set(1, 4, 10);
dijkstra.Set(2, 6, 3);
dijkstra.Set(3, 4, 4);
dijkstra.Set(3, 5, 5);
dijkstra.Set(4, 5, 1);
dijkstra.Set(4, 6, 7);
dijkstra.Set(5, 6, 2);
//최단경로 검색(0->6)
dijkstra.FindPath(0, 6);
return 0;
}
#pragma once
#define INF 99999999 //무제한
class DijkstraAlgorithm
{
private:
const int m_NumberOfNodes; //최대 노드의 수
int **m_Table; //노드간의 거리(혹은 비용) 테이블
public:
DijkstraAlgorithm(int NumberOfNodes);
~DijkstraAlgorithm();
void Set(int From, int To, int Cost); //경로 세팅
void FindPath(int From, int To); //경로 찾기 시작
private:
void CalPath(int *&Path,int From); //경로 계산
void PrintTable(int *cost, bool *visit, int Length); //테이블 출력
void PrintShortestWay(int From, int To, int *prev); //최단 경로 출력
};
#include "stdafx.h"
#include "DijkstraAlgorithm.h"
DijkstraAlgorithm::DijkstraAlgorithm(int NumberOfNodes): m_NumberOfNodes(NumberOfNodes)
{
//비용 테이블 초기화
m_Table = new int*[NumberOfNodes];
for (int i = 0; i < NumberOfNodes; i++)
{
m_Table[i] = new int[NumberOfNodes];
for (int j = 0; j < NumberOfNodes; j++)
{
if(i == j)
m_Table[i][j] = 0;
else
m_Table[i][j] = INF;
}
}
}
DijkstraAlgorithm::~DijkstraAlgorithm()
{
//비용 테이블 메모리 해제
for (int i = 0; i < m_NumberOfNodes; i++)
{
delete[] m_Table[i];
m_Table[i] = NULL;
}
delete[] m_Table;
m_Table = NULL;
}
//경로 세팅
void DijkstraAlgorithm::Set(int From, int To, int Cost)
{
if (From < m_NumberOfNodes && To < m_NumberOfNodes)
{
m_Table[From][To] = Cost;
}
}
//경로 찾기 시작
void DijkstraAlgorithm::FindPath(int From, int To)
{
//경로 저장 배열 초기화
int *path = new int[m_NumberOfNodes];
//경로 계산
CalPath(path, From);
//최단 경로 출력
PrintShortestWay(From, To, path);
//배열 해제
delete[] path;
path = NULL;
}
//경로 계산
void DijkstraAlgorithm::CalPath(int *&Path, int From)
{
int min, index;
int *cost = new int[m_NumberOfNodes]; //비용
bool *visit = new bool[m_NumberOfNodes]; //방문
//배열 초기화
for (int i = 0; i < m_NumberOfNodes; i++)
{
cost[i] = INF;
visit[i] = false;
Path[i] = -1;
}
//출발위치의 비용->0으로
cost[From] = 0;
//총 노드의 수 만큼 반복
for (int i = 0; i < m_NumberOfNodes; i++)
{
min = INF + 1;
index = -1;
//검색할 노드 찾기
for (int j = 0; j < m_NumberOfNodes; j++)
{
//이미 체크한 노드면 패스
if (visit[j])
continue;
//현재 최소값보다 더 작으면 다음 노드로
if (min > cost[j])
{
min = cost[j];
index = j;
}
}
//노드들 비용 재계산
for (int j = 0; j < m_NumberOfNodes; j++)
{
//현재 비용보다, 지금 노드에서 출발하는 비용이 더싸면 갱신
if (cost[j] > cost[index] + m_Table[index][j])
{
//비용 갱신
cost[j] = cost[index] + m_Table[index][j];
//경로 갱신
Path[j] = index;
}
}
//현재 노드는 방문한 노드로 만듬
visit[index] = true;
//테이블 출력(진행사항 체크용)
PrintTable(cost, visit, m_NumberOfNodes);
}
delete[] cost;
delete[] visit;
cost = NULL;
visit = NULL;
}
//테이블 출력
void DijkstraAlgorithm::PrintTable(int *cost, bool *visit, int Length)
{
//번호 출력
printf("Num\t:\t");
for (int i = 0; i < Length; i++)
printf("%d\t",i);
//비용 출력
printf("\nCost\t:\t");
for (int i = 0; i < Length; i++)
{
if (cost[i] != INF)
printf("%d\t", cost[i]);
else
printf("X\t");
}
//방문 여부 출력
printf("\nVisit\t:\t");
for (int i = 0; i < Length; i++)
printf("%d\t", visit[i]);
printf("\n\n");
}
//최단 경로 출력
void DijkstraAlgorithm::PrintShortestWay(int From, int To, int *prev)
{
//출력할 경로 저장
int *path= new int[m_NumberOfNodes];
//저장된 경로 마지막 위치
int lastIndex = 0;
int final = To; //출발 위치
int start = From; //도착 위치
From = prev[To];
//최종 도착위치 부터 역순으로 경로 추적
while (From != start && From != -1)
{
path[lastIndex++] = To;
To = From;
From = prev[From];
}
//경로가 없다면
if (From == -1)
{
printf("경로가 없습니다\n");
}
//경로가 있다면
else
{
//마지막에 입력안된 노드 입력
path[lastIndex++] = To;
//경로 출력
printf("최적경로 : %d -> ", start);
for (int i = lastIndex - 1; i > 0; i--)
{
printf("%d -> ", path[i]);
}
printf("%d\n", final);
}
delete[] path;
path = NULL;
}