문제
- 음의 가중치를 갖는 문제이다.
양의 가중치만 있는 다익스트라와 달리, 다른 방법을 도입해야한다.
- 그 방법으로는 벨만포드가 있는데, 벨만포드는 O(VE)의 시간복잡도를 가진다.
(개선된 다익스트라는 PriorityQueue를 사용하기 때문에, O(E log V) 정도밖에 안가짐.)
벨만포드는 그러므로 모든 간선을 살펴보기 때문에 음의 가중치를 반영할 수 있다.
해결방향성
- 우선 벨만포드 알고리즘을 사용하기위해 기존의 Vertex 클래스 대신에, Edge클래스를 선언한다. 그 원소로는 start, end, weight를 둔다.
- 또한, 그래프를 그릴때도, 기존의 두개의 ArrayList를 선언했던것과 다르게, ArrayList를 하나만 선언하고, 원소는 Edge로 둔다.
(벨만포드는 간선을 중점으로 생각한다.)
이 문제는 또한 최단경로를 구하기위해 int[] 배열이 아닌 long[] 배열을 사용해야한다.
(사실, 변수 범위에 해당하는 맥시멈 값을 조절하는 방법을 찾는데 나도 애를 먹고있기때문에, 더 공부가 필요하다.)
- 마지막으로 함수는, boolean으로 선언해서 음의 순환이 포함되는지 여부를 확인하는게 좋다.
- 아 그리고, 진짜 마지막으로 반복문중 V번째 반복시, 최단경로가 변경된다면, 음의 순환이 존재하는것이다. (그때, return.)
코드
import java.io.*;
import java.util.*;
class Edge{
private int start;
private int end;
private int weight;
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
public int getWeight() {
return weight;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
ArrayList<Edge> graph = new ArrayList<>();
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
graph.add(new Edge(start, end, weight));
}
long[] minway = new long[V + 1];
Arrays.fill(minway, INF);
boolean isNegativeCycle = BelmanFord(graph, minway, V, E);
for (int i = 2; i <= V; i++) {
if (isNegativeCycle) {
bw.write(String.valueOf(-1) + "\n");
break;
} else if (minway[i] == INF) {
bw.write(String.valueOf(-1) + "\n");
} else {
bw.write(String.valueOf(minway[i]) + "\n");
}
}
bw.flush();
br.close();
bw.close();
}
private static int INF = 60_000_000;
private static boolean BelmanFord(ArrayList<Edge> graph, long[] minway, int V, int E) {
minway[1] = 0;
for (int i = 1; i <= V; i++) {
for (int j = 0; j < E; j++) {
Edge edge = graph.get(j);
int edgeStart = edge.getStart();
int edgeEnd = edge.getEnd();
int edgeWeight = edge.getWeight();
if (minway[edgeStart] != INF && (edgeWeight + minway[edgeStart] < minway[edgeEnd])) {
minway[edgeEnd] = minway[edgeStart] + edgeWeight;
if (i == V) {
return true;
}
}
}
}
return false;
}
}
결론
- 벨만포드 알고리즘은 최단경로 초기화에 사용된 INF 값을 포함하여 갱신하면 안된다. 음의 가중치가 포함되어있어, INF - 1이되면, 조건에 벗어나 그대로 값이 출력되기때문에, 이것도, 조건에 포함시킨다.
(기존의 visited배열이 사라진 대신에 이런 조건이 포함된다 생각해도 뭐... 외우기 무방하다.)
- 시간 복잡도가 O(VE)이므로 외워두면 알고리즘 짜기 편리하다.
- 또한, visited 배열이 없어서 전부 확인한다는 것도 다시 반복해서 알아두자.
- 현재 다익스트라, 벨만 포드 모두 맥시멈 범위를 조절하느라 애먹고있다. 어떻게 하면 범위를 잘 조절할수있을지 문제를 계속 풀어보자.