그래프 알고리즘

그래프 대표 알고리즘에 대해 간략히 살펴보겠습니다.1. 플로이드-워셜 알고리즘특징: 모든 쌍의 최단 경로를 구하는 데 적합. 그래프의 모든 노드 쌍에 대해 최단 경로를 계산.시간 복잡도: O(V^3)장점: 구현이 상대적으로 간단하고, 모든 쌍의 최단 경로를 구할 수 있음. (삼중 For문)단점: 시간 복잡도가 높아 노드 수가 많을 경우 비효율적.적용 경우:그래프의 모든 노드 쌍의 최단 경로를 구해야 하는 경우.노드 수가 상대적으로 적고(200개 정도?), 간선의 가중치가 음수일 수도 있는 경우.2. 다익스트라 알고리즘특징: 단일 출발점 최단 경로를 구하는 데 적합. 하나의 시작점에서 다른 모든 노드로의 최단 경로를 계산.시간 복잡도: O((V+E)log⁡V)(우선순위 큐 사용 시)장점: 효율적이며, 많은..

2024.08.08