[필수 알고리즘] 다익스트라

작동원리

- 초기값 무대한으로 설정 및 힙 시작점 추가

- 힙에서 현재 노드를 빼며 간선을 통할때 거리가 짧아진다면 거리 갱신 및 힙 추가

 

핵심코드

// [비용, 노드번호] 형태로 저장하기 위한 우선순위 큐 선언
PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>();

// 시작점 초기화
dist[K] = 0;
heap.Enqueue(new int[] {0, K}, 0); // [비용, 노드번호]를 저장하고, 비용을 기준으로 정렬

while (heap.Count > 0)
{
    // 현재 가장 비용이 적은 노드 정보 추출
    int[] current = heap.Dequeue();
    int ew = current[0]; // 비용
    int ev = current[1]; // 노드 번호
    
    // 이미 처리된 노드라면 스킵 (더 짧은 경로를 이미 찾은 경우)
    if (dist[ev] != ew) continue;
    
    // 인접 노드 탐색
    foreach (var next in edge[ev])
    {
        int nw = next.Item1; // 간선 가중치
        int nv = next.Item2; // 인접 노드
        
        // 더 짧은 경로를 발견한 경우 갱신
        if (dist[nv] > ew + nw)
        {
            dist[nv] = ew + nw;
            heap.Enqueue(new int[] {dist[nv], nv}, dist[nv]); // [갱신된 비용, 노드] 추가
        }
    }
}

 

아이디어

- 한점에서 다른 모든 점으로 가는 최단경로 > 다익스트라 사용

- 모든 점 거리 초기값 무한대 설정

- 시작점 거리 0 및 힙 추가

- 힙에서 하나씩 빼며 수행 -> 현재 거리가 새로운 간선 이동 시 크다면 갱신 -> 새로운 거리 힙 추

 

시간복잡도

- ElgV : E = 3e5, lgV = 20

- O(ElgV) = 6e6

 

변수

- 힙(비용(int), 다음노드(int))[]

- 거리 배열 : int[]

- 간선, 인접리스트 :(비용(int), 다음노드(int))[]

 

TIP

- 코드는 그냥 외우기

- 한점에 다른 점으로 가는 최소 비용이라고 했을때 사용하기

 

문제풀이

- 백준 1753

 

1. 

class num_1753
{
    static void Main(string[] args)
    {
        var sr = new StreamReader(Console.OpenStandardInput());
        var sw = new StreamWriter(Console.OpenStandardOutput());

        string[] input = sr.ReadLine().Split();
        //정점 개수
        int V = int.Parse(input[0]);
        //간선 개수
        int E = int.Parse(input[1]);
        //시작점
        int K = Convert.ToInt32(sr.ReadLine());

        //노드별 비용과 간선수 리스트
        var edge = new List<List<Tuple<int, int>>>();
        for (int i = 0; i <= V; i++)
        {
            edge.Add(new List<Tuple<int, int>>());
        }
    }
}

- 정점, 간선, 시작점 input 받기

- 노드별로 비용, 간선 수를 저장할 List<List<Tuple<int,int>>>(); 초기화

단, 1부터 시작할 것이기 때문에 i <= V 로 처리

 

2.

  //최소값을 구하기 위한 값 배열, MaxValue로 초기화
int[] dist = new int[V + 1];
for (int i = 0; i <= V; i++)
{
    dist[i] = int.MaxValue;
}


for (int i = 0; i < E; i++)
{
    string[] input_ = sr.ReadLine().Split();
    //노드번호
    int u = int.Parse(input_[0]);
    //간선개수
    int v = int.Parse(input_[1]);
    //비용
    int w = int.Parse(input_[2]);

    edge[u].Add(new Tuple<int, int>(w, v));
}

- 노드별 비용을 저장하기 위한 int[] dist 추가 후 int 최대값 저장

- u,v,w 값을 Input받은 후 edge[u]로 노드별로 w,v(비용, 간선수) 저장

 

3.

PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>();

//시작점 초기화
dist[K] = 0;
//시작점이기 때문에 비용은 0 시작노드 K 로 초기화
heap.Enqueue(new int[] { 0, K }, 0);


while (heap.Count > 0)
{
    var qdata = heap.Dequeue();
    int w = qdata[0];
    int node = qdata[1];

    //현재 node의 비용값이 다르면 힙 새로 가져오기
    if (dist[node] != w)
    {
        continue;
    }

    //
    foreach (var next in edge[node])
    {
        //다음 노드의 비용
        int nw = next.Item1;
        //다음 노드의 연결된 노드번호
        int nv = next.Item2;

        //다음노드의 비용이 가져온 노드의 비용과 다음 노드의 비용 비교 
        if (dist[nv] <= w + nw)
        {
            continue;
        }
        dist[nv] = w + nw;
        //더 작다면 현재 노드의 비용과 노드 번호 힙에 추가
        heap.Enqueue(new int[] { dist[nv], nv }, dist[nv]);
    }
}

