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

[si...@apache.org]

Author: simonetripodi
Date: Tue Jun 14 23:14:27 2011
New Revision: 1135843

URL: http://svn.apache.org/viewvc?rev=1135843&view=rev
Log:
Path rebuilt traversing bottom-up the predecessors map (it stores Edges so it makes it easier building both Vertices/Edges lists)

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

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java?rev=1135843&r1=1135842&r2=1135843&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java Tue Jun 14 23:14:27 2011
@@ -68,7 +68,7 @@ public final class Dijkstra
 
         final Set<V> settledNodes = new HashSet<V>();
 
-        final Map<V, V> predecessors = new HashMap<V, V>();
+        final Map<V, WE> predecessors = new HashMap<V, WE>();
 
         // the current node
         V vertex;
@@ -78,11 +78,23 @@ public final class Dijkstra
         {
             assert !settledNodes.contains( vertex );
 
-            // destination reached, stop
+            // destination reached, stop and build the path
             if ( target == vertex )
             {
-                // TODO return a WeightedPath instance
-                break;
+                InMemoryPath<V, WE> path = new InMemoryPath<V, WE>( source, target, shortestDistances.get( target ) );
+
+                V v = target;
+                while ( v != source )
+                {
+                    WE edge = predecessors.get( v );
+
+                    path.addEdgeInHead( edge );
+                    path.addVertexInHead( v );
+
+                    v = edge.getHead();
+                }
+
+                return path;
             }
 
             settledNodes.add( vertex );
@@ -103,7 +115,7 @@ public final class Dijkstra
                         unsettledNodes.add( v );
 
                         // assign predecessor in shortest path
-                        predecessors.put( v, vertex );
+                        predecessors.put( v, edge );
                     }
                 }
             }