[자료구조] 그래프 순회와 다익스트라 최단 경로 알고리즘 C#

다익스트라(Dijikstra)

 

다익스트라 알고리즘은 정점에서 모든 정점의 최단경로를 구하는 알고리즘이다.

BFS는 가중치가 존재한다면 사용하기에 부적절하지만 다익스트라는 가중치가 있는 그래프에 적절하다.

 

다익스트라 알고리즘은 예약한 가장 가까운 정점으로 이동을 하며 이동한 정점에서도 다시 인접한 정점을 조사하여 상황에 따라 발견한 정점의 최단거리를 갱신한다.

 

다익스트라(Dijikstra) 

가중치가 있는 그래프

2차 배열 사용

    class Graph
    {
        int[,] adj = new int[6, 6]
           {
             { -1, 15, -1, 35, -1, -1},
             { 15, -1, 05, 10, -1, -1},
             { -1, 05, -1, -1, -1, -1},
             { 35, 10, -1, -1, 05, -1},
             { -1, -1, -1, 05, -1, 05},
             { -1, -1, -1, -1, 05, -1},
           };
        public void Dijikstra(int start)
        {
            bool[] visited = new bool[6];
            int[] distance = new int[6];//그당시의 최단거리
            int[] parent = new int[6];//방문한 경로
            Array.Fill(distance, int.MaxValue);

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

            while (true)
            {
                //가장 가까이에 있는 제일 좋은 후보를 찾는다.

                //가장 유력한 후보의 거리와 번호를 저장한다.
                int closest = int.MaxValue;
                int now = -1;

                for (int i = 0; i < 6; i++)
                {
                    //이미 방문한 정접은 스킵
                    if (visited[i])
                        continue;
                    //아직 방문(예약)된 적이 없거나, 기존 후보보다 멀리 있으면 스킵
                    if (distance[i] == int.MaxValue || distance[i] >= closest)
                        continue;

                    //지금까지 발견한 가장 가까운 후보
                    closest = distance[i];
                    now = i;
                }

                //다음 후보가 존재하지 않는다.
                if (now == -1) break;

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

                //방문한 정점과 인접한 정점을 조사해서 상황에 따라 발견한 최단거리를 갱신한다.
                for (int next = 0; next < 6; 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;
                    }
                }
            }
        }
    }