- 우선순위 큐를 생성하여 시작점인 k를 이용해 dist[k]를 0으로 초기화(k에서 k로 이동하는데 비용이 들지 않기 때문에 0값)

- heap을 꺼내서 if(dist[node] != w)로 현재 꺼낸 노드 정보가 최신값인지 체크하여 불필요한 연산이나 중복처리 방지

- edge[node]의 정보를 꺼내 dist[nv] <= w +nw로 값이 큰지 체크 후 작다면 정보 갱신 및 노드 정보 heap에 추가

 

4.

//출력
for (int i = 1; i <= V; i++)
{
    if (dist[i] == int.MaxValue)
    {
        sw.WriteLine("INF");
    }
    else
    {
        sw.WriteLine(dist[i]);
    }
}

sw.Flush();
sw.Close();
sr.Close();

- 최종 dist 정보 출력하여 int.MaxValue값이 있으면 INF로 출력

 

최종코드

/*
1. 아이디어
- 한점 시작, 모든거리: 다익스트라
- 간선, 인접리스트 저장
- 거리배열 무한대 초기화
- 시작점 : 거리배열 0, 힙에 넣어주기
- 힙에서 빼며 다음 것을 수행
    -> 최신값인지 먼저 확인
    -> 간선을 타고 간 비용이 더 작으면 갱신

2. 시간복잡도
- 다익스트라 : O(ElgV)
    -> E : 3e5
    -> V : 2e4, lgV ~= 20
    -> ElgV = 6e6

3. 변수
- 힙 : (비용, 노드번호)
- 거리 배열(비용) : int[]
- 간선 저장, 인접리스트 : (비용, 노드번호)[]

*/

class num_1753
{
    static void Main(string[] args)
    {
        var sr = new StreamReader(Console.OpenStandardInput());
        var sw = new StreamWriter(Console.OpenStandardOutput());

        string[] input = sr.ReadLine().Split();
        //정점 개수
        int V = int.Parse(input[0]);
        //간선 개수
        int E = int.Parse(input[1]);
        //시작점
        int K = Convert.ToInt32(sr.ReadLine());

        //노드별 비용과 간선수 리스트
        var edge = new List<List<Tuple<int, int>>>();
        for (int i = 0; i <= V; i++)
        {
            edge.Add(new List<Tuple<int, int>>());
        }

        //최소값을 구하기 위한 값 배열, MaxValue로 초기화
        int[] dist = new int[V + 1];
        for (int i = 0; i <= V; i++)
        {
            dist[i] = int.MaxValue;
        }


        for (int i = 0; i < E; i++)
        {
            string[] input_ = sr.ReadLine().Split();
            //노드번호
            int u = int.Parse(input_[0]);
            //간선개수
            int v = int.Parse(input_[1]);
            //비용
            int w = int.Parse(input_[2]);

            edge[u].Add(new Tuple<int, int>(w, v));
        }

        PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>();

        //시작점 초기화
        dist[K] = 0;
        //시작점이기 때문에 비용은 0 시작노드 K 로 초기화
        heap.Enqueue(new int[] { 0, K }, 0);


        while (heap.Count > 0)
        {
            var qdata = heap.Dequeue();
            int w = qdata[0];
            int node = qdata[1];

            //현재 node의 비용값이 다르면 힙 새로 가져오기
            if (dist[node] != w)
            {
                continue;
            }

            //
            foreach (var next in edge[node])
            {
                //다음 노드의 비용
                int nw = next.Item1;
                //다음 노드의 연결된 노드번호
                int nv = next.Item2;

                //다음노드의 비용이 가져온 노드의 비용과 다음 노드의 비용 비교 
                if (dist[nv] <= w + nw)
                {
                    continue;
                }
                dist[nv] = w + nw;
                //더 작다면 현재 노드의 비용과 노드 번호 힙에 추가
                heap.Enqueue(new int[] { dist[nv], nv }, dist[nv]);
            }
        }

        //출력
        for (int i = 1; i <= V; i++)
        {
            if (dist[i] == int.MaxValue)
            {
                sw.WriteLine("INF");
            }
            else
            {
                sw.WriteLine(dist[i]);
            }
        }

        sw.Flush();
        sw.Close();
        sr.Close();
    }
}

 

참고영상

- 바로가기