다익스트라(Dijkstra) 알고리즘 간단 정리

1. 필요한 변수, 배열

 

1) 노드간 관계도 map

2) 각 노드로의 최단거리를 저장할 배열

 : result[]

3) 알고리즘용 queue( priority_queue 가 아니여도 되네....?)

 -> 아마 동작 시간을 고려해서 pq를 쓰는거 같긴한데... 애매하네

 

4) 최종 결과

 : result[목적지 노드]

 

 

2. 기본 동작 코드

: 무조건 queue로만, 배열을 사용하면서 할 필요성이 0

 1) 각 노드의 최단거리를 MAX로 초기화 시켜놓기

 2) 시작지를 queue에 넣음으로써 루프 시작, BFS랑 유사

 3) for문으로 나랑 연결되어 있는 노드들의 최단거리를 모두 업데이트

 -> 기존의 그 노드로 가는 최단길이 vs 지금 내 위치를 거쳐서 그 노드로 가는 길이를 비교하여, 최솟값으로 초기화

 

4) 위에 조건을 충족한 경우에만 queue에 삽입

 

void dijkstra(int start, int* result)
{
	queue<int> q;
	for (int i = 1; i <= n; i++)
		result[i] = INF;

	//출발지니까 0으로 초기화
	result[start] = 0;
	q.push(start);

	while (!q.empty())
	{
		int node = q.front();
		int dist = result[node];
		q.pop();

		for (int i = 0; i < road[node].size(); i++)
		{
			int next_node = road[node][i].first;
			int next_dist = road[node][i].second;

			//지금 노드를 거쳐서 오는거랑, 기존의최단거리랑 비교
			if (result[next_node] > dist + next_dist)
			{
				result[next_node] = dist + next_dist;
				q.push(next_node);
			}
		}
	}
}

 

 

+) priority queue 사용

중요포인트들만 잡고 갑세

 1) (거리, 노드) 이렇게 넣어야됨!

 2) 거리는 pq에 저장할때 음수로 넣어야됨!

  : 당연히 꺼낼때도 -를 붙여야된다.

 3) 그 뒤는 동일.

 기존 값 vs 현재 내 노드를 거쳐가서 가는 값

priority_queue<pair<int,int>>pq; // 거리, 노드 인덱스
    
    pq.push({0,start}); //시작 노드로 가기위한 최단 경로는 0으로 설정하여, 큐에 삽입.
    d[start]=0;
    
    while(!pq.empty())
    {
        int dist = -pq.top().first; //현재 노드까지의 비용
        int now = pq.top().second; // 현재 노드
        pq.pop();
        
        if(d[now]<dist) // 이미 최단경로를 체크한 노드인 경우 패스
            continue;
        
        for(int i=0; i<graph[now].size(); i++)
        {
            int cost = dist+graph[now][i].second; // 거쳐서 가는 노드의 비용을 계산
                                                  // 현재노드까지 비용 + 다음 노드 비용
            if(cost<d[graph[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[graph[now][i].first]=cost;
                pq.push(make_pair(-cost,graph[now][i].first));
            }
        }
    }