Dijkstra 알고리즘을 이용한 최단 경로 찾기와 C# 구현

안녕하세요! 오늘의 기술 면접 지식은 그래프 이론의 한 부분인 Dijkstra 알고리즘에 관한 것입니다. 이 포스팅에서는 Dijkstra 알고리즘의 기본 개념과 C#으로 구현한 예제 코드를 살펴봅니다.

 

1. Dijkstra 알고리즘 개요 Dijkstra 알고리즘은 그래프에서 주어진 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 가중치가 있는 방향 그래프에서 사용할 수 있으며, 가중치가 음수인 간선이 없는 경우에만 정확한 결과를 보장합니다.
2. C#을 사용한 Dijkstra 알고리즘 구현 아래 예제 코드는 Dijkstra 알고리즘을 C#으로 구현한 것입니다.

 

public static Dictionary<int, int> Dijkstra(Dictionary<int, List<Tuple<int, int>>> graph, int start)
{
    Dictionary<int, int> distances = new Dictionary<int, int>();
    SortedSet<Tuple<int, int>> pq = new SortedSet<Tuple<int, int>>();

    foreach (var vertex in graph.Keys)
    {
        distances[vertex] = int.MaxValue;
    }

    distances[start] = 0;
    pq.Add(new Tuple<int, int>(0, start));

    while (pq.Count > 0)
    {
        var current = pq.First();
        pq.Remove(current);

        int currentDistance = current.Item1;
        int currentNode = current.Item2;

        if (currentDistance > distances[currentNode])
        {
            continue;
        }

        foreach (var neighbor in graph[currentNode])
        {
            int newDistance = currentDistance + neighbor.Item2;

            if (newDistance < distances[neighbor.Item1])
            {
                distances[neighbor.Item1] = newDistance;
                pq.Add(new Tuple<int, int>(newDistance, neighbor.Item1));
            }
        }
    }

    return distances;
}

 

이 코드는 그래프를 인접 리스트(Adjacent List)로 표현하고, 시작 정점에서부터 다른 정점까지의 최단 경로를 계산합니다.

 

Dijkstra 알고리즘은 최단 경로를 찾는 데 사용되는 중요한 알고리즘입니다. 기술 면접에서 그래프 이론과 Dijkstra 알고리즘에 대한 질문이 나올 경우, 이러한 원리와 구현 예시를 활용하여 답변할 수 있습니다. 다음 포스팅에서 또 다른 주제로 찾아뵙겠습니다!