본문 바로가기

우선순위 큐

(1)

[Java] Dijkstra Path 다익스트라 알고리즘 구현(ft. 우선순위 큐) 쉽지만 복잡한 다익스트라 알고리즘 🤔 다익스트라 알고리즘은 왜 쓸까? ❗️최단 경로를 구하는 알고리즘 중 하나이다. 특정 지점에서 목표 지점으로 가장 적은 비용을 들이며 가야할 때 사용할 수 있다. 예) A에서 D로 가는데 걸리는 비용은 최소 값은? A -> D = 5 A -> B -> D = 5 A -> C -> D = 3 따라서 실제 최소 비용 지불하는 경로는 A -> C -> D 이다. 🥸 다익스트라 알고리즘 로직 1. 시작지점과 연결된 노드들과의 비용을 구한다. Result List 연결된 노드 A B C D E 비용 0 3 1 5 무한 출발 지점이 A일 때, 자기 자신에게 가는 비용은 없으니 0 A에서 E와 같이 바로 연결된 경로는 없을 때, 비용을 무한(영향을 주지 않는 아주 큰 값)으로 한다..

이전 1 다음

728x90

티스토리툴바