[알고리즘] 다익스트라

BFS로도 길찾기 알고리즘을 구현할 수 있지만 노드 간의 이동에 비용이 없을 경우에만 사용할 수 있다는 문제점이 있다.

BFS의 이동 기준은 찾은 순서이기 때문에 비용을 고려하지 않기 때문이다. 

이동에 비용을 고려하여 최단 경로를 찾아야 할 때는 다익스트라 알고리즘을 사용할 수 있다.

 

다익스트라 알고리즘의 노드 이동 기준은 노드를 찾은 순서가 아니라 노드의 이동 비용이라는 점에서 BFS와 차이가 있다.

또한 항상 최소 비용으로 이동하기 위해서 이미 탐색 후 이동 비용이 정해진 노드에 대해서도 다시 탐색을 진행하여 언제든지 이동 비용을 갱신 할 수 있도록 한다.

 

로직

1. 방문하지 않은 노드 중 이동 비용이 가장 작은 노드 선정 
2. 선정한 노드 방문 
3. 방문한 노드와 연결되어 있는 노드들에 대해 이동 비용 계산

 

구현

int[,] adj = new int[6, 6]
{
    {-1, 15, -1, 35, -1, -1 },
    {15, -1, 05, 10, -1, -1 },
    {-1, 05, -1, -1, -1, -1 },
    {35, 10, -1, -1, 05, -1 },
    {-1, -1, -1, 05, -1, 05 },
    {-1, -1, -1, -1, 05, -1 },
};

public void Dijikstra(int start)
{
    bool[] visited = new bool[6];
    int[] distance = new int[6];
    Array.Fill(distance, Int32.MaxValue);

    distance[start] = 0;

    while(true)
    {
        // 이동 비용이 가장 작은 노드 선정
        int minDistance = Int32.MaxValue;
        int now = -1;
        for(int i = 0; i < 6; i++)
        {
            // 방문 여부 확인
            if (visited[i] == true)
                continue;
            // 발견되지 않았거나 최소 비용이 아니라면 스킵
            if (distance[i] == Int32.MaxValue || distance[i] > minDistance)
                continue;

            minDistance = distance[i];
            now = i;
        }

        // 이동 가능한 노드가 없음
        if (now == -1)
            break;

        //방문
        visited[now] = true;

        // 연결된 노드들의 이동 비용 갱신
        
        for(int i = 0; i < 6; i++)
        {
            // 방문 여부
            if (visited[i] == true)
                continue;
            // 연결 여부
            if (adj[now, i] == -1)
                continue;

            int nextDistance = distance[now] + adj[now, i];
            if (nextDistance < distance[i])
                distance[i] = nextDistance;
        }
    }
}