Dijkstra

다익스트라 알고리즘(Dijkstra Algorithm)다익스트라 알고리즘은 그래프의 한 정점에서 다른 정점으로의 최단 경로를 찾기 위해 사용되는 최단 경로 알고리즘입니다. 최단 경로를 찾는 알고리즘 하면 BFS를 떠올릴 수도 있지만, 다익스트라는 BFS(넓이 우선 탐색) 알고리즘과는 다르게 가중치가 존재하는 그래프에서 최단 경로를 찾을 때 사용됩니다. 이 때 그래프의 가중치는 음수가 될 수 없습니다.  특정 노드에서 각 노드까지의 최단 경로를 찾기 위해 사용하는 알고리즘인 만큼 실생활의 활용 예시로는 1. 지도의 특정 지점에서 다른 지점까지의 최단 경로 찾기2. 컴퓨터 네트워크에서의 데이터 패킷의 최적 경로를 찾기 위한 네트워크 라우팅 등 에서 사용됩니다. 다익스트라 알고리즘 구현다익스트라 알고리즘의 핵..

문제https://www.acmicpc.net/problem/10282 풀이처음에 DFS / BFS인 줄 알았는데 노드 간에 weight가 존재하는 문제인걸 확인하고 Dijkstra 알고리즘으로 접근하였다.DFS / BFS와는 다르게 각 노드 간에 거리가 존재하기 때문에 노드마다 방문을 진행하면서 시작 노드 c부터 해당 노드까지의 최단거리를 매번 갱신해주어야 한다! 아래와 같이 1~3번 노드가 존재하고 각 노드 간 weight가 존재한다고 가정해 보자. 1번 노드에서 시작해서 3번노드까지의 최단거리를 구해보자.먼저 1번 노드에서 시작한다. 현재 노드를 1번 노드로 설정해 주고 visited 처리를 해준 후, 1번 노드에서 1번 노드까지의 거리는 0이기 때문에 거리를 0으로 설정해 준다. 그 다음은 현재 ..