다익스트라

[알고리즘] Dijkstra Algorithm (다익스트라 알고리즘)

다익스트라 알고리즘이란? 💡다익스트라 알고리즘: 데이크스트라 또는 다익스트라 알고리즘이라 불리는 이 알고리즘은 음의 가중치가 없는 그래프에서 최단 경로 및 최단 거리를 찾는 알고리즘이다. 매번 최단 경로의 정점을 선택하기 때문에 그리디 알고리즘 기법을 활용한 예라고 볼 수 있다. 중요한 점은 음의 가중치가 없을 때만 사용이 가능하다는 점이다. 인접행렬을 사용하는 경우 O(n^2)의 시간복잡도를 가지지만, 우선순위 큐(=힙 트리)등을 이용한다면 O((v+e)logV)(V는 정점의 개수, E는 한 정점의 주변노드)의 시간복잡도를 가진다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 가능한 적은 비용으로 가장 빠르게 해답에 도달하는..