| 1 | /* |
| 2 | * $Id: DijkstraShortestPathFinder.java 5865 2005-10-25 21:02:06Z dfs $ |
| 3 | * |
| 4 | * Copyright 2004 Daniel F. Savarese |
| 5 | * Copyright 2005 Savarese Software Research |
| 6 | * |
| 7 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 8 | * you may not use this file except in compliance with the License. |
| 9 | * You may obtain a copy of the License at |
| 10 | * |
| 11 | * https://www.savarese.com/software/ApacheLicense-2.0 |
| 12 | * |
| 13 | * Unless required by applicable law or agreed to in writing, software |
| 14 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 15 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 16 | * See the License for the specific language governing permissions and |
| 17 | * limitations under the License. |
| 18 | */ |
| 19 | |
| 20 | package com.savarese.algorithms.graph; |
| 21 | |
| 22 | import java.util.*; |
| 23 | |
| 24 | /** |
| 25 | * The DijkstraShortestPathFinder class implements Dijkstra's |
| 26 | * algorithm, which solves the single source shortest paths problem. |
| 27 | * It finds all the shortest paths between a source vertex and every |
| 28 | * other vertex in a graph. |
| 29 | * |
| 30 | * @author <a href="https://www.savarese.com/">Daniel F. Savarese</a> |
| 31 | */ |
| 32 | |
| 33 | public class DijkstraShortestPathFinder<V, E extends Edge<V, Integer>> |
| 34 | implements SingleSourcePathFinder<V, Integer, E> |
| 35 | { |
| 36 | |
| 37 | public static final int INFINITY = Integer.MAX_VALUE; |
| 38 | |
| 39 | class PathData { |
| 40 | int _distance; |
| 41 | V _predecessor; |
| 42 | |
| 43 | PathData() { |
| 44 | this(INFINITY, null); |
| 45 | } |
| 46 | |
| 47 | PathData(int d, V p) { |
| 48 | _distance = d; |
| 49 | _predecessor = p; |
| 50 | } |
| 51 | } |
| 52 | |
| 53 | |
| 54 | class VertexComparator implements Comparator<V> { |
| 55 | public int compare(V o1, V o2) { |
| 56 | PathData p1 = __paths.get(o1); |
| 57 | PathData p2 = __paths.get(o2); |
| 58 | |
| 59 | if(p1._distance > p2._distance) |
| 60 | return 1; |
| 61 | else if(p1._distance == p2._distance) { |
| 62 | if(o1.equals(o2)) |
| 63 | return 0; |
| 64 | else |
| 65 | return (o1.hashCode() > o2.hashCode() ? 1 : -1); |
| 66 | } else |
| 67 | return -1; |
| 68 | } |
| 69 | } |
| 70 | |
| 71 | |
| 72 | class Solution implements SingleSourcePath<V, Integer> { |
| 73 | private HashMap<V, PathData> __paths; |
| 74 | private V __source; |
| 75 | |
| 76 | Solution(V source, HashMap<V, PathData> paths) { |
| 77 | __paths = paths; |
| 78 | __source = source; |
| 79 | } |
| 80 | |
| 81 | public V getSource() { |
| 82 | return __source; |
| 83 | } |
| 84 | |
| 85 | public Integer getDistance(V destination) { |
| 86 | PathData pd = __paths.get(destination); |
| 87 | |
| 88 | if(pd == null || pd._distance == INFINITY) |
| 89 | return null; |
| 90 | |
| 91 | return pd._distance; |
| 92 | } |
| 93 | |
| 94 | public void getPath(V destination, List<V> path) { |
| 95 | int size = path.size(); |
| 96 | |
| 97 | while(!__source.equals(destination)) { |
| 98 | PathData pd = __paths.get(destination); |
| 99 | |
| 100 | if(pd == null || destination == null) { |
| 101 | if(size == 0) |
| 102 | path.clear(); |
| 103 | else |
| 104 | for(int i = path.size() - 1; i >= size; --i) |
| 105 | path.remove(i); |
| 106 | return; |
| 107 | } |
| 108 | |
| 109 | path.add(size, destination); |
| 110 | destination = pd._predecessor; |
| 111 | } |
| 112 | |
| 113 | path.add(size, __source); |
| 114 | } |
| 115 | } |
| 116 | |
| 117 | |
| 118 | private HashMap<V, PathData> __paths; |
| 119 | private TreeSet<V> __queue; |
| 120 | |
| 121 | |
| 122 | public DijkstraShortestPathFinder() { |
| 123 | __paths = null; |
| 124 | __queue = new TreeSet<V>(new VertexComparator()); |
| 125 | } |
| 126 | |
| 127 | |
| 128 | private void __initPath(Graph<V, E> graph, V source) { |
| 129 | __paths = new HashMap<V, PathData>(); |
| 130 | |
| 131 | Iterator<V> vertices = graph.vertexSet().iterator(); |
| 132 | |
| 133 | while(vertices.hasNext()) { |
| 134 | V v = vertices.next(); |
| 135 | __paths.put(v, new PathData()); |
| 136 | __queue.add(v); |
| 137 | } |
| 138 | |
| 139 | PathData data = __paths.get(source); |
| 140 | __queue.remove(source); |
| 141 | data._distance = 0; |
| 142 | } |
| 143 | |
| 144 | |
| 145 | private void __relax(E e) { |
| 146 | V src = e.getSource(); |
| 147 | V dest = e.getDestination(); |
| 148 | |
| 149 | PathData destData = __paths.get(dest); |
| 150 | PathData srcData = __paths.get(src); |
| 151 | |
| 152 | int distance = srcData._distance + e.getWeight(); |
| 153 | |
| 154 | // distance >= 0 guards against overflow. |
| 155 | if(destData._distance > distance && distance >= 0) { |
| 156 | boolean add = __queue.remove(dest); |
| 157 | |
| 158 | destData._distance = distance; |
| 159 | destData._predecessor = src; |
| 160 | |
| 161 | // reorder queue |
| 162 | if(add) |
| 163 | __queue.add(dest); |
| 164 | } |
| 165 | } |
| 166 | |
| 167 | |
| 168 | /** |
| 169 | * Finds all the shortest paths in the given graph between the given |
| 170 | * source vertex and all other vertices in the graph. |
| 171 | * |
| 172 | * @param graph The graph to be searched. |
| 173 | * @param source The source vertex from which all paths will emanate. |
| 174 | * @return The paths found. |
| 175 | */ |
| 176 | public SingleSourcePath<V, Integer> |
| 177 | findPath(Graph<V, E> graph, V source) |
| 178 | { |
| 179 | __initPath(graph, source); |
| 180 | |
| 181 | V vertex = source; |
| 182 | |
| 183 | while(__queue.size() > 0) { |
| 184 | Iterator<E> edges = graph.edgeSet(vertex).iterator(); |
| 185 | |
| 186 | while(edges.hasNext()) |
| 187 | __relax(edges.next()); |
| 188 | |
| 189 | vertex = __queue.first(); |
| 190 | __queue.remove(vertex); |
| 191 | } |
| 192 | |
| 193 | __queue.clear(); |
| 194 | |
| 195 | Solution result = new Solution(source, __paths); |
| 196 | __paths = null; |
| 197 | |
| 198 | return result; |
| 199 | } |
| 200 | |
| 201 | } |
