[TIL] 129 [C#] 다익스트라(Dijkstra) 알고리즘 최단경로

업데이트: 2024.12.11

카테고리: Til

태그: C#, TIL

다익스트라 Dijkstra

다익스트라 (Dijkstra)

다익스트라 알고리즘 : 한 정점 에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다.
최단거리를 계속 갱신.

예시

인접리스트, 우선순위 큐를 사용한 최소비용 최단거리 찾기.

class Program
{
    static void Main()
    {
        {
            var sw = new StreamWriter(Console.OpenStandardOutput());

            int cityT = Convert.ToInt32(Console.ReadLine());
            int busT = Convert.ToInt32(Console.ReadLine());

            var graph = new List<(int, int)>[cityT+1];  // 그래프 인접리스트

            for (int i = 1; i <= cityT; i++)
            {
                graph[i] = new List<(int, int)>();
            }

            for (int i = 0; i < busT; i++)
            {
                int[] info = Array.ConvertAll(Console.ReadLine().Split(" "), Convert.ToInt32);
                int busStart = info[0];
                int busEnd = info[1];
                int cost = info[2];

                graph[busStart].Add((busEnd,cost));
            }

            int[] dist = new int[cityT+1];
            Array.Fill(dist, int.MaxValue); 
            dist[start] = 0;                // 스타트 지점에서 자기자신 0, 다른점 max로 설정

            int[] go = Array.ConvertAll(Console.ReadLine().Split(" "), Convert.ToInt32);
            int start = go[0];
            int end = go[1];

            int result = Dijkstra(dist, graph, start, end);
            sw.WriteLine(result);
            sw.Flush(); sw.Close();

        }

    }

     
//다익스트라(Dijkstra)
//**한 정점** 에서 **모든 정점까지의 최단거리를 각각** 구하는 알고리즘입니다. 
static int Dijkstra(int[] dist , List<(int, int)>[] graph, int start, int end)
    {

        var pq = new PriorityQueue<(int, int), int>();          //우선순위 큐
        pq.Enqueue((start, 0), 0);

        while (pq.Count > 0)
        {
            var (current, currentCost) = pq.Dequeue();

            if (currentCost > dist[current]) continue;          // 현재 계산된 current 까지의 비용이 원래 current 까지의 비용보다 높으면 PASS

            foreach (var (next, cost) in graph[current])        // current와 연결된 노드 확인
            {
                int nextCost = currentCost + cost;
                if (nextCost < dist[next])                      // 현재 start~next까지의 비용이 원래값보다 작으면 
                {
                    dist[next] = nextCost;                      // 갱신
                    pq.Enqueue((next, nextCost), nextCost);     // pq에 추가, next와 연결된 다음경로 탐색
                }
            }
        }

        return dist[end];
    }
}

1. 초기화

var graph = new List<(int, int)>[cityT+1];  // 그래프 인접리스트

for (int i = 1; i <= cityT; i++)
{
    graph[i] = new List<(int, int)>();
}

// 현재 start -> x 까지 최단거리(dist) 초기화
int[] dist = new int[cityT+1];
Array.Fill(dist, int.MaxValue); 
dist[start] = 0;                // 스타트 지점에서 자기자신 0, 다른점 max로 설정

2. 경로(가중치) 입력

for (int i = 0; i < busT; i++)
{
    int[] info = Array.ConvertAll(Console.ReadLine().Split(" "), Convert.ToInt32);
    int busStart = info[0];
    int busEnd = info[1];
    int cost = info[2];
    graph[busStart].Add((busEnd,cost));
}

3. 다익스트라(Dijkstra)

//다익스트라(Dijkstra)
//**한 정점** 에서 **모든 정점까지의 최단거리를 각각** 구하는 알고리즘입니다.  
static int Dijkstra(int[] dist , List<(int, int)>[] graph, int start, int end)
    {

        var pq = new PriorityQueue<(int, int), int>();          //우선순위 큐
        pq.Enqueue((start, 0), 0);

        while (pq.Count > 0)
        {
            var (current, currentCost) = pq.Dequeue();

            if (currentCost > dist[current]) continue;          // 현재 계산된 current 까지의 비용이 원래 current 까지의 비용보다 높으면 PASS

            foreach (var (next, cost) in graph[current])        // current와 연결된 노드 확인
            {
                int nextCost = currentCost + cost;
                if (nextCost < dist[next])                      // 현재 start~next까지의 비용이 원래값보다 작으면 
                {
                    dist[next] = nextCost;                      // 갱신
                    pq.Enqueue((next, nextCost), nextCost);     // pq에 추가, next와 연결된 다음경로 탐색
                }
            }
        }

        return dist[end];
    }

잡담, 일기?

플로이드-워셧, 다익스트라 차이점?
다익스트라 알고리즘 : 한 정점 에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다.
플로이드-워셜 알고리즘 : 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다.

| 종 이 |