반응형 IT Tech/Application38 벨만포드 알고리즘 벨만포드 알고리즘 다익스트라 알고리즘과 동일하게 최단거리를 구하는 알고리즘 차이점은 간선이 단방향 음의 가중치를 가지고 있음 Step 1. 시작 정점부터 다른 정점까지의 거리 값을 무한으로 초기화합니다. (시작 정점은 0) Step 2. 현재 정점의 모든 인접 정점들을 탐색하여 인접 정점까지의 거리보다 현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧다면 인접 정점까지의 거리를 갱신 Step 3. 만약 정점의 개수이상으로 진행이 되고 가중치가 갱신이 되면 음의 사이클 존재 // true: 음수 순환 존재, false: 음수 순환 존재하지 않음 static boolean bellmanford(int start){ dist[start] = 0; // 정점의 개수인 n번 반복 for(int i=0; i 2022. 9. 17. 트리 : 우선순위 큐 완전 이진트리 형태의 자료구조 일차원 배열로 구현 배열로 구현하였기 때문에 부모 또는 자식 노드를 찾아가는 연산을 구현하기도 간편하다. 왼쪽 자식노드 index = (부모 노드 index) * 2 오른쪽 자식노드 index = (부모 노드 index) * 2 + 1 부모 노드 index = (자식노드 index) / 2 최소힙 : 부모노드의 키 값이 자식노드의 키 값보다 항상 작다. 최대힙 : 부모노드의 키 값이 자식노드의 키 값보다 항상 크다. 힙(Heap) 삽입연산 1. 트리의 가장 마지막 위치에 노드 추가 2. 추가된 노드와 그 부모 노드관계가 힙조건을 만족하는지 확인 3. 만족하지 않을 경우 부모와 자식의 키값 교환 4. 조건이 만족하거나 추가된 노드가 root 노드가 될때까지 2, 3번 과정 반.. 2022. 9. 16. 트리 : MST (Minimum Spanning Tree), 최소신장트리 MST : 그래프의 모든 정점을 연결할 수 있는 최소비용의 트리 만들기 신장트리(Spanning Tree) : 무방향으로 모든 정점을 포함하는 트리 . 깊이우선트리(DFS) 신장트리 : Depth가 높고 길죽하게 생성되는 트리 . 너비우선(BFS) 신장트리 : Depth는 낮지만 넓게 생성되는 트리 구현방법 2가지 1. 크루스칼 알고리즘 : 간선을 하나씩 선택해서 MST를 만듬 a. 최초에 모든 간선을 가중치에 따라 오름차순으로 정렬 b. 간선의 가중치가 낮은 간선을 선택, (Union-Find로 사이클 여부 체크) c. 모든 간선이 선택될때까지 반복 -> 중간단계에서는 하나의 트리가 아닌 여러개의 트리가 생성되며 최종적으로 하나의 트리로 연결됨 2. 프림 알고리즘 : 하나의 정점에서 연결된 간선들 중에.. 2022. 9. 16. 다익스트라와 관련 알고리즘 : 벨만포드, BFS, 플로이드워셜 벨만포드 - 음수간선 처리 가능(음수간선은 반드시 단방향) - 약 3000개 노드 BFS - 모든 간선이 동일한 가중치를 가지는 경우 플로이드워셜 - 모든 쌍의 최단경로 계산 - 200~400개 노드 2022. 9. 16. 다익스트라 1. 다익스트라 - 음수 가중치가 없는 그래프에서 시작 정점에서 다른 정점으로 최단 경로를 구하는 알고리즘 - 우선순위 큐를 활용하여 구현 - 기본동작 . 모든 정점의 거리를 무한대로 설정 . 출발점에서 주변의 정점들을 방문하며 거리 갱신 . 미방문 정점 중 가장 거리가 짧은 정점 선택 . dist[A] + Edge[A,X] 2022. 9. 13. 이전 1 2 3 4 5 ··· 8 다음 반응형
