V
- il tipo delle etichette dei nodi del grafoE
- il tipo delle etichette degli archi del grafopublic class DijkstraShortestPathComputer<V,E>
extends java.lang.Object
O(n^2)
dove n
è il numero dei nodi del grafo.Constructor and Description |
---|
DijkstraShortestPathComputer(Graph<V,E> graph)
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(GraphNode<V> sourceNode)
Inizializza le informazioni necessarie associate ai nodi del grafo
associato a questo calcolatore ed esegue l'algoritmo di Dijkstra sul
grafo.
|
Graph<V,E> |
getGraph()
Restituisce il grafo su cui opera questo calcolatore.
|
GraphNode<V> |
getLastSource()
Restituisce il nodo sorgente specificato nell'ultima chiamata effettuata
a
computeShortestPathsFrom(GraphNode<V>) . |
java.util.List<GraphEdge<V,E>> |
getShortestPathTo(GraphNode<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.
|
java.lang.String |
printPath(java.util.List<GraphEdge<V,E>> path)
Genera una stringa di descrizione di un path riportando i nodi
attraversati e i pesi degli archi.
|
public DijkstraShortestPathComputer(Graph<V,E> graph)
graph
- il grafo su cui opera il calcolatore di cammini minimijava.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(GraphNode<V> sourceNode)
sourceNode
- il nodo sorgente da cui calcolare i cammini minimi
verso tutti gli altri nodi del grafojava.lang.NullPointerException
- se il nodo passato è nullojava.lang.IllegalArgumentException
- se il nodo passato non esiste nel grafo
associato a questo calcolatorepublic boolean isComputed()
public GraphNode<V> getLastSource()
computeShortestPathsFrom(GraphNode<V>)
.java.lang.IllegalStateException
- se non è stato eseguito nemmeno una volta il
calcolo dei cammini minimi a partire da un nodo sorgentepublic Graph<V,E> getGraph()
public java.util.List<GraphEdge<V,E>> getShortestPathTo(GraphNode<V> targetNode)
targetNode
- il nodo verso cui restituire il cammino minimo
dalla sorgentenull
se il nodo passato non è raggiungibile dalla
sorgentejava.lang.NullPointerException
- se il nodo passato è nullojava.lang.IllegalArgumentException
- se il nodo passato non esistejava.lang.IllegalStateException
- se non è stato eseguito nemmeno una volta il
calcolo dei cammini minimi a partire da un nodo sorgentepublic java.lang.String printPath(java.util.List<GraphEdge<V,E>> path)
"[ ]"
.path
- un cammino minimojava.lang.NullPointerException
- se il cammino passato è nullo