Newsgroup: it.comp.lang.c
Titolo: Dijkstra in C

Allora, devo realizzare un programmino che, dato in ingresso un digrafo
con pesi non negativi, un nodo sorgente s ed un nodo destinazione d,
calcoli il cammino piů corto (in base ai pesi degli archi) tra s e d.
Ovviamente mi č venuto in mente di utilizzare l'algoritmo di Dijkstra.
La mia domanda č:
se ho piů nodi sorgenti (diciamo k) e voglio calcolare il cammino piů
corto tra questi nodi ed il nodo di destinazione d, devo applicare
Dijkstra k volte (una per ogni nodo sorgente) e scegliere poi il
percorso piů piccolo o posso aggiungere un nodo fittizio da usare come
sorgente, collegato ai k nodi di prima con archi nulli? In quest'ultimo
modo potrei applicare Dijkstra una sola volta. Potrebbe funzionare?
Ciao e grazie.

modo potrei applicare Dijkstra una sola volta. Potrebbe funzionare?
dovrebbe funzionare, ma attento che diventa una algoritmo O(k*nlogn),
quindi con k molto grande diventa abbastanza lento. Se hai necessità
di migliori prestazioni e hai k circa uguale ad n, puoi utilizzare
quest'altro algoritmo O(n^3) (che non mi ricordo però come si chiama):
esso calcola le distanze minime tra tutti i nodi:
/* G è la matrice di adiacenza. I vertici non collegati hanno come
valore +infinito */
int G[n][n];
// inizializza G
int m,a,b;
for(m=0; m<n; m++)
	for(a=0; a<n; a++)
		for(b=0; b<n; b++)
			if (G[a][k]+G[k][b] < G[a][b]) G[a][b]=G[a][k]+G[k][b];
/* attenzione agli overflow! per simulare +infinito si consiglia di
usare MAX_INT/2, altrimenti G[a][k]+G[k][b] può trabordare */
Anto
--
Antonio Cuni, 18 anni, studente
Brainbench Certification: 
Master C++: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
http://www.brainbench.com/transcript.jsp?pid=1301688

 usare MAX_INT/2, altrimenti G[a][k]+G[k][b] puo` trabordare */
Ci sarebbero controindicazioni usando INFINITY?
ciao
Kronos
-- 
Home: 
http://kronoz.cjb.net
"La Via prosegue senza fine."
	Bilbo Baggins - Il Signore degli Anelli - J.R.R. Tolkien

Ci sarebbero controindicazioni usando INFINITY?
non so cosa sia INFINITY: è standard?
Cmq credo che MAX_INT/2 sia la soluzione migliore. Infatti l'algoritmo
che ti ho proposto (a proposito, è l'algoritmo di Floyd) esegue la
somma di due celle della matrice. Se queste valgono entrambe MAX_INT/2
il risultato della somma sarà MAX_INT (o MAX_INT -1), quindi
l'overflow non si verifica.
Invece se INFINITY fosse > MAX_INT/2 avresti degli overflow.


 Invece se INFINITY fosse > MAX_INT/2 avresti degli overflow.
No, perche` INFINITY + k = INFINITY (k e` un qualunque numero).
Inoltre non dovrebbero esserci problemi di confronto perche`:
  In comparison operations, positive infinity is larger than all values
except itself and NaN, and negative infinity is smaller than all values
except itself and NaN.
Da quello che ho capito INFINITY e NAN (Not a numeber) sfruttano le FPE
per la loro rappresentazione e di fatto non sono "numeri".
Il problema e` che avevo letto che rallentano molto la FPU...
ciao
Kronos
-- 
Home: 
http://kronoz.cjb.net
It can't rain forever,
but you can die before seeing the sun again.

No, perche` INFINITY + k = INFINITY (k e` un qualunque numero).
scusa la curiosità, ma come viene espansa questa macro?
E poi sei sicuro che vada bene anche con gli interi e non solo con i
float/double (visto che usano la FPU)?
Cmq secondo me in questo caso specifico MAX_INT div 2 va più che bene
(sempre che i singoli pesi degli archi non superino MAX_INT div 4...)
Anto
--
Antonio Cuni, 19 anni, studente


 Antonio Cuni, 19 anni, studente
Compiuto gli anni? Auguri!
ciao
Kronos
-- 
Home: 
http://kronoz.cjb.net
Se alla sera, dopo una strepitosa vittoria, guardandoti allo
specchio dovessi notare un secondo paio di palle, che il tuo 
cuore non si riempia d'orgoglio, perche` vuol dire che ti 
stanno inculando -- Saggio Cinese

Compiuto gli anni? Auguri!
grazie
Anto
--
Antonio Cuni, 19 anni, studente
