벨만포드1 최단거리 개념 및 문제 접근 방법 0. 개요 - 최단 거리 알고리즘은 그래프 탐색 알고리즘 중 하나이다. - 최단 거리 알고리즘의 종류와 개념 그리고 문제 접근 방법에 대해서 알아보자. 1. 최단 거리 개념과 종류 a) 최단 거리의 의미 - 최단 거리 문제에서 최단 거리는 다음 2가지 경우 중 하나에 해당한다. → 지나온 간선(edge)의 개수가 가장 적은 경로를 찾는 경우 (가중치가 없는 그래프) → 지나온 간선(edge)의 가중치(weight) 합이 가장 작은 경로를 찾는 경우 (가중치가 있는 그래프) b) 최단 거리의 종류 - 최단 거리 문제는 기본적으로 시작점과 도착점이 주어진다. - 시작점과 도착점을 기준으로 최단 경로(간선의 개수 또는 간선 가중치의 합)를 구하는 것이 문제의 핵심이다. - 시작점과 도착점의 구성 방식에 따라서.. 2022. 7. 18. 이전 1 다음