Dijikstra Algorithm : 다익스트라 알고리즘

가중치가 있는 그래프의 경우,

BFS가 아닌 다익스트라 알고리즘을 활용하여 경로를 탐색해준다.

 

임의의 시작점에서 '발견된' vertex를 저장하고 

발견된 vertex 중 방문하는 논리는 BFS와 유사하다. 

 

다만 다익스트라는 이미 발견된 vertex라도 최소 비용을 갖는 지 체크해주며,

발견된 vertex 중 이미 최소 비용의 경로가 존재할 경우 방문을 하지 않는다는 조건이 추가된다.

 

다익스트라를 구현하기에 앞서 필요한 변수와 구조체에 대해 정리해보겠다.

 

해당 vertex를 방문하는 데 필요한 최소 비용을 저장하는 리스트 

vector<int> best(6, INT32_MAX);

초기값은 INT32 자료형의 최대값을 지정해준다. 

 

 

vertex 번호와 비용값을 저장해주는 구조체 선언 후,

struct PathCost
{
    int vertex;
    int cost;
}

 

발견된 vertex의 정보를 저장해주는 리스트 선언.

list<PathCost> discover;

 

발견된 vertex 중 가장 최소 비용을 갖는 list의 element를 저장해주는 iterator 선언.

-> 리스트를 사용하여 해당  vertex로 임의접근하기 위해 선언이 필요하다.

list<PathCost>::iterator bestIt;

 

 

최소 비용의 경로를 계산하기 위한 준비가 끝났다.

이제 다익스트라 알고리즘이 어떠한 논리로 최소 비용을 갖는 경로를 찾는 지 알아보자.

 

 

1. 시작점에서 발견한 vertex 중 최소 비용을 갖는 vertex에 방문하기

int bestCost = INT32_MAX;
list<PathCost>::iterator bestIt;

for(auto it = discover.begin(); it!=discover.end(); it++)
{
    if(it->cost < bestCost)
    {
        bestCost = it->cost;
        bestIt = it;
    }
}

int cost = bestIt->cost; // 이미 최소 비용을 지불했는 지 체크 위해 저장.

here = bestIt->vertex; // 현재 방문 지점 갱신

discover.erase(bestIt); // vertex 방문 후, discover 리스트에서 제거.

 

 

2. 현재 방문한 지점이 이전에 최소 비용으로 방문된 적이 있는 지 체크

if(best[here] < cost)
   continue;

 

 

3. 현재 방문 지점에서 발견된 vertex 찾기

    -> 다음 경로를 찾기 위한 작업

//vertex의 총 개수가 6일 경우
for(int next = 0; next < 6; next++)
{
    if(graph[here][next] == -1)
        continue;
    
    //next vertex로 가는데 드는 비용 계산
    int nextCost = best[here] + graph[here][next];
    
    //이미 최소 비용의 경로가 있다면? -> 발견된 vertex 목록에 추가X
    if(best[next] < nextCost)
        continue;
        
    discover.push_back({next, best[next]});
    best[next] = nextCost;
}

 

3가지의 작업을 발견된 vertex 목록이 없을 때까지 계속 수행해주어야 한다.

 

 

 

전체 코드를 살펴보자.

 

인접행렬을 이용한 그래프 생성

#include <iostream>
#include <vector>
#include <list>

using namespace std;

vector<vector<int>> graph;

void CreateGraph()
{
    graph= = vector<vector<int>>(6, vector<int>(6,-1));
    
    graph[0][1] = 15;
    graph[0][3] = 35;
    graph[1][0] = 15;
    graph[1][2] = 5;
    graph[1][3] = 10;
    graph[3][4] = 5;
    graph[5][4] = 5;
    
}

 

다익스트라 함수 생성

void Dijikstra(int here)
{
    vector<int> best(6, INT32_MAX);
    best[here] = 0; //시작점
    
    struct PathCost
    {
        int vertex;
        int cost;
    }
    
    list<PathCost> discover;
    discover.push_back({here, best[here]});
    
    while(discover.empty()==false)
    {
        int bestCost = INT32_MAX;
        list<PathCost>::iterator bestIt;
        for(auto it = discover.begin(); it != discover.end(); it++)
        {
            if(it->cost < bestCost)
            {
                bestCost = it->cost;
                bestIt = it;
            }
        }
        
        int cost = bestIt->cost;
        here = best->vertex;
        discover.erase(bestIt);
        
        if(best[here] < cost)
            continue;
            
        for(int next = 0; next < 6; next++)
        {
            if(graph[here][next] == -1) // 연결되지 않은 경우
                continue;
            
            int nextCost = best[here] + graph[here][next];
            
            if(best[next] < nextCost)
                continue;
            
            discover.push_back({next, nextcost});
            best[next] = nextCost;
        }
    }
}