네트워크 에서 최단 코스트 경로 를 탐색 하 는 가장 일반 적 인 알고리즘 중 하나 는 다익스트라 알고리즘 [ Dijkstra 59 ] 이 다 . 이 알고리즘 은 경로 의 길이 가 포지티브 홉 간 ( hop - by - hop ) 링크 코스트 의 합 으로 정의 될 때 그래프 의 한 점 ( 소스 또는 루트 노드 ) 에서 모든 가능 한 목적지 까지 최단 경로 들 을 탐색 하 는 문제 를 해결 하 였 다 . 이러 한 문제 는 종종 단일 소스 최단 경로 문제 라 한다 . G =( N , L ) ( N 은 노드 들 의 세트 이 고 L 은 이 노드 들 을 연결 하 는 링크 들 의 세트 를 나타냄 ) 인 그래프 의 경우 , 다익스트라 알고리즘 은 통상 TENT 라 하 는 우선순위 큐 ( priority queue ) 를 이용 하 여 소스 노드 에서 거리 가 증가 하 는 순서 로 노드 들 을 방문 한다 . 다익스트라 알고리즘 을 구현 하 는 데 필요 한 다른 데이터 구조 는 아래 와 같 다 .