다익스트라

다익스트라(Dijkstra)

다익스트라 알고리즘은 그래프의 기본적인 알고리즘이라 할 수 있는데
특정 정점에서 다른 모든 정점으로 가는 최단 경로를 찾아낼 수 있는 알고리즘이다.
정점들이 간선에 가중치를 가지고 있을 때 그 가중치들의 최소비용을 계산하여 다른 노드로 이동할 때 가장 최적의 동선을 찾아주는데 사용한다.

예시)

0이 시작노드에 3으로 이동한다고 하면,
0->3 으로 이동할시 최소비용 :35
0->1->3으로 이동할시에 최소비용 : 25
그래서 3으로 이동할때 0->1->3이 효율적인 동선임을 찾아내준다고 생각하면 된다.

int[][] adj3 =new int[6,6]
{
	{-1, 15, -1, 35, -1, -1},
	{15, -1, 5, 10, -1, -1},
	{-1, 5, -1, -1, -1, -1},
	{35, 10, -1, -1, 5, -1},
	{-1, -1, -1, 5, -1, 5},
	{-1, -1, -1, -1, 5, -1},
};

public void Dijkstra(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;
            //아직 발견(예약)된적이 없거나, 기존 후보보다 멀리 있으면 스킵
            // 1. 초기값을 distance배열의 초기값을 MaxValue로 설정해두고 distance[i]가 MaxValue라는 것은 아직 후보(예약)이 되지않아서 스킵
            //2. distance[i] >= closest는 가장가까이 있는 후보와 멀리있으면 스킵
            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 < 6; next++)
       {
        	//연결되어 있지않은 정점은 스킵
            if(adj3[now,next] == -1)
            	continue;
            //이미 방문한 정점은 스킵
            if(visited[next])
            	continue;
            //위에 if문에서 안걸러지면 새로 조사된 정점이라는거니까 최단거리를 꼐산
            int nextDist = distance[now] + adj3[now,next];
            //만약 기존에 발견한 최단거리가 새로 조사된 최단거리보다 크면 정보를 갱신
            if(nextDist < distance[next])
            {
            	distance[next] = nextDist;
                parent[next] = now;
            }
       }
    }
}