Tracing the longest path using Bellman-Ford with negative edge weights.

Question

Hello All,

I'm currently finding the longest path in a directed acyclic positive-weighted graph by negating all edge weights and running Bellman Ford. This is working great. However, I'd like to print the trace of which nodes/edges were used. Any help? The program takes as input the number of nodes, a source, destination and edge weight. Input halts on -1 -1 -1. My code is as follows:

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<Edge> edges = new Vector<Edge>(); // 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<Edge> 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 < nnodes; ++i)
  // relax every edge in 'edges'
  for (int j = 0; j < 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 < distance[edges.get(j).destination])
    distance[edges.get(j).destination] = newDistance;
  }
 // next loop analyzes the graph for cycles
 for (int i = 0; i < 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] > 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 && distance[edges.get(i).destination] > 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 < 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]);
}

}

Answer 1

Embarrassingly, I've never implemented Bellman-Ford. However, Dijkstra's can be simply modified to return the actual path used as well as the cost, and your idea of negating weights to find the longest path should work just as well in it as it does in Bellman. I'd suggest taking a look at that if you haven't already.

Answer 2

You need to slightly modify what you do in the Bellman Ford implementation:

...
int[] lastNode = new int[nnodes];
lastNode[source] = source;
for (int i = 0; i < nnodes; ++i)
    for (int j = 0; j < edges.size(); ++j) {
        if (distance[edges.get(j).source] == INF) continue;
        int newDistance = distance[edges.get(j).source] + edges.get(j).weight;
        if (newDistance < distance[edges.get(j).destination])
        {
            distance[edges.get(j).destination] = newDistance;
            lastNode[edges.get(j).destination] = edges.get(j).source;
        }
    }

Printing individual paths then becomes:

static void printPath(int source, int end, int[] lastNodes)
{
    if(source!=end)
        printPath(source, lastNodes[end], lastNodes);
    System.out.print(end+" ");
}

Which prints the path in order from source node to end node.

Answer 3

The common solution for graph algorithms is to maintain parent[edge] -> edge mapping. For edge e the value of parent[e] is the node from which we traverse to e when we create a path optimal in some way.

The array is usually updated in the same way you update index in algorithm to find the largest element in the array, i.e. within if condition when you compare fitness of candidate path with that of current path.

In your case, it's here:

if (newDistance < distance[edges.get(j).destination]) {
   distance[edges.get(j).destination] = newDistance;
   parent[edges.get(j).destination] = edges.get(j).source;
}

After you comupted parent mapping, you may take destination node and traverse it back, recursively building an array [dest, parent[dest], parent[parent[dest]], ... source.