View Javadoc

1   package org.apache.commons.graph.shortestpath;
2   
3   /*
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *   http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing,
15   * software distributed under the License is distributed on an
16   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17   * KIND, either express or implied.  See the License for the
18   * specific language governing permissions and limitations
19   * under the License.
20   */
21  
22  import static java.lang.String.format;
23  
24  import java.util.HashMap;
25  import java.util.HashSet;
26  import java.util.Map;
27  import java.util.PriorityQueue;
28  import java.util.Set;
29  
30  import org.apache.commons.graph.Vertex;
31  import org.apache.commons.graph.WeightedEdge;
32  import org.apache.commons.graph.WeightedGraph;
33  import org.apache.commons.graph.WeightedPath;
34  import org.apache.commons.graph.model.InMemoryPath;
35  
36  /**
37   * 
38   */
39  public final class Dijkstra
40  {
41  
42      /**
43       * This class can not be instantiated directly
44       */
45      private Dijkstra()
46      {
47          // do nothing
48      }
49  
50      /**
51       * Applies the classical Dijkstra algorithm to find the shortest path from the source to the target, if exists.
52       *
53       * @param <V>
54       * @param <WE>
55       * @param graph
56       * @param source
57       * @param target
58       * @return
59       */
60      public static <V extends Vertex, WE extends WeightedEdge<V>> WeightedPath<V, WE> findShortestPath( WeightedGraph<V, WE> graph,
61                                                                                                         V source,
62                                                                                                         V target )
63      {
64          final ShortestDistances<V> shortestDistances = new ShortestDistances<V>();
65          shortestDistances.put( source, 0D );
66  
67          final PriorityQueue<V> unsettledNodes =
68              new PriorityQueue<V>( graph.getVertices().size(), shortestDistances );
69          unsettledNodes.add( source );
70  
71          final Set<V> settledNodes = new HashSet<V>();
72  
73          final Map<V, WE> predecessors = new HashMap<V, WE>();
74  
75          // the current node
76          V vertex;
77  
78          // extract the node with the shortest distance
79          while ( ( vertex = unsettledNodes.poll() ) != null )
80          {
81              // destination reached, stop and build the path
82              if ( target.equals( vertex ) )
83              {
84                  InMemoryPath<V, WE> path = new InMemoryPath<V, WE>( source, target, shortestDistances.get( target ) );
85  
86                  while ( !source.equals( vertex ) )
87                  {
88                      WE edge = predecessors.get( vertex );
89  
90                      path.addEdgeInHead( edge );
91                      path.addVertexInHead( vertex );
92  
93                      vertex = edge.getHead();
94                  }
95  
96                  return path;
97              }
98  
99              settledNodes.add( vertex );
100 
101             for ( WE edge : graph.getEdges( vertex ) )
102             {
103                 V v = edge.getTail();
104 
105                 // skip node already settled
106                 if ( !settledNodes.contains( v ) )
107                 {
108                     Double shortDist = shortestDistances.get( vertex ) + edge.getWeight();
109 
110                     if ( shortDist.compareTo( shortestDistances.get( v ) ) < 0 )
111                     {
112                         // assign new shortest distance and mark unsettled
113                         shortestDistances.put( v, shortDist );
114                         unsettledNodes.add( v );
115 
116                         // assign predecessor in shortest path
117                         predecessors.put( v, edge );
118                     }
119                 }
120             }
121         }
122 
123         throw new PathNotFoundException( format( "Path from '%s' to '%s' doesn't exist in Graph '%s'", source, target,
124                                                  graph ) );
125     }
126 
127 }