728x90
목차
최단 경로
간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로
- 하나의 시작 정점에서 끝 정점까지의 최단 경로
다익스트라 (dijkstra): 음의 가중치 허용x
벨만-포드(Bellman-Ford) : 음의 가중치 허용o
- 모든 정점들에 대한 최단 경로
플로이드-워샬(Floyd-Warshall) 알고리즘
1. Dijkstra 알고리즘
시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
탐욕 기법을 사용 - 프림 알고리즘과 유사
시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재
이때 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지으 ㅣ최단 경로로 구성됨
s→t = s→x + x→t
시간복잡도 : O(ElogV)
과정
- 시작 정점을 입력 받음
- 거리를 저장할 배열을 ∞로 초기화, 시작점에서 연결된 정점들의 비용을 기록해둠
- 최단 거리가 가장 짧은 정점을 집합에 포함
- 아직 방문하지 않은 점들이 가지고 있는 거리 값과 현재 정점에서 방문하지 않은 정점까지의 가중치의 합이 작다면 update
- 모든 정점을 방문할 때까지 3,4를 반복
MST_Dijkstra(G, r)
for u in G.V
d[u] = ∞
d[r]=0
Q = G.V // 우선순위 큐
while (Q != 0) // 빈 q가 아닐 동안
u = extract_min(Q) // key 값이 가장 작은 정점
visited[u]=true
for (v in G.Adj[u]) // u의 인접 정점 v
if (!visited[v] and d[v] > d[u] + weight(u, v)) // 거리 갱신
d[v] = d[u]+weight(u,v)
prev[v]=u;
private static void dijkstra(int st) {
PriorityQueue<Node> pq = new PriorityQueue<>();
boolean[] visited = new boolean[V];
pq.add(new Node(st, 0));
dist[st] = 0;
while (!pq.isEmpty()) {
Node curr = pq.poll();
visited[curr.v] = true;
// 연결된 노드
for (Node node : adjList[curr.v])
if (!visited[node.v] && dist[node.v] > dist[curr.v] + node.weight) {
dist[node.v] = dist[curr.v] + node.weight;
pq.add(new Node(node.v, dist[node.v]));
}
}
}
2. 벨만-포드 알고리즘
간선의 가중치가 음의 값을 허용하는 실수인 경우의 최단 경로 알고리즘
(정점 - 1)번 반복하며 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. (다익스트라와 차이)
시간 복잡도: O(VE)
BellmanFord(G, r)
for u in V
d[u] = ∞
d[r] = 0;
for (i=1 to V-1)
for each (u, v) in E // (변동이 생긴 점에 대해서 확인하면 좀 더 효율적)
if (d[u] + weight(u, v) < d[v])
d[v] = d[u]+weight(u, v)
prev[v] = u;
// 음의 사이클 존재 확인
for each (u, v) in E
if (d[u]+ w(u, v) < d[v]) print("음의 사이클 존재")
i번째 루프가 끝나면 최대 i개의 간선을 사용해서 이를 수 있는 최단 경로가 계산됨
가능한 간선의 개수가 V-1이기 때문에 V-1까지 탐색한다
벨만-포드 알고리즘은 음의 가중치를 허용하지만, 음의 사이클이 존재하는 경우는 최단 경로를 구할 수 없다.
V-1번 탐색을 통해 모든 간선을 확인한 후에도 d[u]+ w(u, v) < d[v]
라면 음의 사이클이 존재하는 것을 확인할 수 있다.
static boolean bellmanFord(int r) {
dis[r] = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < adjList.size(); j++) {
int st = adjList.get(j).start;
int ed = adjList.get(j).end;
long weight = adjList.get(j).weight;
if (dis[st] == INF)
continue;
if (dis[ed] > dis[st] + weight) {
dis[ed] = dis[st] + weight;
if (i == N - 1)
return false; // cycle
}
}
}
return true;
}
728x90
'CS > Algorithm' 카테고리의 다른 글
[알고리즘] 위상 정렬 Topological Sort (자바 Java) (1) | 2022.10.05 |
---|---|
[알고리즘] 유니온-파인드 (Union-Find) (자바 Java) (0) | 2022.09.29 |
[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) (자바/Java) (0) | 2022.09.28 |
[알고리즘] 최장 공통 부분 수열 (Longest Common Subsequence LCS) (0) | 2022.09.28 |
[알고리즘] 비트 연산자 & 부분집합 (자바/Java) (1) | 2022.09.19 |