// Java implementation of the Bellman-Ford algorithm // Initialize distance array and starting node's distance dist[start] = 0; // Loop v-1 times to relax edges for (int i = 0; i < v - 1; i++) { for (DirectedEdge edge : edges) { int u = edge.from; int v = edge.to; int weight = edge.cost; // Relax the edge if a shorter path is found if (dist[u] != Double.POSITIVE_INFINITY && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; } } } // Detect negative cycles by running the algorithm again for (int i = 0; i < v - 1; i++) { for (DirectedEdge edge : edges) { int u = edge.from; int v = edge.to; int weight = edge.cost; // Mark nodes involved in negative cycles if (dist[u] != Double.POSITIVE_INFINITY && dist[u] + weight < dist[v]) { dist[v] = Double.NEGATIVE_INFINITY; } } }