svn commit: r1139375 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java

[simonetripodi]

Author: simonetripodi
Date: Fri Jun 24 16:30:39 2011
New Revision: 1139375

URL: http://svn.apache.org/viewvc?rev=1139375&view=rev
Log:
first (incomplete) implementation of Bellmann-Ford's algorithm

Modified:
    
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java

Modified: 
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
URL: 
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java?rev=1139375&r1=1139374&r2=1139375&view=diff
==============================================================================
--- 
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
 (original)
+++ 
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
 Fri Jun 24 16:30:39 2011
@@ -58,7 +58,36 @@ public final class BellmannFord
 
         final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, 
WE>();
 
-        
+        for ( WE edge : graph.getEdges() )
+        {
+            V u = edge.getHead();
+            V v = edge.getTail();
+
+            Double shortDist = shortestDistances.getWeight( u ) + 
edge.getWeight();
+
+            if ( shortDist.compareTo( shortestDistances.getWeight( v ) ) < 0 )
+            {
+                // assign new shortest distance and mark unsettled
+                shortestDistances.setWeight( v, shortDist );
+
+                // assign predecessor in shortest path
+                predecessors.addPredecessor( v, edge );
+            }
+        }
+
+        for ( WE edge : graph.getEdges() )
+        {
+            V u = edge.getHead();
+            V v = edge.getTail();
+
+            Double shortDist = shortestDistances.getWeight( u ) + 
edge.getWeight();
+
+            if ( shortDist.compareTo( shortestDistances.getWeight( v ) ) < 0 )
+            {
+                throw new NegativeWeightedCycleException( "A negative weighted 
cycle has been dected in vertex %s",
+                                                          v, graph );
+            }
+        }
 
         return null;
     }