|
|||||||
|
|
|
 |
|
|
Strumenti |
12-09-2004, 21:09
|
#1 |
|
Member
Iscritto dal: Jul 2002
Messaggi: 55
|
[C] Grafi e cammini
Io ho un grafo (lo rappresento tramite una lista di adiacenza).
Ho un punto di partenza e di arrivo, ogni arco ha un costo. Devo trovare il cammino che costa meno. Che algoritmo posso usare? Bellman-ford puo' essere una giusta scelta? |
|
|
|
13-09-2004, 08:54
|
#2 |
|
Senior Member
Iscritto dal: Apr 2002
Città: Palermo
Messaggi: 4913
|
Se hai un vertice sorgente e vuoi trovare il cammino minimo tra esso e tutti gli altri vertici allora ti conviene usare l'algoritmo di DIJSKTRA (spero di averlo scritto bene), nell'implementazione base ti costa O(V^2).
L'algoritmo di Bellman-Ford, non l'ho studiato, cmq l'algoritmo che ti ho detto sopra ti dovrebbe bastare 
__________________
Sun Certified Java Programmer - Sun Certified Web Component Developer - Sun Certified Business Component Developer |
|
|
|
|
|
| Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 06:06.
