최단 경로| 다익스트라, 벨만포드, 플로이드 비교

최단 경로 알고리즘

1) 다익스트라 : one-to-all (가중치는 양수만)

2) 벨만-포드 : ont-to-all (가중치 음수도 가능, 음수 사이클 여부 판단 시 多 사용)

3) 플로이드 : all-to-all

---

1) 다익스트라 (dijkstra) 알고리즘 | One-to-One

• 출발 노드→ 다른 모든 노드로의 최단 거리 구하는 알고리즘
• 특징은 엣지 (가중치)가 모두 양수
• 시간 복잡도 : O(E logV)

→ 특정 노드 (1개)에서 다른 노드들(all)에 대한 최단 거리 구하라는 문제가 주어졌을 때 ‘다익스트라’를 떠올려라

⬛ 다익스트라 알고리즘 수행 과정

1) 인접 리스트로 그래프 표현
2) 최단 거리 distance[] 1차원 배열 선언
           → 최초 초기화 시 Integer.MAX_VALUE로 초기화
3) PriorityQueue<>선언 필요
         : 매번 작은 가중치 우선 처리할 수 있도록 pQ 활용하여 최단 경로 갱신 목적
4) 시작점 세팅 : distance[st] = 0, pQ.offer(st, 0)
             //즉, 출발점 자기 자신에 대한 거리는 0
5) while(!pQ.isEmpty() {
    //현재 cur 노드 뽑음
    //다음 정점 nx에 대한 distance[nx] > distance[cur.e] + nx.val 인 경우
       distance[nx]를 최단 거리로 갱신 처리 후, pQ에 담기
}

---

2) 벨만-포드 알고리즘 | One-to-One

• 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 알고리즘
• 특징은 음수 가중치 엣지 존재해도 수행 가능
• 보통은 음수 사이클 존재 여부 판단하는 문제가 많다.
• 시간 복잡도 : O(VE)

⬛ 벨만 포드 알고리즘 수행 과정

1) 엣지 리스트로 그래프 구현 후, distance[] 배열 MAX로 초기화
2) 총 N-1번 매 반복마다 모든 간선 순회하며 최단 거리 배열 업데이트
3) 음수 사이클 유무 판단
(마지막에 한번 더 모든 간선 순회했는데도 업데이트 되는 노드 발생한다는 건
음수 사이클이 존재해서 가중치 감소가 나타나는 것이다.)

---

3) 플로이드 알고리즘 | All-to-All

• 모든 노드 간의 최단 경로 탐색 알고리즘
• 음수 가중치 존재해도 수행 가능
• 전체 경로의 최단 경로는 부분 경로의 최단 경로 조합이다 라는 아이디어에서 출발
• 시간 복잡도 : O(V^3) //3중 for문 도니까

⬛ 플로이드 알고리즘 수행 과정

1. 모든 N개의 정점에서 다른 N개의 정점으로의 최단거리를 구해야 하므로 distance[][] 2차원 배열 선언
2. distance[][] 초기화 (i=j) 0, 그 외는 MAX
3. 점화식 사용하여 3중 for문으로 최단 거리 갱신

for(경유지 K에 관해(1~N)
  for(출발지 S 에 관해 (1~N)
	  for(도착지 E에 관해 (1~N)
         D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) ;