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 }