다익스트라 알고리즘(Dijkstra's Algorithm)

개념공부

다익스트라 알고리즘(Dijkstra's Algorithm)

Cadi 2024. 12. 10. 22:07

다익스트라 알고리즘

특정 시작점에서 그래프의 다른 정점들까지의 최단 거리를 계산하는 로직.

https://www.youtube.com/watch?v=tZu4x5825LI

다익스트라 알고리즘의 단계는 다음과 같다

초기화 작업
가장 가까운 정점 찾기
이웃 정점의 거리 업데이트(반복)
반복 종료

구현을 통해 각 과정과 코드를 자세히 알아보자

구현

우선 변수들을 선언해준다.

변수로는 각 정점까지의 거리를 저장할 Dictionary형 변수 distances

이전 정점을 저장하는 Dictionary형 변수 Preivous

방문하지 않은 정점들을 관리하는 집합인 HashSet가 있다.

그리고 1번인 초기화 작업을 해 준다.

 Dictionary<Vertex, float> distances = new Dictionary<Vertex, float>();
        Dictionary<Vertex, Vertex> previous = new Dictionary<Vertex, Vertex>();
        HashSet<Vertex> unvisited = new HashSet<Vertex>();

물론 시작점이 존재하지 않으면, 그대로 종료하는 예외처리도 해 주어야 한다.(위 코드의 위에)

        if (!vertices.ContainsKey(startName)) return;

그리고 각각의 정점들을 초기화를 해 준다.

 foreach (var vertex in vertices.Values)
        {
            distances[vertex] = float.MaxValue;
            previous[vertex] = null;
            unvisited.Add(vertex);
        }

여기서 거리를 float.MaxValue;로 하는 이유는, 최단 거리를 구하기 위해 거리 값들을 비교하고, 제일 작은 거리 값을 구하는 과정을 할 때에 0으로 초기화 되어 있다면 변하지 않기 때문이다.

모든 정점들을 방문하지 않았다는 HashSet에 추가해준다.

그리고 시작점을 start라고 이름짓고, 매개변수를 받아 할당해준다.

시작점의 거리는 0이다.

Vertex start = vertices[startName];
        distances[start] = 0;

그리고 다음의 과정을 unvisited.Count>0, 즉 모든 정점들을 방문할때까지 반복한다.

1. 가장 가까운 미방문 정점을 찾는다. (그리고 current에 할당한다)

2. 방문할 정점이 더 이상 없다면 종료한다.

3. 가장 가까운 정점(current)를 unvisited에서 제거한다.

4. 현재 정점(current)의 모든 이웃을 검사한다.

-1 현재까지와 current와 이웃까지의 거리를 계산한다.

-2 기존 거리보다 더짧은 경로가 발견되면 거리와 경로를 업데이트한다.

while (unvisited.Count > 0)
    {
        // 현재 방문하지 않은 정점 중 가장 가까운 정점을 찾기
        Vertex current = null;
        float minDistance = float.MaxValue;

        foreach (var vertex in unvisited)
        {
            // "거리가 가장 짧은 정점"을 찾음
            if (distances[vertex] < minDistance)
            {
                current = vertex;        // 가장 가까운 정점 저장
                minDistance = distances[vertex]; // 최소 거리 갱신
            }
        }

        // 방문할 정점이 더 이상 없다면 종료
        if (current == null) break;

        // 가장 가까운 정점을 "방문하지 않은 정점" 집합에서 제거
        unvisited.Remove(current);

        // --- 현재 정점의 모든 이웃(neighbor) 검사 ---
        foreach (var neighbor in current.neighbors)
        {
            // 현재 정점(current)에서 이웃(neighbor)까지의 거리 계산
            float alt = distances[current] + neighbor.Value;

            // 기존 거리보다 더 짧은 경로가 발견되면 거리와 경로를 업데이트
            if (alt < distances[neighbor.Key])
            {
                distances[neighbor.Key] = alt;      // 더 짧은 거리로 갱신
                previous[neighbor.Key] = current;  // 이전 정점을 현재 정점으로 설정
            }
        }

여기서 내가 의문이었던 점은, foreach ( var vertex in unvisited) 라는 구문이다. 이웃이 아닌 vertex들과의 거리는 등록되어 있지 않은데 어떻게 처리하지.. ? 였는데 이는 계산할 수 없기 때문에 float.MaxValue로 초기화 된 상태를 유지한다고 한다.

이해가 가지 않았던 점은, 예를 들어 A에서 B가 가장 짧은 정점이라면, B를 통하는 정점들만 검사하는게 아닌가 ? 하는

지금 생각해보면 바보같은 생각이 있었다. 그러다 하나하나 시뮬레이션 해 보면서, 결국 unvisited HashSet에서 하나씩 지우기 때문에, 모든 정점을 들리고, 그 정점을 거치는 경로 하나하나를 다 검사한다는 뜻이다.

완성된 코드는 다음과 같다.

 public void Dijkstra(string startName)
    {
        if (!vertices.ContainsKey(startName)) return;

        Dictionary<Vertex, float> distances = new Dictionary<Vertex, float>();
        Dictionary<Vertex, Vertex> previous = new Dictionary<Vertex, Vertex>();
        HashSet<Vertex> unvisited = new HashSet<Vertex>();

        //초기화
        foreach (var vertex in vertices.Values)
        {
            distances[vertex] = float.MaxValue;
            previous[vertex] = null;
            unvisited.Add(vertex);
        }

        Vertex start = vertices[startName];
        distances[start] = 0;

        while (unvisited.Count > 0)
        {
            //가장 가까운 미방문 정점 찾기
            Vertex current = null;
            float minDistance = float.MaxValue;
            foreach (var vertex in unvisited)
            {
                if (distances[vertex] < minDistance)
                {
                    current = vertex;
                    minDistance = distances[vertex];
                }
            }

            if (current == null) break;

            unvisited.Remove(current);
            foreach (var neighbor in current.neighbors)
            {
                float alt = distances[current] + neighbor.Value;
                if (alt < distances[neighbor.Key])
                {
                    distances[neighbor.Key] = alt;
                    previous[neighbor.Key] = current;
                }
            }

            //결과 출력
            foreach (var vertex in vertices.Values)
            {
                Debug.Log($"{startName}에서 {vertex.name}까지의 최단 거리 : {distances[vertex]} ");
            }
        }
    }

간단한 예시를 통해 이해한 바를 확실히 해보자.

foreach문 두 개를 구분하기 위해 1번 foreach문, 2번 foreach문이라고 명명한다.

1. startName에 A가 들어온다.

2. 1번 foreah문에 가서, 최단거리 정점을 선택한다.

아직, A 그 자체가 unvisited에서 제외되지 않았으므로, 자연스럽게 거리가 0인 A 선택
foreach문이 끝나고, unvisited에서 A 제거

3. 선택된 A가 2번 foreah문에 가서 주변(neighbor)까지의 최단 거리를 업데이트하고, 경로를 표시하기 위해 preivous 에

이전 노드인 A를 저장한다.

A에서 B(1) , D(4)로 향하는 거리 업데이트, 동시에 previous에 A 저장.

3. 1번 foreach문으로 돌아감 ( unvisited > 0)

unvisited에 남아있는 {B,C,E,D} 중 최단 거리인 B 선택
foreach문이 끝나고, unvisited에서 B 제거

4. 선택된 B가 2번 foreach문으로 가서 주변까지의 최단 거리를 업데이트하고, preivous에 B 저장

B -> C : 1 + 2 (업데이트)
B -> D : 1 + 6(기존D까지의 거리 4보다 크므로 무시)

5. 1번 foreach문으로 돌아감

unvisited에 남아있는 {C,E,D) 중 최단 거리인 C 선택
unvisited에서 C 제거

6. 2번 foreach문으로 감

C의 이웃은 존재하지 않음

7. 1번 foreach문으로 돌아감

unvisited에 남아있는 {E,D) 중 최단 거리인 D 선택
unvisited에서 D 제거

8. 선택된 D가 2번 foreach문으로 가서 주변의 최단거리를 갱신하고 previous D 저장

D -> E : 4 + 1(업데이트)
1번 foreach문으로 돌아감

9. 1번 foreach문으로 돌아감

남아 있는 유일한 unvisited인 D를 선택함
2번에서도 아무것도 선택되지 않고, while unvisited = 0이 되므로 반복문 종료

의문 : 이런 식으로 while문이 종료되면 왜 굳이 if ( current == null ) break ; 라는 구문이 존재할까 ?

답변 : 특정한 상황(특정 정점에 도달할 수 없는 경우) 를 처리하기 위해서
다익스트라 알고리즘은 그래프에서 모든 정점이 서로 연결되어 있다고 가정하지 않음

=> 정점의 거리 값은 계속해서 무한대(flaot.MaxValue)로 남아 있음

=> current == null 인 경우에도 계속해서 반복문 실행

이와 같은 문제 때문에 if 문이 존재하는 것 !!

틀린 부분 있으면 언제나 말해주세오