최단거리(ShortestPath)

최단거리(ShortestPath)

데이크스트라 알고리즘 (Dijkstra Algorithm)

특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하기 위해 사용한다.
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 후,
해당 노드를 거쳐 다른 노드로 가는 비용을 계산한다.

<데이크스트라 알고리즘 (Dijkstra Algorithm) 구현>

internal class Dijkstra
{
	 const int INF = 99999;
    //단절 INF 최댓값 상수설정, int.Maxvalue 사용 시 오버플로우 위험있음

    public static void ShortestPath(in int[,] graph, in int start,out bool[] visited, out int[] distance, out int[] parents)
    //최단거리 함수 생성
    {
        int size = graph.GetLength(0);//첫 배열길이를 가지는 size 변수
        visited = new bool[size];//첫 배열길이 대입
        distance = new int[size];//첫 배열길이 대입
        parents = new int[size];//첫 배열길이 대입

        for (int i = 0; i < size; i++)// 갯수만큼 반복
        {
            visited[i] = false; //초기값 대입
            distance[i] = INF; //초기값 대입
            parents[i] = -1;  //초기값 대입
        }
        distance[start] = 0; //시작지점 0;

        for (int i = 0; i < size; i++) // 갯수만큼 반복
        {
            // 1. 방문하지 않은 정점 중 가장 가까운 정점부터 탐색
            int next = -1;//다음 정점 next 초기값 대입
            int minDistance = INF;//다음 정점까지 거리 minDistance 초기값 대입

            for (int j = 0; j < size; j++)//갯수만큼 반복
            {
                if (!visited[j]&& 
                    distance[j] < minDistance) 
                    //방문하지 않았으면서(false) And 거리가 더 가까운 경우
                {
                    next = j;//j가 다음 정점
                    minDistance = distance[j];//distance[j]가 최소거리
                }
            }

            if (next < 0)// 반복이 끝났을 때, 해당되는 값이 없을 때
                break; //멈춘다.

            // 2. 직접연결된 거리보다 다른 정점을 거쳐서 더 짧아진다면 갱신.
            for (int j = 0; j < size; j++)
            {
                // distance[j] : 목적지까지 직접 연결된 거리
                // distance[next] : 탐색중인 정점까지 거리
                // graph[next, j] : 탐색중인 정점부터 목적지의 거리
                if (distance[j]> distance[next]+ graph[next, j])
                    //직접거리가 탐색중인 정점을 거쳐서 목적지까지의 거리보다 먼 경우
                {
                    distance[j] = distance[next] + graph[next, j];
                    //탐색정점을 거쳐서 간 거리를 직접거리로 대입

                    parents[j] = next;
                    //직전 정점 값 next;
                }
            }
            visited[next] = true;//방문한 정점 true 표기
        }
    }
}

<함수 출력>

internal class Program
{
    const int INF = 99999;

    static void Main(string[] args)
    {
        int[,] graph = new int[8, 8] //사용할 그래프 생성
        {
        //예시, 임의로 작성
            { INF, INF, INF, 5, 4, INF, INF, INF },
            { INF, INF, 6, INF, INF, INF, INF, INF },
            { 6, INF, INF, INF, INF, 8, INF, INF},
            { INF, INF, INF,INF, INF, 6, INF, INF },
            { INF, INF, 6, INF, INF, INF, INF, INF},
            { INF, INF, INF, INF, INF, INF, 4, 6},
            { INF, INF, 9, INF, INF, 1, INF, INF},
            { INF, INF, INF, INF, INF, INF, INF, INF },
            
        };

        Dijkstra.ShortestPath(in graph, 0,out bool[] visited, out int[] distance, out int[] parents);//함수에 값 대입

        Console.WriteLine("<Dijkstra>");

        PrintDijkstra(visited, distance, parents); 
    }

    private static void PrintDijkstra(bool[] visited, int[] distance, int[] parents)//값 출력 함수 생성
    {
        Console.WriteLine($"{"Vertex",8}{"Visited",10}{"Distance",10}{"Parents",10}");

        for (int i = 0; i < distance.Length; i++)
        {
            Console.Write($"{i,8}");

            Console.Write($"{visited[i],10}");

            if (distance[i] == INF)
            {
                Console.Write($"{"INF",10}");
            }
            else
            {
                Console.Write($"{distance[i],10}");
            }

            Console.WriteLine($"{parents[i],10}");
        }
    }
}