V
- il tipo delle etichette dei nodi del grafoE
- il tipo delle etichette degli archi del grafopublic class PriorityQueueDijkstraShortestPathComputer<V extends PriorityQueueElement,E> extends java.lang.Object implements SingleSourceShortestPathComputer<V,E>
O(n log m)
dove n
è il numero di
nodi del grafo e m
è il numero di archi. Tuttavia, se la coda con
priorità è realizzata con uno heap di Fibonacci, si ottiene un tempo di
esecuzione O((n log n) + m)
.Constructor and Description |
---|
PriorityQueueDijkstraShortestPathComputer(Graph<V,E> graph,
MinPriorityQueue<V> queue)
Crea un calcolatore di cammini minimi a sorgente singola per un grafo
diretto e pesato privo di pesi negativi.
|
Modifier and Type | Method and Description |
---|---|
void |
computeShortestPathsFrom(PriorityGraphNode<V> sourceNode)
Inizializza le informazioni necessarie associate ai nodi del grafo
associato a questo calcolatore ed esegue un algoritmo per il calcolo dei
cammini minimi a partire da una sorgente data.
|
Graph<V,E> |
getGraph()
Restituisce il grafo su cui opera questo calcolatore.
|
PriorityGraphNode<V> |
getLastSource()
Restituisce il nodo sorgente specificato nell'ultima chiamata effettuata
a
computeShortestPathsFrom(GraphNode<V>) . |
java.util.List<GraphEdge<V,E>> |
getShortestPathTo(PriorityGraphNode<V> targetNode)
Restituisce una lista di archi dal nodo sorgente dell'ultimo calcolo di
cammini minimi al nodo passato.
|
boolean |
isComputed()
Determina se è stata invocata almeno una volta la procedura di calcolo
dei cammini minimi a partire da un certo nodo sorgente specificato.
|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
printPath
public PriorityQueueDijkstraShortestPathComputer(Graph<V,E> graph, MinPriorityQueue<V> queue)
graph
- il grafo su cui opera il calcolatore di cammini minimiqueue
- la coda con priorità in cui inserire ed estrarre i nodi
durante l'esecuzione dell'algoritmo.java.lang.NullPointerException
- se il grafo passato è nullojava.lang.IllegalArgumentException
- se il grafo passato è vuotojava.lang.IllegalArgumentException
- se il grafo passato non è direttojava.lang.IllegalArgumentException
- se il grafo passato non è pesato,
cioè esiste almeno un arco il cui
peso è Double.NaN
.java.lang.IllegalArgumentException
- se il grafo passato contiene almeno
un peso negativo.public void computeShortestPathsFrom(PriorityGraphNode<V> sourceNode)
SingleSourceShortestPathComputer
computeShortestPathsFrom
in interface SingleSourceShortestPathComputer<V extends PriorityQueueElement,E>
sourceNode
- il nodo sorgente da cui calcolare i cammini minimi
verso tutti gli altri nodi del grafopublic boolean isComputed()
SingleSourceShortestPathComputer
isComputed
in interface SingleSourceShortestPathComputer<V extends PriorityQueueElement,E>
public PriorityGraphNode<V> getLastSource()
SingleSourceShortestPathComputer
computeShortestPathsFrom(GraphNode<V>)
.getLastSource
in interface SingleSourceShortestPathComputer<V extends PriorityQueueElement,E>
public Graph<V,E> getGraph()
SingleSourceShortestPathComputer
getGraph
in interface SingleSourceShortestPathComputer<V extends PriorityQueueElement,E>
public java.util.List<GraphEdge<V,E>> getShortestPathTo(PriorityGraphNode<V> targetNode)
SingleSourceShortestPathComputer
getShortestPathTo
in interface SingleSourceShortestPathComputer<V extends PriorityQueueElement,E>
targetNode
- il nodo verso cui restituire il cammino minimo
dalla sorgentenull
se il nodo passato non è raggiungibile dalla
sorgente