
[ALGORITHM] 다익스트라 알고리즘
·
ALGORITHM & DATA STRUCTURE
최단 경로 문제 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 단일 출발 최단 경로 문제 : 그래프 내의 특정 노드 u에서 출발하여, 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제 단일 도착 최단 경로 문제 : 모든 노드들로 부터 출발해서, 그래프 내의 특정 노드 u로 도착하는 가장 짧은 경로를 찾는 문제 단일 쌍 최단 경로 문제 : 주어진 노드 u와 v간의 최단경로를 찾는 문제 전체 쌍 최단 경로 : 그래프 내의 모든 노드 쌍 사이에 대한 최단 경로를 찾는 문제 다익스트라 알고리즘 (최단경로 알고리즘) 다익스트라 알고리즘은 단일 출발 최단 경로..