다익스트라 2

[ 알고리즘 ] 최소 신장 트리, 최단 거리 알고리즘

최소 신장 트리신장 트리 : 그래프의 모든 정점을 포함하는 트리최소 신장 트리 : 가중치가 있는 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리  프림 알고리즘(Prim algorithm) - 정점 기준그리디 알고리즘으로, 임의의 정점을 시작점으로 트리를 확장하면서 최소 신장 트리를 생성하는 방식이다. 💡 프림 알고리즘 과정시작점부터 뻗어 나가는 간선 중 가장 작은 가중치를 가진 노드로 연결한다.시작점과 연결한 노드에서 뻗어 나가는 간선 중 가장 작은 가중치를 가진 노드로 연결한다.반복한다.  크루스칼 알고리즘(Kruskal algorithm) - 간선 기준그리디 알고리즘으로, 간선을 오름차순으로 정렬한 뒤 가중치가 낮은 간선을 선택하면서 최소 신장 트리를 생성한다. 💡 크루스칼 알고리즘 과정..

[ STUDY ]/CS 2024.11.17

[ 그래프 ] 다익스트라(Dijkstra)

다익스트라그래프에서 최단 거리를 구하는 알고리즘출발 노드와 모든 노드간의 최단 거리 검색제약 조건 : 에지는 모두 양수시간 복잡도는 O(ElogV)   V: 노드 수, E: 에지 수 💡  다익스트라 알고리즘의 핵심 이론1. 인접리스트로 그래프 구현하기  2. 최단거리 배열 초기화하기  3. 값이 가장 작은 노드 고르기  4. 최단 거리 배열 업데이트 하기현재 선택된 노드의 에지들을 탐색하고 업데이트-> Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값) 5. 과정 3~4를 반복해 최단 거리 배열 완성하기과정 4에서 이미 선택됐던 노드를 다시 방문하지 않기위해 방문 배열(visited)을 만든다. ☝🏻  다익스트라 알고리즘은 출발 노드와 그외 노드 간의 최단 ..