Databases
StackOverflow2013
Postsdbo
POTracing the longest path using Bellman-Ford with negative edge weights
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTracing the longest path using Bellman-Ford with negative edge weights
    text
    copied!<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>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload