Newsgroup: it.comp.lang.visual-basic
Titolo: trasformazione grafo in matrice per calcolo cammini minimi

ciao, è la prima volta che scrivo. sono bloccato su un lavoro e mi
servirebbe un consiglio/aiuto urgente.
qualcuno ha già dovuto creare una matrice dinamica da un grafo orientato e
pesato?
i nodi sono sull'ordine delle migliaia e voglio usare l'algoritmo di
dijkstra per il calcolo dei cammini minimi.
secondo voi,per la memoria occupata o per qualunque altro motivo che vi
viene in mente, è meglio una lista di successione o una matrice?
spero di essere stato abbastanza chiaro. :-)
grazie per l'attenzione.
ciao a tutti.
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 viene in mente, è meglio una lista di successione o una matrice?
Matrice n-dimensionale: occupa meno spazio, accesso rapido agli elementi,
rigidità nel ridimensionamento.
Lista: occupazione di memoria superiore, frammentazione di memoria ma
flessibilità nella rimozione/aggiunta di elementi; semplicità di accesso
alle relazioni tra i nodi (hai i puntatori) e in generale miglior approcio
OO.
Secondo me dipende tutto dalla statiticità o meno del grafo (sai a priori
quanti nodi/archi avrà? forse conviene usare un array) e
dall'implementazione a cui vuoi ispirarti.
L'unica nota, se decidi di utilizzare la lista (e quindi creare una classe
con puntatori a oggetti della classe stessa), devi tenere conto che VB
fatica molto a deallocare un numero grande di oggetti istanziati.
Avevo fatto un albero binario autobilanciante con un milione di elementi: VB
impiegava mezz'ora a deallocarli.
<x:termoPilucco>

 l'algoritmo di dijkstra
8-O
orcoboia! ti si è incasinata la tastiera!

in effetti pensavo di utilizzare una matrice, il problema è che non so se si
può fare una sola matrice con adiacenze e pesi oppure devo per forza fare 2
matrici una di adiacenze e l'atra dei pesi. (aumentando la memoria occupata)
I nodi sono nell'ordine delle migliaia e ogni nodo ha max 4 archi pesati
(con distanza da nodi adiacenti).
altro problema è la velocità, non può impiegarci mezz'ora!!!!


 altro problema è la velocità, non può impiegarci mezz'ora!!!!
Qui dipende dalla bontà dell'algoritmo... mi sembra di ricordare che
l'algoritmo di Dijkstra sia un caso particolare del Simplesso che nel caso
peggiore (ma molto sfigato) ha complessità esponenziale... il che potrebbe
rndere la cosa molto dura.
Però è anche vero che proprio essendo un caso particolare del Simplesso,
dovrebbe avere ottimizzazioni spinte per il problema che risolve.
Onestamente non ricordo. In ogni caso non credo ci sia di meglio in giro.
<x:termoPilucco>

La complessitą di dijkstra č O(n^2), perchč nel caso peggiore bisogna
eseguire n passi, ciascuno dei quali richiede O(n) iterazioni.
Grazie ancora mi sei stato molto utile.
alla prox.
ciao e buon week end.


[*Marg* = 
ke...@inwind.it
 in
news:bogdjk$1cgnf0$
1...@ID-193795.news.uni-berlin.de
] ha scritto:

In effetti è scritto in modo errato. Si chiama Dijkstra.
Più "semplicemente" si chiama problema del "commesso viaggiatore" che quello
lì ha tradotto in termini mate-magici ;-)

 quello lì ha tradotto in termini mate-magici ;-)
aaahhhh..... è il mago di Segrate!! svulazza!
ciaociao

 ??? Appunto, esattamente come ha scritto lui! ;)
Con una vbTextCompare, sì.