최단 경로 문제
최단 경로 문제란, 가중그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제입니다.
최단 비용을 구하는 알고리즘에는 다익스트라 알고리즘, 벨만 포드 알고리즘, 프로이드 워샬 알고리즘 등이 있습니다.
그리고 최단 경로 계산하는 방식에도 아래와 같은 종류가 있습니다.
- (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기
- (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기
- (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기
최단 거리 알고리즘
다익스트라 알고리즘
다익스트라 알고리즘은 One-To-All 방식으로 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 입니다.
단순히 시작노드로부터 특정 노드까지의 최단거리를 구할 수 있을거라 생각하기 쉬운데 최종적으로 얻고자 하는것은
시작정점으로부터 시작정점을 제외한 모든 노드 i 까지의 최단거리가 적힌 테이블입니다.
다익스트라 알고리즘은 모든 노드를 빠짐없이 방문하며 지속적으로 최선의 값으로 업데이트 해줍니다.
우리가 업데이트하는것은 해당 특정 정점의 인접정점에 대한 거리테이블입니다.
방문하지 않았던 노드를 방문하며, 방문노드의 인접정점 테이블을 업데이트 해주는데, 테이블에 존재했던 기존 최단경로의 값과 방문노드를 통해서 갈 수 있는 새로운 경로에 드는 비용을 계산하여 둘 중 더 작은값으로 인접 정점에 대한 최소 거리로 업데이트합니다.
DP인 이유는 특정 노드까지 갈 수 있는 최단경로는 이전의 최단경로로 나타낼 수 있기 때문입니다.
작동과정
- 출발노드를 설정합니다.
- 출발노드를 기준으로 각 노드의 최소비용을 저장합니다.
- 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택합니다. 선택 이후에는 해당 노드를 구분하기 위해 방문처리 해주어야 합니다.
- 최단거리 테이블 업데이트
위의 과정에서 3-4번을 반복하면 됩니다.
사실 모든 블로그에 써있는 작동과정인데 이렇게만 보면 이해가 잘 안간다.
선택노드의 기준에 대한 설명이 충분하지 않아 테이블 업데이트할때 어떤 노드 기준인지 이해하느라 힘들었다.
아무튼 이해하고 천줄로 적었는데 줄이고 줄인 다익스트라 요약집입니다. 나 지금 에츠허르 다익스트라..
최단거리 테이블 업데이트
다익스트라는 모든 노드를 방문하며, 최선의 선택인 최소의 비용으로 업데이트 해야 하는데 (Greedy), 비용을 계산할 때 기존의 테이블값을 이용합니다.
그래프의 특성 상 인접노드까지의 다른 경로가 존재했을수도 있습니다.
만약 인접노드까지 도착 할 기존의 방법이 있었는데, 새로운 경로를 통해 인접노드까지 가는 경로가 개척된다면 그 새로운 경로가 베스트인지 기존 다른경로로 왔던 비용과 비교해주어야 합니다.
예를 들어 방금 방문한 노드를 P, P의 인접노드를 C라고 해봅시다.
중요한건 여기서 업데이트 하려는 테이블의 주인은 P의 인접노드인 C입니다.
C까지의 경로에 드는 비용은 아래와 같습니다.
- C까지의 기존 최단 경로 ( In table , P를 거치지 않음 ): Start to C
- C까지의 새로운 경로 ( P를 거쳐감 ): Start to P + P to C (가중치)
시작 노드에서 C까지의 모든 경로 중 최단 경로로 업데이트 하는게 목적인데,
기존 테이블에 적혀있던 Start to C 와 새로운 방법인 시작노드에서 P까지의 최단거리정보(Start to p) 와 P에서 C까지의 거리(P to C)의 합 을 비교하여 작은 값으로 업데이트 하는게 다익스트라 입니다.
테이블에는 여지껏 최소비용으로 업데이트 해왔던 Start to C 와 Start to p 가 존재할거고 그 값을 그대로 가져와 새로운 경로를 계산하고 비교하여 더 작은 거리를 적어주는 것입니다.
모든 노드에 대해 P를 옮겨가며 적용해준다면, 최종 테이블에는 시작 정점에서 출발해 각각의 노드에 대한 시작정점으로부터의 최단거리만이 남아있게 됩니다.
테이블은 아래의 공식을 적용하여 업데이트 합니다.
min(선택노드의 최단거리 배열의 값(start to C), 간선 가중치(p to C)+연결노드의 최단 거리 배열 값(start to p))
결과
다익스트라 알고리즘을 이용해 완성한 배열은 출발 노드 이외의 모든 노드간의 최단거리를 표현합니다.
예를 들어 노드의 개수가 N개이면, N-1개의 거리정보를 반환합니다.
특징
- 그래프의 최단 경로 구하는 알고리즘 (그리디 & 다이나믹 프로그래밍)
- 하나의 정점에서 출발하여 도착할 수 있는 모든 노드 에 대한 최단거리 정보 를담은 표를 구할 수 있음
- 음수 가중치 없어야 함
- 인접행렬로 표현된 그래프의 경우 시간복잡도
- 우선순위 큐를 사용하여 까지 낮출 수 있음 (개선된 다익스트라 알고리즘)
-
이전까지 구했던 최단거리 정보를 그대로 사용해서, 최단거리가 확정된다면 해당 정점을 탐색하지 않고 나머지 정점들에 대해 탐색을 계속합니다.
-
그래서 다익스트라 알고리즘에서도 방문한 노드에 대해서는 방문처리 해주어야 합니다.
다익스트라 알고리즘 구현
다익스트라 알고리즘을 인접 리스트 그래프 + 우선순위 큐를 사용하여 구현해보겠습니다.
Node클래스
Node클래스를 만듭니다. 이 클래스는 우선순위 큐에 정점번호 + 가중치 저장을 위해 만드는 것 입니다.
int index;
int cost;
public Node(int index, int cost) {
this.index = index;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.cost, o.cost);
}
}
public class Main {
static ArrayList<Node>[] graph;
//노드의 크기, 출발지
public static void Dijkstra(int n, int start) {
boolean[] check = new boolean[n + 1];
int[] dist = new int[n + 1];
int INF = Integer.MAX_VALUE;
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
while(!pq.isEmpty()) {
int nowVertex = pq.poll().index;
if(check[nowVertex]) continue;
check[nowVertex] = true;
//index의 연결된 정점 비교
for(Node next : graph[nowVertex]) {
if(dist[next.index] > dist[nowVertex]+ next.cost) {
dist[next.index] = dist[nowVertex] + next.cost;
pq.offer(new Node(next.index, dist[next.index]));
}
}
}
//최소거리 출력
for(int i : dist) {
if(i == INF) System.out.print(0 + " ");
else System.out.print(i+" ");
}
}
public static void main(String[] args) throws IOException {
//그래프 입력 받기
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//정점의 개수, 간선의 개수
int n = Integer.parseInt(bf.readLine());
int m = Integer.parseInt(bf.readLine());
graph = new ArrayList[n+1];
for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
StringTokenizer st;
for(int i = 0 ; i < m; i++) {
st = new StringTokenizer(bf.readLine());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph[v].add(new Node(w, cost));
}
int start = Integer.parseInt(bf.readLine());
//다익스트라 알고리즘 수행
Dijkstra(n, start);
}
}