0 Replies Latest reply: Dec 5, 2009 8:23 PM by 843853 RSS

    Bellman Ford Algorithm

    843853
      Hello everyone,

      I've been looking into using the Bellman Ford algorithm that I found on the website here:

      http://forums.sun.com/thread.jspa?threadID=783463

      I'm wondering what I need to add to this so that the output also prints out the cost from every node to its neighboring node along the shortest path. So currently it prints out the shortest cost between two nodes, and I would like it to tell me the individual costs along the way that add up to that total. Can someone help me out with this?

      Thank you,

      raiderleaf
      package shortest_path;
       
      import java.util.Arrays;
      import java.util.Vector;
       
      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; }
           }
           
           public static void main(String[] args) {
                Vector<Edge> edges = new Vector<Edge>(); // a sample vector of edges of some graph
                edges.add(new Edge(0, 1, 5));
                edges.add(new Edge(0, 2, 8));
                edges.add(new Edge(0, 3, -4));
                edges.add(new Edge(1, 0, -2));
                edges.add(new Edge(2, 1, -3));
                edges.add(new Edge(2, 3, 9));
                edges.add(new Edge(3, 1, 7));
                edges.add(new Edge(3, 4, 2));
                edges.add(new Edge(4, 0, 6));
                edges.add(new Edge(4, 2, 7));
                bellmanFord(edges, 5, 4);
           }
           
           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 shortest distance from our main source to DESTINATION
                          // then record that new shortest 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("Negative edge weight 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 shortest distance between nodes " + source + " and " + i + " is " + distance);
           }
      }