최단 경로, 최소 신장

최단 경로 알고리즘

최단 경로 알고리즘은 두 개의 정점 사이의 가장 짧은 경로를 찾는 알고리즘이다. 이 알고리즘은 그래프의 가중치를 이용하여 경로를 선택하며, 가중치는 간선에 할달된 비용을 의미한다. 그래프에서 가장 짧은 경로를 찾는 것은 네트워크 라우팅, GPS 네비게이션, 물류 최적화 증 다양한 분야에서 활용 된다. 

 

가장 대표적인 최단 경로 알고리즘으로는 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이 있다.

 

# 다익스트라(Dijkstra)

• 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘을 말한다.
• 한 노드에서 다른 모든 노드로의 최단 경로를 구하는 데 사용한다.
• 간선에 음의 가중치가 없어야 한다. 
• 그리디 + DP 형태를 가지고 있다. 
• 알고리즘 복잡도 : O(ElogN) E: 간선, N:노드
• 순서
  1. A기준으로 주변 노드로 가는 가중치를 계산하여 배열에 입력
  2. 가장 작은 가중치를 가진 위치의 노드로 이동한다. 
  3. 해당 노드에서 연결된 노드와 이전 노드의 가중치의 합이 다음 노드로 가는 가중치 보다더 작다면 해당 가중치로 업데이트 한다. (2와 3번 반복) 

 

# 벨만 - 포드 (BellMan - Ford)

• 음수 간선이 포함되어 있어도 최단 경로를 구할 수 있다.
  • 음수 사이클이 있으면 정상작동 하지 않는다. 
• 매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느리다.
• 알고리즘 복잡도 : O (VE)

• 음수 사이클을 구별하는 방법은 V 수 만큼 반복한 값과  V + 1 까지 반복한 값을 비교했을 때, 값이 다르다면 그래프가 음의 사이클에 의해 비정상 작동 한다고 할 수 있다. 

 

# 플로이드 워셜(Floyd - Warshall)

• 모든 노드 간의 최단 경로를 구하는 알고리즘
• 음의 간선이 포함되어 있어도 사용 가능하다. 
  • 음수 사이클이 있으면 정상 작동 하지 않는다. 
• 알고리즘 복잡도 : O(V^3)

 

---

최소 신장 트리(MST)

• MST : Minimun Sponning Tree
• 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법
  • 크루스칼, 프림

 

# 크루스칼(Kruskal) 알고리즘

• 간선 중 최소 값을 가진 간선부터 연결
• 사이클 발생 시 다른 간선 선택
• 주로 간선 수가 적을 때 사용한다. 
• 알고리즘 복잡도 : O(E log E)

 

# 프림(Prim) 알고리즘

• 임의의 노드에서 시작
• 연결된 노드의 간선 중 가장 낮은 가중치를 갖는 간선을 선택
• 간선의 개수가 많을 때 크루스칼 보다 유리함
• 알고리즘 복잡도 : O (E log V)