Precedente :: Successivo |
Autore |
Messaggio |
dverrastro Comune mortale
Registrato: 22/06/16 19:12 Messaggi: 4
|
Inviato: 26 Giu 2016 10:43 Oggetto: Cammini Minimi |
|
|
Salve, dovrei risolvere un problema di calcolo di cammini minimi con peso sui nodi invece che sugli archi, pensate che questo possa andar bene?
Codice: | CamminiMinimiDijkstra
Inizializza(G,S)
Q = V[G]
while notEmpty(Q)
u = ExtractMin(Q)
for ogni v appartente a Adj[u]
Rilassa(uv)
if d[v] > d[u] + w[s]
DecreaseKey(v,d[u] + w[v])
pi[v] = u |
Grazie in anticipo |
|
Top |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11572 Residenza: Tokelau
|
Inviato: 27 Giu 2016 09:39 Oggetto: |
|
|
che senso ha un cammino minimo con peso sui nodi? il totale sarà sempre lo stesso no? |
|
Top |
|
|
dverrastro Comune mortale
Registrato: 22/06/16 19:12 Messaggi: 4
|
Inviato: 27 Giu 2016 09:58 Oggetto: |
|
|
Non lo so, è un esercizio assegnato.. il professore suggeriva di spezzare il nodo in due nodi e di porre fra di essi un arco fittizio con peso uguale al peso che era inizialmente sul nodo. Su tutti gli altri archi bisognava porre peso uguale a 0. Pensi che la soluzione che ho scritto funzioni? |
|
Top |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11572 Residenza: Tokelau
|
Inviato: 29 Giu 2016 12:37 Oggetto: |
|
|
scusa, forse ho capito cosa intendi... trovare un cammino minimo su un grafo dato, partendo da un nodo assegnato e arrivando ad un altro assegnato.
Direi che non è diverso dall'algoritmo che lo calcola usando i pesi sugli archi, con la differenza che la funzione che restituisce il peso sull'arco (a,b) invece di prenderla dalla tabella dei pesi sugli archi la prende dalla tabella dei pesi dei nodi, immagino prenderai il nodo di arrivo come riferimento... |
|
Top |
|
|
|