[다익스트라 / 플로이드-워셜] 알고리즘 정리

🎯 다익스트라? 

그래프에서 최단 거리를 구하는 알고리즘

 

✅ 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 (출발 노드와 이어진 모든 노드 간 최단 거리 검색) 

      - 출발 노드 ~ 목적지 노드 사이 최단 거리 뿐만 아니라, 출발 노드와 연결된 모든 노드들의 최단 거리 얻을 수 있음

✅ 간선 가중치는 모두 양수여야 함!

✅ 시간 복잡도 : O(ElogV) 

 

➡️ 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어진 경우 사용한다!

🔻 과정

1. 주어진 그래프를 인접 리스트로 구현

 

2. 최단 거리 배열 초기화 : 최단 거리 배열(D[N]) 생성 → D[출발 노드] = 0, 나머지는 MAX 로 초기화

 

3. 최단 거리 배열에서 현재 값이 가장 작은 노드 선택 (처음은 당연히 출발 노드 시작)

 

4. 선택된 노드에 연결된 간선 가중치 바탕으로 연결된 노드 까지의 최소 거리 (=D[i]) 업데이트 (최솟값 비교)

   🔸 이때 중복 방지를 위해 방문 배열 체크 필수!

   🔸 현재 노드와 연결된 모든 노드 따져줘야 함, 값을 갱신한 노드는 큐에 넣어주고 턴이 끝날 때 까지 대기.

🔸 이때, 출발 노드로부터 거리가 짧은 순서대로 노드를 방문하기 위해 우선순위 큐를 사용할 것

 

5. 다음 노드와 연결된 그 다음 노드 탐색 후 업데이트 반복

 

🎯 플로이드-워셜?

최단 경로를 구할 때 사용하는 알고리즘으로, 다익스트라와 주로 비교됨

 

✅ 한 번 실행으로 모든 노드간 최단 경로 탐색 가능함 → 노드의 개수의 범위가 적은 문제에 사용 多

✅ 간선 가중치가 음수여도 가능! 

✅ 동적 계획법의 원리 차용한 알고리즘

✅ 시간 복잡도 : O(V^3)

 

💡  A → B 까지 최단 경로를 구했다 가정하고, 최단 경로 위에 노드 K가 존재하는 경우
     → K가 포함된 부분 경로 또한 최단 경로임을 이용하는 것!

🔥 점화식 
      ⇒ D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

     

🔻 과정

1. 최단 거리 저장하는 배열 선언하고 초기화

    ▫️  D[S][E] : 노드 S ~ 노드 E 까지 최단 거리를 저장하는 배열

       - D[i][i]의 값은 0, 다른 칸은 INF 로 초기화

 

2. 최단 거리 배열에 각 간선의 가중치 저장

   ▫️ 플로이드-워셜 알고리즘은 그래프 표현 시, 인접 행렬 사용할 것

 

3. 점화식으로 배열 업데이트 진행

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])

   ▫️ 위 점화식을 3중 for문 형태로 반복해 최단 거리 업데이트 함

      EX) K = 2, S = 1인 경우

         -  E = 1) D[1][1] = 0

         -  E = 2) D[1][2] = D[1][2] VS. D[1][2]+D[2][2]

         -  E = 3) D[1][3] = D[1][3] VS. D[1][2] + D[2][3] 

         -  E = 4) D[1][4] = D[1][4] VS. D[1][2] + D[2][4] 

         -  E = 5) D[1][5] = D[1][5] VS. D[1][2] + D[2][5]

 

🔸 경로의 일부인 K까지 중간 경로를 구해서  → 부분 정복 해 나가는 방식으로 구함 

 

 

 

출처 : Do-it 알고리즘 - JAVA 편