• 다익스트라 알고리즘 소개
• 우선순위 큐 (Priority Queue)
• 힙 (Heap)
• 연결 리스트 (Linked List)

다익스트라 알고리즘 소개

다익스트라 알고리즘은 가중치가 있는 그래프에서 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.

우선순위 큐 (Priority Queue)

우선순위 큐는 가장 작은(또는 가장 큰) 요소에 빠르게 접근할 수 있는 자료 구조입니다. 최소 힙(최대 힙)으로 구현되는 우선순위 큐는 다익스트라 알고리즘에 적합한 자료 구조입니다.

import java.util.*

val priorityQueue = PriorityQueue<Int>()

힙 (Heap)

힙은 완전 이진 트리로, 부모 노드의 값이 자식 노드의 값보다 작은(또는 큰) 완전 이진 트리입니다. 이진 힙은 우선순위 큐를 구현하는 데 사용될 수 있습니다.

import java.util.*

val minHeap = PriorityQueue<Int>()

연결 리스트 (Linked List)

연결 리스트는 데이터 요소가 순서대로 연결되어 있는 자료 구조입니다. 다익스트라 알고리즘에서는 연결 리스트를 사용하여 그래프의 간선 및 가중치를 효율적으로 저장할 수 있습니다.

class ListNode(val value: Int, var next: ListNode? = null)

다익스트라 알고리즘에 적합한 자료 구조는 우선순위 큐(Priority Queue), 힙(Heap), 그리고 연결 리스트(Linked List)입니다.

참고 자료:

• GeeksforGeeks - Dijkstra’s Algorithm
• Wikipedia - Dijkstra’s algorithm