DAGSP1 [알고리즘] DAG 최단 경로 문제(DAG Shortest Path Problem) Directed Acyclic Graph(DAG)DAG란 그래프 연결에 방향이 있고(Directed), 한 곳에서 순환이 발생하지 않는(Acyclic) 그래프(Graph)를 의미합니다.Edge RelaxationDAG Shortest Path 문제를 풀기 위해 Edge Relaxation 개념이 필요합니다. Edge Relaxation이란, 가중치가 있는 그래프(Weighted Graph)에서, 각 edge에 배정되어 있는 만큼의 가중치를 더해가며 탐색할 때, 더 나은(작은) 경로의 가중치가 있다면 그 값으로 update하는 것을 의미합니다. 말이 어렵게 느껴지는데 굉장히 쉬운 개념입니다. 결국 더 나은 대안으로 수정한다는 의미입니다. 그리고 앞으로 그래프에서 이 작업을 Relax라고 부릅니다.그림으로 .. 2023. 12. 1. 이전 1 다음
