밸만 포드 알고리즘과 다이젝스트라 알고리즘
오늘 문제를 풀다가 밸만 포드 알고리즘을 공부하게 되었습니다.
그래서 벨만 포드 알고리즘을 사용하여 문제를 풀던 도중 저의 얇은 지식으로 인한 구현 오류에 대해 작성하기로 했습니다.
우선 다이젝스트라 알고리즘에 대해 간단하게 말하자면, 간선이 양수인 경우 특정 지점에서 다른 모든 지점까지의 거리를 구할 수 있는 알고리즘 입니다.
"노드 u에 대한 최단 거리의 예상 값은 = v까지의 최단 거리 + u와 v의 거리" 의 원리를 사용하여 최단거리를 구합니다.
최단거리의 예상 값인 이유는 u에 연결된 노드가 많을 수 있기 때문입니다. 이와 같은 비교는 우선순위 큐를 통해 쉽게 구현이 가능합니다.
public static int[] Dijkstra(List<List<Node>> map, int node,int start){
PriorityQueue<Node> pq = new PriorityQueue<>();
int[] dist = new int[node+1];
boolean[] vist = new boolean[node+1];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[start] = 0;
pq.add(new Node(start,0));
while(!pq.isEmpty()){
Node now = pq.poll();
if(vist[now.end]){
continue;
}
vist[now.end] = true;
for(Node nxt : map.get(now.end)){
if(dist[nxt.end]>dist[now.end]+nxt.cost){
dist[nxt.end]=dist[now.end]+nxt.cost;
pq.add(new Node(nxt.end,dist[now.end]+nxt.cost));
}
}
}
return dist;
}
다이젝스트라 알고리즘을 사용하며 "왜 visit 배열을 사용해야할까?" 라는 의문을 품은 적이 있습니다.
사실 없어도 결과는 나오긴합니다. 하지만 그렇게 사용하면 무덤에 계신 다익스트라 선생님과 우선순위 큐가 섭섭합니다.
간선이 양수라는 조건과 우선 순위 큐의 사용은, 최초 노드에 방문한 탐색은 항상 최소 거리를 의미합니다. 즉 한번 방문한 노드는 더 이상 볼 필요가 없는 것이죵.
이를 이용하여 저는 visit 배열말고 방문 노드의 수를 카운트하여 다익스트라를 구현한 적도 있습니다. 물론 모든 노드가 연결되어 있다는 조건이 선행되어야 합니다.
그렇다면 간선이 양수가 아닌 경우에는 밸만 포드만 알고리즘을 사용하여 최단 거리를 구합니다.
밸만 포드만 알고리즘은 크게 두 단계를 가지는데
1. 모든 정점(사실 모든 정점 -1개의 정점을 탐색)에 대해 모든 간선을 한 번씩 탐색
2. 모든 간선을 통해 최단거리 갱신 여부를 탐색
1번을 하는 이유가 무엇일까요? 저는 이것을 잘 이해하지 못했기 때문에 계속해서 문제를 틀렸습니다.
제가 처음에 한 생각은 "시작점이 존재 할때, 시작점을 기준으로 탐색하는 것으로 충분하지 않을까"입니다. 그리고 다익스트라 알고리즘을 살짝 변형했습니다.
while(!pq.isEmpty()){
Pair now = pq.poll();
for(Pair nxt : list.get(now.next)){
if(dist[nxt.next] > dist[now.next]+nxt.cost) dist[nxt.next] = dist[now.next]+ nxt.cost;
if(vis[nxt.next]) continue;
vis[nxt.next] = true;
pq.add(new Pair(nxt.next,dist[nxt.next]));
}
}
하지만 아까 우선순위큐를 사용하게 되어, " 최초 노드에 방문한 탐색은 항상 최소 거리" 라는 규칙이 간선이 음수가 가능한 경우 성립이 되지 않습니다.
위와 같은 경우, 4번 노드에 최초 방문되어 갱신한 최단 거리는 3이지만 그 값이 최단 거리가 아닙니다. 왜죠
그 이유는 간선이 음수가 가능하게되면서 1번에서 4번까지 가장 적은 비용을 갖더라도 "4번까지의 최단 거리 = 1번까지 거리(0) + 1,4의 거리"가 아니라 "4번까지의 최단거리 = 1,2 거리 + 2,3 거리 + 3,4 거리"가 될 수 있기 때문입니다.
즉 모든 노드에 대해 모든 간선을 다 확인해줘서 최단 거리를 구해야 합니다.
그렇게 계산한 최단 거리가 간선을 탐색을 한번 더 진행되 있을 때, 변경이 이뤄진다면 음수가 순환되는 것을 알 수 있습니다.
Long[] dist = new Long[n+1];
Arrays.fill(dist,Long.MAX_VALUE);
dist[1] = 0L;
boolean[] vis = new boolean[n+1];
vis[1] = true;
for(int i=1;i<n;i++){
for(int j=0;j<e;j++){
Pair now = list.get(j);
if(dist[now.now] != Long.MAX_VALUE && dist[now.next] > dist[now.now]+now.cost) dist[now.next] = dist[now.now]+now.cost;
}
}
boolean hasNegative = false;
// System.out.println(Arrays.toString(dist));
for(int i=0;i<e;i++){
Pair pair = list.get(i);
if (dist[pair.now] != Long.MAX_VALUE && dist[pair.next] > dist[pair.now] + pair.cost) {
hasNegative = true;
break;
}
}
+
그렇다면 음수가 순환되는 노드들의 집합을 어떻게 구할 수 있을까요?
이 부분은 좀 더 생각을 해봐야겠습니다.