C# Dijkstra 알고리즘

Dijkstra Algorithm

 

다익스트라 알고리즘은 최단 경로를 구하는 MST의 탐색 방법중 하나이며 특정한 하나의 정점에서 모든 정점들의 최단 경로를 구해주는 알고리즘이다.

 

다익스트라 알고리즘은 음의 간선이 들어간 그래프에서는 제대로 된 경로를 못찾아 사용할수는 없지만 현실 세계에서는 음의 간선은 없기 때문에 별로 상관없는 이야기긴 하다.

 

다익스트라 알고리즘의 구현은 대표적으로 2가지 방법이 있는데 하나는 선형탐색 또 하나는 우선순위 큐를 이용해서 구현할수 있다.

 

하지만 선형탐색은 최소 n²의 시간복잡도를 같기때문에 문제를 풀거나 구현을 해야하는 상황이 생기면 선형탐색으로 구현은 비추천이다.

 

그래서 우선순위 큐를 이용해서 구현을 해보겠다

 

내 버전에서의 C#은 우선순위 큐를 지원하지 않기때문에

 

https://blog.naver.com/ambidext/221285681447

[C#] Priority Queue (우선순위 큐)

 

여기 블로그에 있던 우선순위 큐의 소스를 이용해서 구현을 하였고

우선순위 큐가 구현되있는 코드까지는 올리지 않을것이다.

 

일단 우선순위 큐를 이용해서 어떻게 작동을 하는지 보겠다.

 

 

일단 노드들이 담겨져 있는 최단 경로들의 배열들을 무한대로(가지 못하는 경로로) 바꾼다.

 

 

 

 

현재 시작 정점에 최단경로 배열에 0을 넣고 우선순위 큐에 넣는다.

 

 

 

우선순위 큐를 꺼낸 0번 노드의 인접한 노드들에 현재 최단경로들이 시작 정점 최단 경로 값들보다 비용이 적은지 확인한후 넣고 체크를 한다.

 

0번째 인접 노드들의 최단경로들을 배열에 넣고 다시 우선순위 큐에다 넣는다.

 

 

우선 순위 큐에다 넣은 현재 노드와 그 노드까지의 최단 경로를 가져와 현재 최단경로에 저장되있는 노드보다 큰지 확인하고 크면 굳이 확인할 이유가 없으니 넘어가고 비용이 적거나 같으면 현재 그 정점의 인접 노드들을 다시 검사한다.

 

현재 인접해있는 1번 노드와 3번 노드는 현재 2번 노드의 최단 경로에서 가중치를 더하면 시작 정점 최단 경로보다

더 크거나 같기 때문에 갱신이 안되고

 

시작 정점 최단 경로에 있던 5번 노드의 최단 거리는 무한대였고 지금 2번 노드까지 가는 최단경로가 3이였던 정보가 현재 인접한 5번 노드를 가면서 현재 저장되있던 최단경로 3이랑 5번 노드로 가는 가중치 8을 더해서 5번까지 가는 최단 경로는 11이 되었고

 

시작 정점 최단경로의 저장 되있는 INF 최단경로보다 더 비용이 적기때문에 시작 정점 최단경로에 11을 넣고 다시 우선 순위큐에 최단경로 : 11, 현재 노드 : 5에 정보를 넣는다.

 

 

 

그리고 우선순위가 높았던 3번 노드까지의 최단경로가 4인 정보를 꺼내고 현재 노드의 시작 정점 최단경로와

최단 경로가 크지 않으니 다시 인접 노드의 최단 경로들을 검사하게 되고

 

인접해있는 5번까지의 최단 경로가 4 + 2를 해서 6이 되니깐 현재 시작 정점 최단경로보다 최단경로가 더 낮으니

다시 11에서 6으로 갱신되고 우선순위 큐에다 정보를 넣는다.

 

 

방금 넣었던 최단경로가 가장 짧은 최단경로 : 6 현재 노드 5가 꺼내지면서

 

현재 인접해있는 4번노드까지 가는 거리가 6 + 5 = 11이기 때문에 원래 시작 정점 최단경로 였던 12보다 더 낮아 다시 갱신이 되고 그 정보를 우선순위 큐에 넣고

 

이렇게 반복적으로 작동이 되고 우선순위 큐에 있는 정보들을 다 꺼내게 되면 정지하고 그 정점까지의 최단경로들을 출력하는 방식이라고 보면 된다.

 

그래서 마지막 결과는 0 3 4 11 6이고 내가 구현한 다익스트라 코드를 출력 하면

 

제대로 나오는것을 볼수 있다.

 

내가 짠 다익스트라 코드

 class Program
    {
        static int n = 5;
        static int INF = 100000000;
        static int[] d;
        static List<(int weight, int node)>[] maps;
        static void Main(string[] args)
        {       
            maps = new List<(int weight, int node)>[n + 1];

            for (int i = 1; i < n + 1; i++)
            {
                maps[i] = new List<(int weight, int node)>();
            }

            maps[1].Add((3, 2));
            maps[1].Add((4, 3));
            maps[1].Add((12, 4));

            maps[2].Add((3, 1));
            maps[2].Add((6, 3));
            maps[2].Add((8, 5));

            maps[3].Add((4, 1));
            maps[3].Add((6, 2));
            maps[3].Add((2, 5));

            maps[4].Add((12, 1));
            maps[4].Add((5, 5));
       
            maps[5].Add((8, 2));
            maps[5].Add((2, 3));
            maps[5].Add((5, 4));

            Dijkstra(1);
        }
        static void Dijkstra(int start)
        {
            d = new int[n + 1];

            for (int i =1; i < d.Length; i++)
            {
                d[i] = INF;
            }

            d[start] = 0;

            MinHeap<Tuple<int, int>> pq = new MinHeap<Tuple<int, int>>();

            pq.Add(new Tuple<int, int>(d[start], start));

            while (pq.Count != 0)
            {
                int distance = pq.GetMin().Item1;
                int current = pq.ExtractDominating().Item2;

                if (d[current] < distance) continue;

                for (int i = 0; i < maps[current].Count; i++)
                {
                    int node = maps[current][i].node;
                    int weight = distance + maps[current][i].weight;

                    if (d[node] > weight)
                    {
                        d[node] = weight;

                        pq.Add(new Tuple<int, int>(d[node], node));
                    }
                }
            }

            for (int i = 1; i < d.Length; i++)
            {
                Console.Write(d[i] + " ");
            }                    
        }
    }
}

 

이 문제들은 백준에 있는 문제들이고 내가 다익스트라를 이용해서 풀고 올린 링크들이다.

최단 경로들을 대표하는 문제들이니 풀어보는 것이 좋을 것 같다.

 

https://propim.tistory.com/55

C# 백준 1916 최소비용 구하기

https://propim.tistory.com/56

C# 백준 1753 최단경로

https://propim.tistory.com/57

C# 백준 1504 특정한 최단 경로