그래프 알고리즘

Singapore

---

그래프 대표 알고리즘에 대해 간략히 살펴보겠습니다.

1. 플로이드-워셜 알고리즘

• 특징: 모든 쌍의 최단 경로를 구하는 데 적합. 그래프의 모든 노드 쌍에 대해 최단 경로를 계산.
• 시간 복잡도: O(V^3)
• 장점: 구현이 상대적으로 간단하고, 모든 쌍의 최단 경로를 구할 수 있음. (삼중 For문)
• 단점: 시간 복잡도가 높아 노드 수가 많을 경우 비효율적.
• 적용 경우:
  • 그래프의 모든 노드 쌍의 최단 경로를 구해야 하는 경우.
  • 노드 수가 상대적으로 적고(200개 정도?), 간선의 가중치가 음수일 수도 있는 경우.
    
    

2. 다익스트라 알고리즘

• 특징: 단일 출발점 최단 경로를 구하는 데 적합. 하나의 시작점에서 다른 모든 노드로의 최단 경로를 계산.
• 시간 복잡도: O((V+E)log⁡V)(우선순위 큐 사용 시)
• 장점: 효율적이며, 많은 실제 문제에 사용 가능.
• 단점: 음수 가중치가 있는 간선이 있는 경우 사용할 수 없음.
• 적용 경우:
  • 단일 시작점에서 다른 모든 노드로의 최단 경로를 구하는 경우.
  • 그래프의 가중치가 모두 비음수인 경우.
    
    

3. 벨만-포드 알고리즘

• 특징: 단일 출발점 최단 경로를 구하는 데 적합. 음수 가중치 간선이 있는 그래프에서도 사용 가능
• 시간 복잡도: O(VE)
• 장점: 음수 가중치가 있는 그래프에서도 동작하며, 음수 사이클을 감지할 수 있음.
• 단점: 다익스트라 알고리즘보다 느림.
• 적용 경우:
  • 단일 시작점에서 다른 모든 노드로의 최단 경로를 구해야 하며, 그래프에 음수 가중치가 존재할 수 있는 경우.

 

문제에 따른 알고리즘 선택

• 모든 쌍의 최단 경로:
  • 플로이드-워셜: 노드 수가 적고, 모든 쌍의 최단 경로를 구해야 하는 경우.
• 단일 시작점 최단 경로:
  • 다익스트라: 그래프의 가중치가 모두 비음수일 경우.
  • 벨만-포드: 음수 가중치가 존재하거나 음수 사이클을 감지해야 하는 경우.