2
UVA http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=40의이 Arbitage 문제를 해결했지만 가장 짧은 길이의 부정적인 사이클 (여기 길이는 정점의 수)을 찾지 못했습니다. 여기에 부정 사이클을 성공적으로 감지하는 코드가 있습니다.Bellman Ford가 최단 길이의 음수 사이클을 감지 함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class _104 {
public static void main(String[] args) throws NumberFormatException,
IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
String input;
while ((input = reader.readLine()) != null) {
int n = Integer.parseInt(input);
double[][] cost = new double[n + 1][n + 1];
double[] spEstimate = new double[n + 1];
int parent[] = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
spEstimate[i] = Double.MAX_VALUE;
cost[0][i] = 0;
cost[i][0] = Double.MAX_VALUE;
parent[i] = Integer.MAX_VALUE;
}
spEstimate[0] = 0.0;
parent[0] = 0;
for (int i = 1; i < n + 1; i++) {
String[] line = reader.readLine().split("\\s+");
for (int j = 1; j < n + 1; j++) {
if (i == j) {
cost[i][j] = 0;
} else if (i < j) {
cost[i][j] = -(Math
.log(Double.parseDouble(line[j - 2]))/Math
.log(2));
} else {
cost[i][j] = -(Math
.log(Double.parseDouble(line[j - 1]))/Math
.log(2));
}
}
}
int save = 1, s = 1;
boolean flag = BellmanFord(n, cost, spEstimate, parent);
display(cost);
// Relax all edges once more
boolean brk = true;
for (int i = 0; i < cost.length && brk; i++) {
for (int j = 0; j < cost.length && brk; j++) {
//relax(i, j, spEstimate, cost[i][j], parent);
}
}
ArrayList<Integer> path = new ArrayList<Integer>();
while (parent[save] != s) {
path.add(save);
save = parent[save];
}
if (flag) {
System.out.println("no arbitrage sequence exists");
} else {
path.add(0, path.get(path.size() - 1));
for (int i = path.size() - 1; i >= 0; --i) {
System.out.println(path.get(i));
}
}
}
reader.close();
}
public static boolean BellmanFord(int n, double[][] cost, double[] sp,
int[] parent) {
for (int k = 0; k < n - 1; k++) {
for (int i = 0; i < cost.length; i++) {
for (int j = 0; j < cost.length; j++) {
relax(i, j, sp, cost[i][j], parent);
}
}
}
// Relax all edges once more to detect cycle
for (int i = 0; i < cost.length; i++) {
for (int j = 0; j < cost.length; j++) {
if (sp[j] > (sp[i] + cost[i][j])) {
return false;
}
}
}
return true;
}
static void relax(int i, int j, double[] sp, double cij, int[] parent) {
if (sp[j] > (sp[i] + cij)) {
sp[j] = sp[i] + cij;
System.out.println("relaxed " + i + " " + j + " " + cij + " "
+ sp[i] + " " + sp[j]);
parent[j] = i;
}
}
static void display(double[][] cost) {
System.out.println("Display Cost");
for (int i = 0; i < cost.length; i++) {
for (int j = 0; j < cost.length; j++) {
System.out.print(cost[i][j] + "\t");
}
System.out.println();
}
}
static void display(double[] sp) {
for (int i = 0; i < sp.length; i++) {
System.out.println(sp[i]);
}
}
}