목록Dijkstra (1)

포시코딩

그래프 - 최단 경로 알고리즘, 다익스트라 알고리즘

최단 경로 문제란? 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 문제 종류 단일 출발 및 단일 도착 그래프 내의 특정 노드 u에서 출발, 또 다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 출발점이 A라고 한다면 A가 아닌 각각 다른 노드들 간의 최단 경로를 찾는걸 의미 다익스트라 알고리즘이 여기에 해당됨 전체 쌍(all-pair) 그래프 내의 모든 노드 쌍(u, v)에 대한 최단 경로를 찾는 문제 다익스트라 알고리즘 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단..
자료구조알고리즘/이론 2023. 4. 16. 07:15
이전 Prev 1 Next 다음