PDA

Visualizza la versione completa : [PSEUDOCODICE] Dijkstra e archi negativi


snakessj
25-07-2010, 18:01
Ho un problema di Algoritmi e Strutture Dati che non riesco a risolvere:

dato un grafo G = (V,E) orientato e connesso con funzione di peso w con w : E -> |R (ovvero gli archi possono essere negativi) si dimostri che, anche se prendessi -k (valore dell'arco di peso minimo), e lo sommassi (k) a tutti gli archi di E; se chiamassi Dijkstra su tale grafo (ora privo di archi negativi) questo NON produrrebbe dei risultati corretti.

Spero di non aver dimenticato nulla, mi basta un contro esempio...grazie!

mostec
26-07-2010, 09:12
se non ricordo male(l'esame di algoritmi l'ho dato qualche anno fa) per il problema dei cammini minimi su grafi con archi negativi dijkstra non si poteva utilizzare, per questi casi c'era l'algoritmo di bellman-ford che perņ č computazionalmente meno efficiente..

snakessj
26-07-2010, 10:30
ok, ma a me serve un contro-esempio per dire "no, non si puņ usare nemmeno se si rendono gli archi positivi con questo metodo"...

Loading