sdesign416 님의 블로그

[알고리즘] 다익스트라(Dijkstra)알고리즘 - 최단 경로와 동작 원리다익스트라 (Dijkstra) 알고리즘은 시작 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 예를 들어 지도 어플에서 현재 위치에서 목적지까지 가장 빠른 길을 찾거나네트워크에sdesign416.tistory.com다익스트라는 현재까지 발견한 거리 중 가장 짧은 정점을 선택하면서 최단 거리를 갱신하는 방식이다.하지만 정점이 많아질 경우 매번 가장 가까운 정점을 찾는 과정에서 많은 시간이 필요하다.이를 해결하기 위해 실제 구현에서는우선순위 큐(Priority Queue)와 힙(Heap) 자료구조를 사용한다.1. 우선순위 큐(Priority Queue)우선순위 큐는 일반적인 큐와 다르게먼저 들어온 데이터가 아니라 우선순위..

다익스트라 (Dijkstra) 알고리즘은 시작 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 예를 들어 지도 어플에서 현재 위치에서 목적지까지 가장 빠른 길을 찾거나네트워크에서 데이터가 이동하는 최적 경로를 찾을 때 사용된다. 다익스트라 알고리즘은 그래프의 가중치를 기준으로 최단 거리를 계산하기 때문에 가중 그래프에서 많이 사용된다. ※ 단, 다익스트라 알고리즘은 음수 가중치가 있는 그래프에서는 사용할 수 없다. 1. 최단 경로 알고리즘(Shortest Path Algorithm) 최단 경로 알고리즘은 그래프에서 특정 정점에서 다른 정점까지 이동할 때 가장 적은 비용이 드는 경로를 찾는 알고리즘이다.그래프의 가중치를 기준으로 최단 경로를 판단하기 때문에거리, 시간, 비용 등 어떤 값을 ..