[PSEUDOCODICE] Dijkstra e archi negativi

[snakessj]

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]

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]

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"...