DFS & 다익스트라

Depth First Search(DFS), 깊이 우선 탐색

• 그래프의 탐색에 사용되는 알고리즘
• 모든 경우의 수를 탐색할 때 사용
• Vertex의 순서를 고려할 때 사용
• 백트래킹에 사용

 

다익스트라 알고리즘

• 최단 거리 알고리즘 
• 힙 사용(우선순위 큐)
• 가중치 있는 간선일 때 사용

 

priority_queue< pair<int, int> > pq;
pq.push(make_pair(0, 시작 정점)); // 시작 정점의 가중치는 0
dist[시작 정점] = 0;

while(!pq.empty())
{
	int cur_vertex = pq.top().second;
    int cur_dist = -pq.top().first; // 넣을 때 -를 붙여서 넣는다. 가장 작은 간선 가중치가 위로 올라오기 때문이다.
    
    for(int i=0;i<v[cur_vertex].size();i++)
	{
    	int next_dist = v[cur_vertex][i].dist; // 현재 정점 - 연결된 정점 간선의 가중치
        int next_vertex = v[cur_vertex][i].vertex; // 연결된 정점의 정보
        next_dist = next_dist + cur_dist; // 현재 위치 가중치 + 연결된 정점의 가중치 값 구하기
        if(next_dist < dist[next_vertex]) // 현재 위치 가중치 + 연결된 정점의 가중치 값이 저장된 가중치 값보다 작으면 최단거리이므로 업데이트 !
		{
        	dist[next_vertex] = next_dist;
            pq.push(make_pair(-dist[next_vertex], next_vertex)); // 더 짧은 거리가 있을 수 있으므로 탐색 대상에 추가 
		}
	}
}