최단거리 구하기
-
너비 우선 탐색을 통한 최단거리 구해보기알고리즘 이론/알고리즘 구현 2019. 9. 3. 02:47
너비 우선 탐색(BFS) 은 그래프에서의 최단 경로 문제를 푸는 용도로 사용 된다. 최단 경로 문제는 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾 는문제 이다. 코드 ( C ++ ) #include #include #include #include using namespace std;vector adj; // start에서 시작해 그래프를 너비 우선 탐색하고 시작점부터 각 정점까지// 최단 거리와 너비 우선 탐색 스패닝 트리 계산// distance[i] = start부터 i까지의 최단 거리// parnet[i] = 너비 우선 탐색 스패닝 트리에서 i 의 부모의 번호, 루트일 경우 자신의 번호void bfs2(int start, vector& distance, vector& parent){di..