본문 바로가기

728x90

이론1

[Algorithm] 다익스트라(Dijkstra) 알고리즘이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 그래프 문제에서 아주 빈번하게 사용되는 다익스트라라는 알고리즘에 대해서 알아보겠습니다. 바로 시작할게요! 다익스트라란? 🤔 나무 위키에는 다음과 같이 정의되어있습니다. "음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다." 쉽게 말하면 한 정점에서 다른 정점으로 이동할 때 가장 빠른 길을 찾아주는 알고리즘이에요. 그래프 설명 다음과 같은 그래프가 있다고 가정하겠습니다. 시작 정점은 1로 목표 정점을 4로 두었을 때 가장 가까운 거리는 몇일까요? 1 - 5 - 4 로 가는 경우가 3 + 1 = 4로 가장 가까운 길이겠죠? 이렇게 간단히 보이는 경로는 눈으로 쉽게 찾을 수 있지만 복잡한 경로일수록 찾기가 어려워질 것입니다. 이.. 2021. 5. 22.

이전 1 다음

728x90

티스토리툴바