title: Tracing the longest path using Bellman-Ford with negative edge weights
body: <p>I'm currently finding the longest path in a directed acyclic positive-weighted graph by negating all edge weights and running Bellman-Ford algorithm. This is working great.</p>
  
  <p>However, I'd like to print the trace of which nodes/edges were used. How can I do that?</p>
  
  <p>The program takes as input the number of nodes, a source, destination and edge weight. Input halts on <code>-1 -1 -1</code>. My code is as follows:</p>
  
  <pre><code>import java.util.Arrays;
  import java.util.Vector;
  import java.util.Scanner;
  
  public class BellmanFord {
      public static int INF = Integer.MAX_VALUE;
  
      // this class represents an edge between two nodes
      static class Edge {
          int source; // source node
          int destination; // destination node
          int weight; // weight of the edge
          public Edge() {}; // default constructor
          public Edge(int s, int d, int w) { source = s; destination = d; weight = (w*(-1)); }
      }
  
      public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
          int inputgood = 1;
          int tail;
          int head;
          int weight;
          int count = -1;
          Vector&lt;Edge&gt; edges = new Vector&lt;Edge&gt;(); // data structure to hold graph
          int nnodes = input.nextInt();
          while (inputgood == 1) {
              tail = input.nextInt();
              head = input.nextInt();
              weight = input.nextInt();
  
              if (tail != -1) {
                  edges.add(new Edge(tail, head, weight));
                  count++;
              }
              if (tail == -1)
                  inputgood = 0;
          }
          int start = edges.get(0).source;
          bellmanFord(edges, nnodes, start);
      }
  
      public static void bellmanFord(Vector&lt;Edge&gt; edges, int nnodes, int source) {
          // the 'distance' array contains the distances from the main source to all other nodes
          int[] distance = new int[nnodes];
          // at the start - all distances are initiated to infinity
          Arrays.fill(distance, INF);
          // the distance from the main source to itself is 0
          distance[source] = 0;
          // in the next loop we run the relaxation 'nnodes' times to ensure that
          // we have found new distances for ALL nodes
          for (int i = 0; i &lt; nnodes; ++i)
              // relax every edge in 'edges'
              for (int j = 0; j &lt; edges.size(); ++j) {
                  // analyze the current edge (SOURCE == edges.get(j).source, DESTINATION == edges.get(j).destination):
                  // if the distance to the SOURCE node is equal to INF then there's no shorter path from our main source to DESTINATION through SOURCE
                  if (distance[edges.get(j).source] == INF) continue;
                  // newDistance represents the distance from our main source to DESTINATION through SOURCE (i.e. using current edge - 'edges.get(j)')
                  int newDistance = distance[edges.get(j).source] + edges.get(j).weight;
                  // if the newDistance is less than previous longest distance from our main source to DESTINATION
                  // then record that new longest distance from the main source to DESTINATION
                  if (newDistance &lt; distance[edges.get(j).destination])
                      distance[edges.get(j).destination] = newDistance;
              }
          // next loop analyzes the graph for cycles
          for (int i = 0; i &lt; edges.size(); ++i)
              // 'if (distance[edges.get(i).source] != INF)' means:
              // "
              //    if the distance from the main source node to the DESTINATION node is equal to infinity then there's no path between them
              // "
              // 'if (distance[edges.get(i).destination] &gt; distance[edges.get(i).source] + edges.get(i).weight)' says that there's a negative edge weight cycle in the graph
              if (distance[edges.get(i).source] != INF &amp;&amp; distance[edges.get(i).destination] &gt; distance[edges.get(i).source] + edges.get(i).weight) {
                  System.out.println("Cycles detected!");
                  return;
              }
          // this loop outputs the distances from the main source node to all other nodes of the graph
          for (int i = 0; i &lt; distance.length; ++i)
              if (distance[i] == INF)
                  System.out.println("There's no path between " + source + " and " + i);
              else
                  System.out.println("The Longest distance between nodes " + source + " and " + i + " is " + distance[i]);
      }
  }
  </code></pre>