 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
cappi e grafo orientato
Clicca QUI per vedere il messaggio nel forum |
| Bloom |
Ciao a tutti sto facendo il progetto edilizia e sto pensando alla struttura dati per gestire le strade.
Io pensavo a un grafo orientato per poter poi utilizzare l'algoritmo di Ford (e simili) per calcolare il cammino minimo.
La mia domanda è questa: Se nel grafo orientato ci sono dei cappi come faccio ad utilizzare un algoritmo come ford che di cappi non ne vuol sentire parlare?
es:
ho 5 nodi:
a,b,c,d,e.
il mio grafo è :
a->a peso 4 (cappio)
a->b peso 10
a->c peso 12
c->d peso 1
d->e peso 3
b->e peso 1
Se parto da a e devo arrivare a e con Ford e Dijkstra continuerei a ciclare sul nodo a perchè l'arco a->a è quello con peso minore rispetto a->b e a->c.
Sapete darmi una mano?
Grazie Laura |
|
|
|
|
