/home/nicola/Dropbox/Progetto SOL/CARS_terfram/src/shortestpath.h File Reference

definizione dei prototipi per il calcolo dei cammini minimi si grafo diretto More...

#include <stdio.h>
#include "dgraph.h"

Go to the source code of this file.

Defines
#define	INFINITY   (-1.0)
#define	UNDEF   ((unsigned int) -1)
Functions
double *	dijkstra (graph_t *g, unsigned int source, unsigned int **pprec)
char *	shpath_to_string (graph_t *g, unsigned int n1, unsigned int n2, unsigned int *prec)

---

Detailed Description

definizione dei prototipi per il calcolo dei cammini minimi si grafo diretto

Author:

lso11

---

Define Documentation

#define INFINITY   (-1.0)

infinito -- valore di distanza per l'output dell'algoritmo di Dijkstra

Referenced by dijkstra(), is_less(), and stampadist().

---

Function Documentation

double* dijkstra	(	graph_t *	g,
		unsigned int	source,
		unsigned int **	pprec
	)

implementa l'algoritmo di Dijkstra per la ricerca di tutti i cammini minimi a patire da un nodo sorgente

Parameters:

g	grafo pesato, con parametri non negativi
source	nodo da cui calcolare i cammini minimi
pprec	puntatore di puntatore: (1) se pprec != da NULL viene assegnato a *pprec il vettore dei predecessori definito come segue: per ogni nodo n1 pprec[n1] = n2 se n2 e' il nodo che precede n1 nel cammino minimo da source a n1 (2) se pprec == NULL il vettore non viene assegnato (non e' un errore)

Return values:

dist	puntatore al vettore delle distanze minime calcolate (se tutto e' andato bene )
NULL	se si \'e verificato un errore, setta errno

References node::adj, heap_array::array, decrease_key(), dequeue(), enqueue(), INFINITY, is_empty(), is_less(), edge::km, MALLOC_ERRNO, n_size(), and graph::node.

Referenced by appendReqOff(), and main().

char* shpath_to_string	(	graph_t *	g,
		unsigned int	n1,
		unsigned int	n2,
		unsigned int *	prec
	)

crea la stringa della rotta da n1 a n2 usando l'array delle precedenze calcolato da dijkstra

Parameters:

g
n1
n2
prec

Return values:

rotta	puntatore alla stringa che descrive la rotta se tutto e' andato bene rotta contiene tutte le citta attraversate separate da '$' n1$citta1$....$cittaN$n2 ad esempio rotta da PISA ad AREZZO PISA$LUCCA$PRATO$FIRENZE$AREZZO
NULL	se la rotta da n1 a n2 non esiste (errno == 0) e se si e' verificato un errore (errno != 0)

References node::label, LLABEL, MALLOC_ERRNO, n_size(), and graph::node.

Referenced by appendReqOff(), and calcola_e_stampa_rotte().