최단 경로 문제 유형, 다익스트라 알고리즘

그래프 최단 경로 찾기 문제 유형

PS에서 최단 경로 문제는 다음과 같은 종류로 나눌 수 있다.

• 단일 출발 - 단일 도착 최단 경로
  • 그래프 내 특정 노드 A에서 출발해서, 다른 특정 노드 B에 도착하는 가장 짧은 경로를 찾는 문제

    

  • 위와 같은 가중치 그래프가 주어졌을 때, A-F 간 최단 경로를 찾는 경우가 이에 해당한다.

• 단일 출발 최단 경로
  • 그래프 내 특정 노드 A에서 출발해서, 그래프에 존재하는 모든 노드들에 대한 가장 짧은 경로를 찾는 문제
  • 그래프 내 가중치들이 음수가 아닌 경우에 다익스트라 알고리즘을 사용한다

• 전체 쌍(all pair) 최단 경로
  • 그래프 내 모든 노드 쌍들에 대한 최단 경로를 찾는 문제
  • 플로이드 와샬 등의 알고리즘을 사용

다익스트라 알고리즘

• 시작 노드를 기준으로 하여 연결되어 있는 노드들을 추가하며 최단 경로들을 갱신해 나가는 알고리즘

• BFS기반이며,
  1. 첫 노드가 A라면, A부터 모든 노드의 최단 거리를 저장할 배열
  2. 우선 순위 큐(가중치가 우선 순위)

  두가지가 필요하다.

로직

1. 초기화

• 노드 수 만큼 배열을 생성하고, 시작 점 노드 인덱스의 값은 0으로, 나머지 노드 인덱스 값은 무한대 값으로 초기화 한다. 그리고 우선순위 큐에 시작 점 노드 인덱스의 가중치 값을 0으로 하여 넣는다.

  

2. 우선 순위 큐에서 값 추출 후, 인접 노드와 거리 계산

• 우선순위 큐에서 값(가중치 값, 노드 인덱스)을 꺼내 해당 노드의 인접 노드들을 방문한다.

• 꺼낸 가중치 값 + 인접 노드 까지의 가중치를 더한 값이 최단 거리 배열에 저장된 값보다 작으면 배열을 업데이트 시키고 우선순위 큐에 넣는다, 같거나 크면 아무 작업도 하지 않는다

• 이 작업을 우선순위 큐가 빌 때까지 반복한다. 로직이 종료되고 난 후 배열에 저장된 값이 시작 노드에서 다른 노드 까지의 최단 경로이다.

Uploaded by N2T