[알고리즘] 최단 경로 문제_다익스트라 & 벨만포드

다익스트라 & 벨만포드

이 두 알고리즘은 그래프에서 최단 경로 문제를 해결할 때 사용되는 알고리즘이다.

최단 경로 문제? 최단 경로란 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다.

최단 경로 문제를 푸는데 다양한 방법이 있지만, 다익스트라와 벨만포드를 정리해보려고 한다.

다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 그래프에서 음의 가중치가 없을 때 최단 경로를 찾을 수 있다.

V개의 정점과 양의 가중치를 가진 E개의 간선을 가진 그래프에서 출발 정점으로부터 모든 최단 경로를 찾을 수 있다.

알고리즘은 다음과 같이 진행된다.

1. 현재 정점에 연결되어 있는 정점들을 모두 본다.
2. 현재 정점과 연결되는 다음 정점으로의 거리와 시작 정점과 현재 정점까지의 최단 거리의 합이 시작 정점과 다음 정점까지의 최단거리 합보다 작으면 갱신해준다.
3. 모든 정점을 방문하여 최단 경로 테이블을 완성한다.

큐를 이용하여 구현하게 되면 O(V^2)의 시간 복잡도를 가지고, 우선순위 힙을 이용하게 되면 O(ElogV)의 시간 복잡도를 가진다.

벨만-포드 알고리즘(Bellman-Ford-Algorithm)

벨만포드 알고리즘은 음의 가중치가 있어도 최단 경로를 찾을 수 있다.

V개의 정점과 E개의 간선을 가진 그래프에서 출발 정점으로부터 모든 최단 경로를 찾을 수 있고, 음의 사이클도 찾을 수 있다.

알고리즘은 다음과 같이 진행된다.

1. 그래프내에 모든 간선에 대해서 2번 시행한다.
2. 정점 A에서 정점 B로 가는 간선에서 현재 B로가는 최단 경로보다 A로 가는 최단 경로와 현재 간선의 가중치의 합이 더 적다면 갱신해준다.
3. 더 이상 갱신이 이루어 지지 않을 때까지 반복하는데, (정점의 수)번 시행이 이루어진 후에도 갱신이 이루어진다면 음의 순환이 일어나고 있다고 판단하고 종료한다.

총 연산횟수는 V*E이므로, O(VE)의 시간복잡도를 가진다.

구현

다익스트라와 벨만포드 알고리즘을 백준 1916번 최소비용 구하기 문제에 적용해 보았다.

[Algorithm/Java][백준] 1916번 최소비용 구하기