commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1139375 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
Date Fri, 24 Jun 2011 16:30:40 GMT
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;
     }



Mime
View raw message