001 package org.apache.commons.graph.shortestpath;
002
003 /*
004 * Licensed to the Apache Software Foundation (ASF) under one
005 * or more contributor license agreements. See the NOTICE file
006 * distributed with this work for additional information
007 * regarding copyright ownership. The ASF licenses this file
008 * to you under the Apache License, Version 2.0 (the
009 * "License"); you may not use this file except in compliance
010 * with the License. You may obtain a copy of the License at
011 *
012 * http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing,
015 * software distributed under the License is distributed on an
016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
017 * KIND, either express or implied. See the License for the
018 * specific language governing permissions and limitations
019 * under the License.
020 */
021
022 import static java.lang.String.format;
023
024 import java.util.HashMap;
025 import java.util.HashSet;
026 import java.util.Map;
027 import java.util.PriorityQueue;
028 import java.util.Set;
029
030 import org.apache.commons.graph.Vertex;
031 import org.apache.commons.graph.WeightedEdge;
032 import org.apache.commons.graph.WeightedGraph;
033 import org.apache.commons.graph.WeightedPath;
034 import org.apache.commons.graph.model.InMemoryPath;
035
036 /**
037 *
038 */
039 public final class Dijkstra
040 {
041
042 /**
043 * This class can not be instantiated directly
044 */
045 private Dijkstra()
046 {
047 // do nothing
048 }
049
050 /**
051 * Applies the classical Dijkstra algorithm to find the shortest path from the source to the target, if exists.
052 *
053 * @param <V>
054 * @param <WE>
055 * @param graph
056 * @param source
057 * @param target
058 * @return
059 */
060 public static <V extends Vertex, WE extends WeightedEdge<V>> WeightedPath<V, WE> findShortestPath( WeightedGraph<V, WE> graph,
061 V source,
062 V target )
063 {
064 final ShortestDistances<V> shortestDistances = new ShortestDistances<V>();
065 shortestDistances.put( source, 0D );
066
067 final PriorityQueue<V> unsettledNodes =
068 new PriorityQueue<V>( graph.getVertices().size(), shortestDistances );
069 unsettledNodes.add( source );
070
071 final Set<V> settledNodes = new HashSet<V>();
072
073 final Map<V, WE> predecessors = new HashMap<V, WE>();
074
075 // the current node
076 V vertex;
077
078 // extract the node with the shortest distance
079 while ( ( vertex = unsettledNodes.poll() ) != null )
080 {
081 // destination reached, stop and build the path
082 if ( target.equals( vertex ) )
083 {
084 InMemoryPath<V, WE> path = new InMemoryPath<V, WE>( source, target, shortestDistances.get( target ) );
085
086 while ( !source.equals( vertex ) )
087 {
088 WE edge = predecessors.get( vertex );
089
090 path.addEdgeInHead( edge );
091 path.addVertexInHead( vertex );
092
093 vertex = edge.getHead();
094 }
095
096 return path;
097 }
098
099 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 }