[C#] 다익스트라 최단 경로 알고리즘(추가 공부 필요)

다익스트라 최단 경로 알고리즘

-가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다.

using System;
using System.Collections.Generic;
using System.Text;

namespace Exercise
{
    class Graph
    {
        int[,] adj = new int[6, 6]
        {
            { -1, 10, 15, -1, -1, -1 },
            { 10, -1, 15, -1, -1, -1 },
            { 15, 15, -1, 5, 5, -1 },
            { -1, 5, -1, -1, -1, -1 },
            { -1, -1, 5, -1, -1, 5 },
            { -1, -1, -1, -1, 5, -1 },
        };

        public void Dijikstra(int start)
        {
            bool[] visited = new bool[6];
            int[] distance = new int[6];
            int[] parent = new int[6];
            Array.Fill(distance, Int32.MaxValue);

            distance[start] = 0;
            parent[start] = start;

            while (true)
            {
                //가장 가까이에 있는 곳을 찾는다.
                int closest = Int32.MaxValue;
                int now = -1;
                for(int i = 0; i < 6; i++)
                {
                    //이미 방문한 정점은 스킵
                    if (visited[i])
                        continue;
                    //아직 발견(예약)된 적이 없거나, 기존 후보보다 멀리 있으면 스킵
                    if (distance[i] == Int32.MaxValue || distance[i] >= closest)
                        continue;
                    //여태껏 발견한 가장 후보라는 의미니깐, 정보 갱신
                    closest = distance[i];
                    now = i;
                }
                // 다음 후보가 하나도 없다 -> 종료
                if (now == -1)
                    break;

                //제일 좋은 후보를 찾았으니깐 방문
                visited[now] = true;

                //방문한 정점과 인접한 정점들을 조사해서,
                //상황에 따라 발견한 최단거리를 갱신한다
                for (int next = 0; next < 9; next++)
                {
                    //연결되지 않은 정점 스킵
                    if (adj[now, next] == -1)
                        continue;
                    //이미 방문한 정점은 스킵
                    if (visited[next])
                        continue;

                    //새로 조사된 정점의 최단거리를 계산한다.
                    int nextDist = distance[now] + adj[now, next];
                    //만약에 기존에 발견한 최단거리가 새로 조사된 최단거리보다 크면,
                    //정보를 갱신
                    if(nextDist < distance[next])
                    {
                        distance[next] = nextDist;
                        parent[next] = now;
                    }
                }
            }
        }
    }
}

 

 

---------------------------------------------------------------------------------------------------------------------------

참고 : [인프런] Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘

참고 :  https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98