최단 경로 탐색 알고리즘
최단 경로 탐색 알고리즘이란?
그래프의 한 노드에서 다른 노드까지의 경로 중 간선의 가중치의 합이 최소가 되는 경로를 찾는 알고리즘
- Single Source : 하나의 시작점에서 다른 모든 점까지의 최단 경로를 구하는 알고리즘
- Single Destination : 하나의 목적지까지 다른 모든 점에서 출발하는 최단 경로를 구하는 알고리즘
- Single Pair : 하나의 시작점에서 다른 하나의 목적지까지의 최단 경로를 구하는 알고리즘
- All Pair : 그래프의 모든 쌍에 대하여 최단 경로를 탐색하는 알고리즘
💡 BFS
그래프의 모든 간선의 가중치가 같거나, 가중치가 없을 경우
- Queue를 이용하여 구현할 수 있다.
- 경로 탐색의 시작점을 Queue에 push한다.
- Queue가 empty 상태가 될 때까지 무한루프
- Queue의 front를 꺼낸 후 해당 노드와 인접한 노드들이 아직 방문하지 않은 노드일 경우 Queue에 push
📍 구현 코드 예시
while (!q.empty()) { int node = q.front(); q.pop(); // front 노드 꺼내기 visited[node] = 1; // 방문 for (int i = 0; i < EDGE[node].size(); i++) { int neigh = EDGE[node][i]; // 인접 노드 if (visited[neigh] == -1) { q.push(neigh); dis[neigh] = dis[node] + 1; visited[neigh] = 1; /* 방문하지 않은 노드일 경우 Queue에 push 후 방문 표시, distance(거친 노드 수) update */ } } }
💡 Dijkstra
음의 가중치가 없는 그래프에서 Single Source, Single Destination, Single Pair 경로 탐색 가능
- 출발점에서 인접한 노드들에 대한 가중치 update
- 그 중 가장 짧은 경로를 가진 노드를 최단 경로에 추가(방문)
- 아직 방문하지 않은(최단 경로에 포함하지 않은) 노드들에 대하여 다시 가중치 update
가중치 = min(update된 최단 경로에서의 가중치, 원래 가중치)
- 모든 노드를 방문하여 최단 경로에 추가할 때까지 위의 2, 3번 과정 반복
📍 구현 코드 예시
Dijkstra(const int n, const int v) { // n은 노드의 수, v는 시작점 for(int i=0; i<n; i++) { // initialize s[i] = false; // 방문 여부 dist[i] = length[v][i]; // 시작 점에서의 거리 } s[v] = true; // 시작점 방문 dist[v] = 0; // 시작점의 거리는 0 for(int i=0; i<n-2; i++) { // 시작점에서 n-1개의 path를 거쳐 목적지로 도달 int u = Choose(n); // 최단 경로를 가지는 노드 선택 s[u] = true; // 방문 for(int w=0; w<n; w++) if(s[w] == false) dist[w] = min(dist[u] + length[u][w], dist[w]); // update된 최단 경로를 가지고 다른 노드까지의 최단 경로 update }
- Complexity
- 최단 경로에 포함될 다음 노드를 선택할 때 : O()
- 인접 List 또는 인접 행렬를 사용할 경우 한 경로가 update될 때마다 다른 각 노드에 대한 최단 경로가 update되어야 한다.
- Total : O()
- (추후 수정)
💡 Bellman-Ford
음의 가중치를 포함하는 그래프에서 Single Source, Single Destination, Single Pair 경로 탐색 가능
- Dijkstra에서 음의 가중치가 있을 경우 cycle이 형성되어 무한반복 ➡ 최단 경로를 구할 수 없음
- n개의 점이 있는 그래프에서 한 점에서 다른 한 점까지의 최단 경로는 사이클이 없을 때 최대 n-1개의 간선을 지난다.
- 한 점 d에서 다른 점 v까지 이동한다고 할 때, 시작점에서 v까지 k개의 간선을 거친다고 가정하면, 시작점에서 d까지는 k-1개의 간선을 거친다.
- 시작점에서 d까지의 경로는 현재까지 구한 최단 경로이므로 여기에 d에서 v까지의 최단경로를 더하면 새로운 최단경로가 된다는 것을 보장한다.
D(v, k) = min{ D(v, k-1), min(D(d, k-1) + length(d, v)) }
- D(v, k)는 k개의 간선을 거쳐 v까지 도달하는 최단 경로를 말한다.
- 여기서 d는 v에 인접한 모든 점들을 말한다.
- 이 과정을 최단 경로에 n-1개의 간선이 포함될 때까지 반복한다.
- n-1개의 간선을 가지는 최단 경로를 구한 후, 다시 한번 최단 경로 update를 수행할 때 이전 경로와 다른 최단경로가 update될 경우, 음의 가중치가 있음을 알아낼 수 있다.
- 이 경우 사이클이 발생하기 때문에 정상적인 최단경로를 계산할 수 없다.
📍 구현 코드 예시
BellmanFord(const int n, const int s) { // n은 노드의 수, s는 시작점 for(int i=0; i<n; i++) dist[i] = length[s][i] // 시작점에서의 경로 초기화 for(int k=2; k<n-1; k++) // n-1개의 경로 for(each v such that v != s and v has at least one incoming edge) // 시작점 외에 다른 점들까지 for(each <w, v> in the graph) dist[v] = min(dist[v], dist[w] + length[w][v]) // 최단경로 update }
- Complexity
- 인접 행렬을 사용할 경우 O()
- 인접 리스트를 사용할 경우 O()
Author And Source
이 문제에 관하여(최단 경로 탐색 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hnym1104/최단-경로-탐색-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)