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

Implementazione delle funzioni definite in shortestpath.h. More...

#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include "shortestpath.h"
#include "macros.h"
#include "heap.h"

Functions
static int	is_less (double a, double b)
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

Implementazione delle funzioni definite in shortestpath.h.

Author:

Nicola Corti Si dichiara che il contenuto di questo file e' in ogni sua parte opera originale dell' autore.

---

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().

static int is_less	(	double	a,
		double	b
	)		[static]

Funzione static che effettua un confronto fra 2 valori, considerando il valore INFINITY come infinito

Parameters:

[in]	a	primo valore
[in]	b	secondo valore

Return values:

0	se a > di b
un	valore di verso da 0 negli altri casi

References INFINITY.

Referenced by dijkstra().

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().