Dijkstra 썸네일형 리스트형 8. 최단 경로 탐색: 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 최단 경로 탐색 알고리즘중 가장 대표적인 알고리즘이라고 할 수 있습니다. 일반적으로 최단 경로 탐색 알고리즘 교육에서는 가장 첫 장으로 소개되기 마련이며, 최단 경로 탐색 알고리즘인 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 중에서 가장 시간복잡도가 낮습니다. 하지만 모든 최단 경로 탐색 문제에 다익스트라 알고리즘을 사용할 수 있는 것은 아닙니다. 다익스트라 알고리즘의 위키백과 정의를 살펴보겠습니다. 컴퓨터 과학에서, 데이크스트라 알고리즘(=다익스트라 알고리즘)(영어: Dijkstra algorithm)은 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 이름은 네덜란드의 컴퓨터과학자 에츠허.. 1854번: K번째 최단경로 찾기 - Baekjoon Online Judge K번째 최단경로 찾기는 최단경로 알고리즘 중에서 가장 기본적이고, 가장 널리 알려진 다익스트라(Dijkstra) 알고리즘의 응용 문제이다. 다익스트라 알고리즘에 대해 간단히 알아보자면 다익스트라 알고리즘은 노드와 간선으로 이루어진 그래프가 있을 때, 하나의 노드를 출발점으로 하여 목표 노드까지 도달하는데 드는 비용을 최소화시키는 알고리즘이다. 알고리즘이 갖는 의미가 비교적 단순명료하여 이해하기는 쉬운데 처음 소스로 구현하자면 어떻게 해야할지 방향 잡기가 힘들다. 간단히 다익스트라 알고리즘 푸는 법을 설명하자면, 처음 시작점에서부터 갈 수 있는 노드들을 탐색하여, 해당 노드까지 가는데 드는 비용이 최소가 되도록 업데이트 해준다. 그리고 비용을 줄여서 이동 가능한 노드들이 우리가 도착 목표로 하고 있는 노드.. 이전 1 다음