java - Bellman Ford detecting negative cycle of shortest length -

java - Bellman Ford detecting negative cycle of shortest length -

solving arbitage problem of uva http://uva.onlinejudge.org/index.php?option=com_onlinejudge&itemid=8&page=show_problem&problem=40 stuck finding negative cycle of shortest length(length here number of vertices).here code detects negative cycle

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]; (int = 0; < 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; (int = 1; < n + 1; i++) { string[] line = reader.readline().split("\\s+"); (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 edges 1 time more boolean brk = true; (int = 0; < cost.length && brk; i++) { (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)); (int = path.size() - 1; >= 0; --i) { system.out.println(path.get(i)); } } } reader.close(); } public static boolean bellmanford(int n, double[][] cost, double[] sp, int[] parent) { (int k = 0; k < n - 1; k++) { (int = 0; < cost.length; i++) { (int j = 0; j < cost.length; j++) { relax(i, j, sp, cost[i][j], parent); } } } // relax edges 1 time more observe cycle (int = 0; < cost.length; i++) { (int j = 0; j < cost.length; j++) { if (sp[j] > (sp[i] + cost[i][j])) { homecoming false; } } } homecoming 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 " + + " " + j + " " + cij + " " + sp[i] + " " + sp[j]); parent[j] = i; } } static void display(double[][] cost) { system.out.println("display cost"); (int = 0; < cost.length; i++) { (int j = 0; j < cost.length; j++) { system.out.print(cost[i][j] + "\t"); } system.out.println(); } } static void display(double[] sp) { (int = 0; < sp.length; i++) { system.out.println(sp[i]); } } }

you can that:

fix start vertex of cycle(let's phone call v).

run ford-bellman algorithm assuming dist[i] = 0 if = v , inf otherwise.

if there negative cycle contains v, after k iterations of outer loop in ford-bellman algorithm dist[v] become negative. can find such smallest k checking if dist[v] still non-negative or not after each iteration.

the smallest k among v answer.

java algorithm graph dynamic-programming bellman-ford