Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
Cammini Minimi
Nuovo argomento   Rispondi    Indice del forum -> Programmazione
Precedente :: Successivo  
Autore Messaggio
dverrastro
Comune mortale
Comune mortale


Registrato: 22/06/16 19:12
Messaggi: 4

MessaggioInviato: 26 Giu 2016 10:43    Oggetto: Cammini Minimi Rispondi citando

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 Smile
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 27 Giu 2016 09:39    Oggetto: Rispondi citando

che senso ha un cammino minimo con peso sui nodi? il totale sarà sempre lo stesso no? Confused
Top
Profilo Invia messaggio privato HomePage
dverrastro
Comune mortale
Comune mortale


Registrato: 22/06/16 19:12
Messaggi: 4

MessaggioInviato: 27 Giu 2016 09:58    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 29 Giu 2016 12:37    Oggetto: Rispondi

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... Confused
Top
Profilo Invia messaggio privato HomePage
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Programmazione Tutti i fusi orari sono GMT + 1 ora
Pagina 1 di 1

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi