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