그래프에서 다시보는 너비 우선 탐색(BFS)
트리에서 봤던 너비 우선 탐색과 같음
원래는 그래프에서 사용 가능한 것이며 트리는 특별한 제약이 있는 그래프라고 칭할 수 있다
차이점으로는 방문한 노드를 기억해야 한다
public static void searchBreadthFirst(Node node) {
HashSet<Node> discovered = new HashSet<>();
Queue<Node> queue = new LinkedList<>();
queue.add(node);
discovered.add(node);
while (!queue.isEmpty()) {
Node next = queue.remove();
System.out.println(next.data + " ");
for (Node neighbor : next.neighbors) {
if (!discovered.contains(neighbor)) {
queue.add(neighbor);
discovered.add(next);
}
}
}
}최단 경로(SP : shortest path) 찾기
가장 간단한 방법은 주먹구구식
ㄴ 모든 가능한 조합을 만든 뒤, 그 중 가장 짧은 것을 선택
ㄴ 단 순환이 없게끔 해야 함
BFS 를 사용하면 최단 경로를 찾을 수 있음 시간복잡도 O(N + E)
BFS 증명 google : BFS shortest path proof
BFS 로 최단 경로 찾기
기본적인 BFS 와 크게 다르지 않음
시작점부터 현재 노드까지의 거리(BFS 깊이)를 기억
기억하는 방법으로 해시 맵(모든 노드 거리 저장), 2D 배, 각 노드 안에 거리 저장(리셋 필요)
저장법을 포함한 BFS
public static int findShortestDistance(Node s, Node d) {
HashMap<Node> distances = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
queue.add(s);
distances.put(s, 0);
while (!queue.isEmpty()) {
Node next = queue.remove();
int distance = distances.get(next);
if (next.equals(d)) {
return distance;
}
for (Node neighbor : next.neighbors) {
if (!distances.containsKey(neighbor)) {
queue.add(neighbor);
distances.put(neighbor, distance + 1);
}
}
}
return - 1
}다익스트라 알고리듬(Dijkstra's algorithm)
두 노드 사이의 최단 경로를 찾음
방대한 노드 네트워크에 사용하기 충분히 빠름
변의 가중치가 음수인 경우 제대로 작동하지 않음
지도/네비, IP 라우팅, 경유 항공편, 등...
동적 계획법
구조
1.아직 방문하지 않은 노드 중 가장 거리 값이 작은 노드 n 선택
2.n 의 각 미방문 이웃 m 으로 가는 더 짧은 경로가 있다면 업데이트
ㄴ min { 현재까지 알려진 m 의 거리, 현재까지 알려진 n 의 거리에 n 에서 m 까지 거리를 합한 것
3.다음 조건 중 하나를 만족하기 전까지 1~2 를 반복
ㄴ 모든 노드 방문, n = 목적지
4.목적지까지의 거리/경로 반환
시간 복잡도
방문하느 노드 수(알고리듬 실행 횟수) : N
ㄴ최소 거리 노드 선택하는 방법은 : Log N
모든 변을 한 번씩은 지나감 : E
ㄴ 거리 값 업데이터 : Log N
: O(N log N + E log N) = O((N + E) log N)
다익스트라 와 음의 가중치
음의 가중치가 있는 경우 방문한 노드를 재방문하여 최단 경로를 찾을 수 있는 경우
다익스트라 알고리듬은 한번 방문한 노드는 재방문하지 않기 때문에 사용할 수 없다
위와 같은 문제를 해결할 수 있는 알고리듬으로 벨만-포드 알고리듬이 따로 있다
코드
public class Node {
private final String name;
private final HashMap<Node, Integer> roads = new HashMap<>();
public Node(String name) {
this.name = name;
}
public String getName() {
return name;
}
public HashMap<Node, Integer> getRoads() {
return roads;
}
public void addRoad(final Node to, final int dist) {
this.roads.put(to, dist);
}
public int getDistance(final Node to) {
return this.roads.get(to);
}
}
public class Candidate implements Comparable<Candidate> {
private final Node node;
private final int distance;
public Candidate(final Node node, final int distance) {
this.node = node;
this.distance = distance;
}
public Node getNode() {
return node;
}
public int getDistance() {
return distance;
}
@Override
public int compareTo(Candidate o) {
return this.distance - o.distance;
}
}
public class Dijkstra {
private Dijkstra() {}
public static HashMap<String, Integer> run(final HashMap<String, Node> nodes, final String from, final HashMap<String, String> prevs) {
HashMap<String, Integer> minDists = new HashMap<>();
final int INF = Integer.MAX_VALUE;
for (var entry : nodes.entrySet()) {
String name = entry.getKey();
minDists.put(name, INF);
}
minDists.put(from, 0);
prevs.put(from, null);
PriorityQueue<Candidate> open = new PriorityQueue<>();
Node s = nodes.get(from);
Candidate candidate = new Candidate(s, 0);
open.add(candidate);
while (!open.isEmpty()) {
candidate = open.poll();
Node n = candidate.getNode();
String nodeName = n.getName();
int minDist = minDists.get(nodeName);
int dist = candidate.getDistance();
if (minDist < dist) {
continue;
}
Map<Node, Integer> roads = n.getRoads();
for (var e : roads.entrySet()) {
Node next = e.getKey();
int weight = e.getValue();
int newDist = minDist + weight;
String nextName = next.getName();
int nextMinDist = minDist.get(nextName);
if (newDist >= nextMinDist) {
continue;
}
minDists.put(nextName, newDist);
prevs.put(nextName, nodeName);
Candidate newCandidate = new Candidate(next, newDist);
open.add(newCandidate);
}
}
return minDists;
}
}A* 알고리듬
다익스트라와 기본은 같은 알고리듬
불필요한 노드 방문을 줄일 수 있다
다익스트라의 기준은 시작점 부터 노드까지
A(휴리스틱, 근사치) 는 노드로부터 목적지까지
휴리스틱 함수에 따라 A 성능이 달라짐
대부분의 경우 다익스트라 보다 빠름
같은 노드를 두 번 이상 방문할 수 있음
g(n) : 시작 노드부터 노드 n 까지의 거리 (실제 값, 다익스트라)
h(n) : n 부터 목적지 노드까지의 거리 (추정치, 휴리스틱)
h'(n) : 목적지로 이동하는 실제 비용
f(n) : 추정 함수 g(n) + h(n)
과정
1.그래프에 있는 모든 노드의 g(n), f(n) 무한대로 초기화, f(n) = g(n) + h(n) 바로 입력 가능
2.g(s) = 0, f(s) = h(s)
3.시작 노드 s 를 OPEN(다익스트라 예제 안의 PriorityQueue 인스턴스 변수) 에 추가
4.OPEN 에서 f(n) 이 가장 작은 노드를 찾아 제거
5.n 의 각 이웃 m 에 대해 시작점 -> n -> m 이 더 짧은 경로이면 g(m) 업데이트, m OPEN 에 추가
6.목적지에 도달하거나 OPEN 이 비워질 때 까지 4 ~ 5 반복
h(n) == 0
다익스트라 알고리듬과 똑같은 동작
h(n) <= h'(n)
추정 거리가 실제 거리 이하인 경우
언제나 이런 경우 A* 는 최단 거리를 찾음, 괜찮은 알고리듬 속도
그러나 하나라도 추정치가 큰 경우에 크게 돌아서 도착지에 도착할 수 있음
h(n) << h'(n)
추정 거리가 실제 거리보다 훨씬 작은 경우
A* 가 더 많은 경로를 탐색
따라서 탐색 범위가 넓어지고 속도가 느림
h(n) == h'(n)
추정 거리가 실제 거리와 같음
언제나 최고의 경로를 따라가며 알고리듬이 매우 빠름
A* 의 중복 방문 허용 이유
다익스트라는 새로 방문하는 노드의 실제 거리가 최소이므로 재방문이 필요 없음
A* 는 새로 방문하는 노드의 거리가 실제 거리가 아니고 h(n) 추정치가 포함 되며
다른 경로를 통해 재방문 시 거리가 작아질 수 있음
그러나 h(n) 이 특정 조건(h(n) <= dist(n, m) + h(m))을 만족하면 노드를 한 번씩 방문
플로이드 워셜 알고리듬
모든 쌍의 최단 거리를 찾는 알고리듬
인접 행렬(2D) 사용, 동적 계획법 알고리듬
그래프에 있는 노드를 1 ~ N 까지 번호를 매김
sp(i,j,k) : i -> j 의 최단 경로, 중간에 1 ~ k 노드를 거쳐도 됨
sp(i,j,k) 는 sp(i,j,k-1) 의 확장
sp(i,j,k-1) : 1 ~ k-1 노드를 거칠 수 있는 i -> j 최단 거리
sp(i,j,k) : sp(i,j,k-1) 에 추가적으로 k 노드도 거치는 경우도 고려
ㄴ 더 짧은 거리를 못찾음(기존 경로) : sp(i,j,k) = sp(i,j,k-1)
ㄴ 더 짧은 거리를 찾음(k 따라 이동) : sp(i,j,k) = sp(i,k,k-1) + sp(k,j,k-1)
