다익스트라 알고리즘

다익스트라 알고리즘(dijkstra's algorithm)

두 정점 사이간 최소 거리를 구하는 알고리즘의 일종.

간단히 이론적인 것을 설명하자면..

N개의 정점을 모두 돌아다니는데 N과 연결된 정점을 찾아 거리를 계산해주는 것이다.

Start(시작점), End(도착점)이 존재하는데 각 점과 Start의 거리의 초기 값은 inf(무한대)이고

정점을 찾아다니며 최소 거리를 갱신하는 것이다.

-실제로는 inf 값을 넣지않고 큰 값, 혹은 일정한 값을 넣는다.(음수도 가능?할지도)

예를 들어 

정점 5개가 존재하고 각 정점을 0~4로 이름을 매긴다.

각 정점 간 관계는 아래와 같다.

또한 각 정점 간 거리는 아래와 같다.

 Start가 0, End가 3이라 놓는다면

0은 1과 2밖에 연결이 안 되어 있으니, 탐색은 0->1, 0->2로 시작된다.

이때 0->1, 0->2는 0으로부터 각 정점간 최단 거리이므로 3, 2가 최단거리가 될 것이다.

또한 1은 2와 3이랑 연결이 되어있다.

이때 탐색 루트는 0->1->2 , 0->1->3이 되는 것인데

0->1->2 루트의 거리는 5이고 이전에 0->2는 2이므로 최단거리 갱신이 안된다.

0->1->3 루트는 첫 탐색이므로 7이 최단거리가 된다.

0->2->3, 0->2->4 탐색을 해보자.

0->2->3 루트는 이미 0->1->3으로 0->3간 최단 거리가 설정되있다. 

하지만 0->2->3 루트는 거리가 3이므로 기존에 7보다 작으므로 최단거리 갱신이 된다.

0->3까지 최단거리는 이로써 3이 된다.

원래는 C++, C는 우선순위 큐를 이용하여 작성해야만 변수가 사라진다.

지금은 C# 코드만 ..

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
 
namespace Rextester
{
    public class Program
    {
        //빈공간이라는 것을 의미하는 변수
       private static int BigSize = 50000;
 
        //n개의 정점간 관계를 나타내는 이차원 배열
        private static int[,] map=new int[,]{{BigSize,3,2,BigSize,BigSize},
                                {BigSize,BigSize,2,4,BigSize},
                                {BigSize,BigSize,BigSize,1,3},
                                {BigSize,BigSize,BigSize,BigSize,4},
                                {BigSize,BigSize,BigSize,BigSize,BigSize}};
        //각 정점과 start와의 최소 거리
        private static int[] dist=new int[]{BigSize,BigSize,BigSize,BigSize,BigSize};
 
        //트래커, 이전에 어떤 정점을 거쳐온건지 체크
        private static int[] prev=new int[]{-1,-1,-1,-1,-1};
        public static void Main(string[] args)
        {
            serch(0,4);
        }
        private static void serch(int start, int end){
            if(start>5 || end>5) // 일단은 정점이 5개므로 초과로 입력되는 것을 막는다.
                Console.WriteLine("error");
            dist[start]=0; // start initialization // 시작 정점은 최소거리가 0이므로 초기화를 시켜준다.
            for(int i=0; i<5; i++){
                for(int j=0; j<5; j++){
                    if(map[i,j]!=BigSize){  // 정점 간 간선이 존재한다면
                        if(dist[j]==BigSize){ // 그리고 첫번째 방문이라면
                            dist[j]=dist[i]+map[i,j]; // 바로 최소거리가 된다.
                            prev[j]=i; //그리고 이전 정점을 넣어준다.
                        }
                        else if(dist[j] > dist[i]+map[i,j]){ // 첫 방문이 아니고 이전에 설정된 최소거리가 지금 최소거리보다 크다면
                            dist[j]=dist[i]+map[i,j];
                            prev[j]=i;
                        }
                    }
                }
            }
            Console.WriteLine("length:"+dist[end]);
            trck(start,end);
        }
        private static int trck(int start,int tmp){ // 최소거리가 되는 정점을 찾는다.
            if(tmp==start){ 
                Console.Write(start);
            }else{
                Console.Write(tmp+"->");
                return trck(start,prev[tmp]);
            }
            return 0;
                
        }
    }
}