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

[simonetripodi]

Author: simonetripodi
Date: Tue Jun 21 18:54:24 2011
New Revision: 1138135

URL: http://svn.apache.org/viewvc?rev=1138135&view=rev
Log:
as reported on wikipedia (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) 
"This [Dijkstra] is asymptotically the fastest known single-source 
shortest-path algorithm for arbitrary directed graphs with unbounded 
nonnegative weights"

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=1138135&r1=1138134&r2=1138135&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 21 18:54:24 2011
@@ -57,9 +57,9 @@ public final class Dijkstra
      * @return a path which describes the shortest path, if any,
      *         otherwise a {@link PathNotFoundException} will be thrown
      */
-    public static <V extends Vertex, WE extends WeightedEdge<V>> 
WeightedPath<V, WE> findShortestPath( WeightedGraph<V, WE> graph,
-                                                                               
                        V source,
-                                                                               
                        V target )
+    public static <V extends Vertex, WE extends WeightedEdge<V>, G extends 
WeightedGraph<V, WE> & DirectedGraph<V, WE>> WeightedPath<V, WE> 
findShortestPath( G graph,
+                                                                               
                                                                               
V source,
+                                                                               
                                                                               
V target )
     {
         final ShortestDistances<V> shortestDistances = new 
ShortestDistances<V>();
         shortestDistances.setWeight( source, 0D );
@@ -86,9 +86,7 @@ public final class Dijkstra
 
             settledNodes.add( vertex );
 
-            @SuppressWarnings( "unchecked" ) // graph type driven by input 
Graph instance
-            Set<WE> edges = ( graph instanceof DirectedGraph ) ? ( 
(DirectedGraph<V, WE>) graph ).getOutbound( vertex )
-                                                               : 
graph.getEdges( vertex );
+            Set<WE> edges = graph.getOutbound( vertex );
             for ( WE edge : edges )
             {
                 V v = getConnectedVertex( vertex, edge );