티스토리 뷰
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.
Shortest Path(최단 경로)
최단 경로 문제란 가장 짧은 경로에서 두 꼭지점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치의 합이 최소가 되도록 하는 경로를 찾는 문제이다.
예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다.
보통은 주어진 가중 그래프에서 (V는 꼭지점, E는 변, 가중치 함수 f : E → R)
가 v에서 v'로 가는 모든 경로들 중 최소가 되도록 하는 경로를 찾는 문제이다.
출처 : 위키백과
최단 경로 문제의 유형
- Single-Source : one to all
하나의 출발노드 S로부터 다른 모든 노드까지의 최단 경로를 찾아라.
예 : Dijkstra의 알고리즘
- Single-destination :
모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라.
Single-Source 문제와 동일
문제 예 :
- 입력 : 음수 사이클이 없는 가중치 방향 그래프 G=(V, E)와 출발노드 s ∈ V
- 목적 : 각 노드 v ∈ V에 대해서 다음을 계산한다.
d[v] : distance estimate
- 처음에는 d[s] = 0, d[v] = ∞ 로 시작한다.
- 알고리즘이 진행됨에 따라서 감소해간다. 하지만 항상 d[v] >= ∂(s, v)를 유지한다.
- 최종적으로 d[v] = ∂(s, v)가 된다.
- 그런 노드가 없는 경우 π[v] = NIL
π[v] : s에서 v까지의 최단 경로 상에서 v의 직전노드(predecessor)
- 기본 연산 : Relaxation
RELAX(u, v, w){ if d[v] > d[u] + w(u, v) then d[v] <- d[u] + w(u, v) π[v] <- u }
- 대부분의 Single-Source 최단 경로 알고리즘의 기본 구조
1) 초기화 : d[s]=0, 노드 v != s에 대해서 d[v] = ∞, π[v] = NIL
Generic-Single-Source(G, w, s){
INITIALISE-SINGLE-SOURCE(G, s)
repeat
for each edge(u, v) ∈ E
RELAX(u, v, w)
until there is no change
}
- Bellman-Ford 알고리즘 의사코드
BELLMAN-FORD(G, w, s){
INITIALIZE-SINGLE-SOURCE(G, s)
for i <- 1 to |V[G]|-1
do for each edge(u, v) ∈ E[G]
do RELAX(u, v, w)
for each edge(u, v) ∈ E[G]
do if d[v] > d[u] + w(u, v)
then return FALSE
return TRUE
}
시간복잡도 : O(nm)
예제를 통해 구현 소스 코드(Java)
package Sort; | |
// 벨만포드의 최단 경로 알고리즘 구현 | |
// 연결되고, 가중치가 있는 그래프를 나타내느 클래스 | |
public class BellmanFordGraph { | |
// 그래프의 가중치를 나타내는 클래스 | |
class Edge{ | |
int src, dest, weight; | |
Edge(){ | |
src = dest = weight = 0; | |
} | |
}; | |
int V, E; | |
Edge edge[]; | |
// V, E가 있는 그래프 생성 | |
BellmanFordGraph(int v, int e) { | |
// TODO Auto-generated constructor stub | |
V = v; | |
E = e; | |
edge = new Edge[e]; | |
for(int i=0; i<e; ++i) { | |
edge[i] = new Edge(); | |
} | |
} | |
// 벨만포드 알고리즘을 이용하여 src에서 다른 정점들까지의 최단거리를 찾는 메인 기능 | |
// 음의 무게 주기 감지 | |
void BellmanFord(BellmanFordGraph graph, int src) { | |
int V = graph.V, E = graph.E; | |
int dist[] = new int[V]; | |
// 1단계 : src에서 다른 정점으로 모든 정점 초기화 | |
for(int i=0; i<V; ++i) { | |
dist[i] = Integer.MAX_VALUE; | |
} | |
dist[src] = 0; | |
// 2단계 : 모든 edge|V|-1회, | |
// src에서 다른 정점들까지의 간단한 최단경로는 |V|-1 선을 가질 수 있다. | |
for(int i=1; i<V; ++i) { | |
for(int j=0; j<E; ++j) { | |
int u = graph.edge[j].src; | |
int v = graph.edge[j].dest; | |
int weight = graph.edge[j].weight; | |
if(dist[u] != Integer.MAX_VALUE && dist[u]+weight< dist[v]) { | |
dist[v] = dist[u]+weight; | |
} | |
} | |
} | |
// 3단계 : 비 가중치 사이클 점검 | |
// 만약 더 짧은 길을 가진다면 순환이 이루어진다 | |
for(int j=0; j<E; ++j) { | |
int u = graph.edge[j].src; | |
int v = graph.edge[j].dest; | |
int weight = graph.edge[j].weight; | |
if(dist[u] != Integer.MAX_VALUE && dist[u]+weight < dist[v]) { | |
System.out.println("Bellman-Ford Graph contains negative weight cycle"); | |
} | |
} | |
printArr(dist, V); | |
} | |
// 배열 출력 | |
void printArr(int dist[], int V) { | |
System.out.println("Vertex Distance from Source"); | |
for(int i=0; i<V; ++i) { | |
System.out.println(i+"\t\t"+dist[i]); | |
} | |
} | |
public static void main(String[] args) { | |
// TODO Auto-generated method stub | |
int V = 5; // 그래프의 점의 수 | |
int E = 8; // 그래프의 선의 수 | |
BellmanFordGraph graph = new BellmanFordGraph(V, E); | |
// add edge 0-1 | |
graph.edge[0].src = 0; | |
graph.edge[0].dest = 1; | |
graph.edge[0].weight = -1; | |
// add edge 0-2 | |
graph.edge[1].src = 0; | |
graph.edge[1].dest = 2; | |
graph.edge[1].weight = 4; | |
// add edge 1-2 | |
graph.edge[2].src = 1; | |
graph.edge[2].dest = 2; | |
graph.edge[2].weight = 3; | |
// add edge 1-3 | |
graph.edge[3].src = 1; | |
graph.edge[3].dest = 3; | |
graph.edge[3].weight = 2; | |
// add edge 1-4 | |
graph.edge[4].src = 1; | |
graph.edge[4].dest = 4; | |
graph.edge[4].weight = 2; | |
// add edge 3-2 | |
graph.edge[5].src = 3; | |
graph.edge[5].dest = 2; | |
graph.edge[5].weight = 5; | |
// add edge 3-1 | |
graph.edge[6].src = 3; | |
graph.edge[6].dest = 1; | |
graph.edge[6].weight = 1; | |
// add edge 4-3 | |
graph.edge[7].src = 4; | |
graph.edge[7].dest = 3; | |
graph.edge[7].weight = -3; | |
graph.BellmanFord(graph, 0); | |
} | |
} | |
- Single-Pair : one to one
주어진 하나의 출발 노드 S로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라.
최악의 경우 시간복잡도에서 Single-Source 문제보다 나은 알고리즘이 없음
- All-Pairs : all to all
모든 노드 상에 대해서 최단 경로를 찾아라.
예 : Floyd의 알고리즘이 가장 유명하다.
최단 경로의 기본 특성
- 최단 경로의 어떤 부분 경로도 역시 최단 경로이다.
- 최단 경로는 사이클을 포함하지 않는다.(음수 사이클이 없다는 가정하에서)
'알고리즘' 카테고리의 다른 글
Floyd-warshall(플로이드-워셜) 알고리즘 (0) | 2017.12.21 |
---|---|
Dijkstra(다익스트라) 알고리즘 (0) | 2017.12.21 |
Prim(프림)의 알고리즘 (0) | 2017.12.18 |
Kruskal(크루스칼) 알고리즘 (1) | 2017.12.18 |
MST(Minimum Spanning Tree, 최소비용신장트리) (0) | 2017.12.17 |