001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.algorithms.graph.sssp; 018 019import java.util.ArrayList; 020import java.util.Collections; 021import java.util.List; 022 023import net.automatalib.algorithms.graph.GraphAlgorithms; 024import net.automatalib.commons.smartcollections.BinaryHeap; 025import net.automatalib.commons.smartcollections.ElementReference; 026import net.automatalib.commons.smartcollections.SmartDynamicPriorityQueue; 027import net.automatalib.commons.util.mappings.MutableMapping; 028import net.automatalib.graphs.Graph; 029import net.automatalib.graphs.concepts.EdgeWeights; 030 031 032/** 033 * Implementation of Dijkstras algorithm for the single-source shortest path 034 * problem. 035 * 036 * @author Malte Isberner <malte.isberner@gmail.com> 037 * 038 * @param <N> node class 039 * @param <E> edge class 040 */ 041public class DijkstraSSSP<N,E> implements SSSPResult<N,E> { 042 043 /* 044 * Internal data record 045 */ 046 private static final class Record<N,E> implements Comparable<Record<N,E>> { 047 public final N node; 048 public float dist; 049 public ElementReference ref; 050 public E reach; 051 public Record<N,E> parent; 052 int depth; 053 054 055 public Record(N node, float dist) { 056 this(node, dist, null, null); 057 } 058 059 public Record(N node, float dist, E reach, Record<N,E> parent) { 060 this.node = node; 061 this.dist = dist; 062 this.reach = reach; 063 this.parent = parent; 064 this.depth = (parent != null) ? parent.depth + 1 : 0; 065 } 066 067 @Override 068 public int compareTo(Record<N, E> o) { 069 if(dist < o.dist) 070 return -1; 071 return (dist == o.dist) ? 0 : 1; 072 } 073 } 074 075 /** 076 * Search for the shortest paths from a single source node in a graph. 077 * 078 * @param graph the graph in which to perform the search 079 * @param init the initial (source) node 080 * @param edgeWeights the edge weights 081 * @return the single-source shortest path results 082 */ 083 public static <N,E> SSSPResult<N,E> findSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights) { 084 DijkstraSSSP<N, E> dijkstra = new DijkstraSSSP<N, E>(graph, init, edgeWeights); 085 dijkstra.findSSSP(); 086 return dijkstra; 087 } 088 089 private final Graph<N,E> graph; 090 private final N init; 091 private final EdgeWeights<E> edgeWeights; 092 private final MutableMapping<N,Record<N,E>> records; 093 094 /** 095 * Constructor. 096 * @param graph the graph in which to search for shortest paths 097 * @param init the initial node 098 * @param edgeWeights the edge weights 099 */ 100 public DijkstraSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights) { 101 this.graph = graph; 102 this.init = init; 103 this.edgeWeights = edgeWeights; 104 this.records = graph.createStaticNodeMapping(); 105 } 106 107 108 /** 109 * Start the search. This method may only be invoked once. 110 */ 111 public void findSSSP() { 112 Record<N,E> initRec = new Record<>(init, 0.0f); 113 if(records.put(init, initRec) != null) 114 throw new IllegalStateException("Search has already been performed!"); 115 116 SmartDynamicPriorityQueue<Record<N,E>> pq = BinaryHeap.create(graph.size()); 117 initRec.ref = pq.referencedAdd(initRec); 118 119 while(!pq.isEmpty()) { 120 // Remove node with minimum distance 121 Record<N,E> rec = pq.extractMin(); 122 float dist = rec.dist; 123 124 N node = rec.node; 125 126 // edge scanning 127 for(E edge : graph.getOutgoingEdges(node)) { 128 float w = edgeWeights.getEdgeWeight(edge); 129 float newDist = dist + w; 130 131 N tgt = graph.getTarget(edge); 132 Record<N,E> tgtRec = records.get(tgt); 133 if(tgtRec == null) { 134 // node has not been visited before, add a record 135 // and add it to the queue 136 tgtRec = new Record<>(tgt, newDist, edge, rec); 137 tgtRec.ref = pq.referencedAdd(tgtRec); 138 records.put(tgt, tgtRec); 139 } 140 else if(newDist < tgtRec.dist) { 141 // using currently considered edge decreases current distance 142 tgtRec.dist = newDist; 143 tgtRec.reach = edge; 144 tgtRec.depth = rec.depth + 1; 145 tgtRec.parent = rec; 146 // update it's position in the queue 147 pq.keyChanged(tgtRec.ref); 148 } 149 } 150 } 151 } 152 153 /* 154 * (non-Javadoc) 155 * @see net.automatalib.algorithms.graph.sssp.SSSPResult#getShortestPathDistance(java.lang.Object) 156 */ 157 @Override 158 public float getShortestPathDistance(N target) { 159 Record<N,E> rec = records.get(target); 160 if(rec == null) 161 return GraphAlgorithms.INVALID_DISTANCE; 162 return rec.dist; 163 } 164 165 /* 166 * (non-Javadoc) 167 * @see net.automatalib.algorithms.graph.sssp.SSSPResult#getShortestPath(java.lang.Object) 168 */ 169 @Override 170 public List<E> getShortestPath(N target) { 171 Record<N,E> rec = records.get(target); 172 if(rec == null) 173 return null; 174 175 if(rec.depth == 0) 176 return Collections.emptyList(); 177 178 List<E> result = new ArrayList<>(rec.depth); 179 180 E edge; 181 while((edge = rec.reach) != null) { 182 result.add(edge); 183 rec = rec.parent; 184 } 185 186 Collections.reverse(result); 187 return result; 188 } 189 190 /* 191 * (non-Javadoc) 192 * @see net.automatalib.algorithms.graph.sssp.SSSPResult#getInitialNode() 193 */ 194 @Override 195 public N getInitialNode() { 196 return init; 197 } 198 199 /* 200 * (non-Javadoc) 201 * @see net.automatalib.algorithms.graph.sssp.SSSPResult#getShortestPathEdge(java.lang.Object) 202 */ 203 @Override 204 public E getShortestPathEdge(N target) { 205 Record<N,E> rec = records.get(target); 206 if(rec == null) 207 return null; 208 return rec.reach; 209 } 210}