Trovare l'INSIEME di TUTTI i cammini minimi tra 2 nodi di G

[AndreaNobili1]

Ciao,
mi trovo nella seguente situazione da cui non riesco ad uscire...

Dato un grafo G = (V, E, w) NON DIRETTO e PESATO (V = insieme dei nodi, E= insieme degli archi; w associa un peso reale ad un arco)

C'è un modo di trovare l'INSIEME DI TUTTI I CAMMINI MINIMI tra una certa coppia di nodi u,v

Nel senso che se ad esempio ho che u,v sono collegati da 5 cammini di cui 3 minimi...posso calcolare i 3 cammini minimi che connettono u,v

Qualche idea?

Grazie mille
Andrea

[hamming_burst]

Nì.
Direi che puoi farlo se elimini di volta in volta un certo arco che produce un cammino minimo.

[apatriarca]

@hamming_burst: in che senso elimini di volta in volta un certo arco? come sceglieresti quell'arco? Come fai a capire se un particolare arco appartiene ad un solo cammino minimo?

Personalmente modificherei una qualche versione dell'algoritmo di Dijkstra in modo che sia in grado di memorizzare più cammini dello stesso costo minimo verso ogni nodo. Per ogni nodo memorizzi cioè sia il costo minimo che l'insieme dei nodi che lo precedono in questi cammini minimi.

[hamming_burst]

"apatriarca":@hamming_burst: in che senso elimini di volta in volta un certo arco? come sceglieresti quell'arco? Come fai a capire se un particolare arco appartiene ad un solo cammino minimo?

Personalmente modificherei una qualche versione dell'algoritmo di Dijkstra in modo che sia in grado di memorizzare più cammini dello stesso costo minimo verso ogni nodo. Per ogni nodo memorizzi cioè sia il costo minimo che l'insieme dei nodi che lo precedono in questi cammini minimi.

circa intendo quello che hai espresso te. "elimino" è inteso come valuto se eliminare tale arco che "produce" cioè è valido essere un cammino minimo secondo Bellman.

forse son stato un po' troppo stringato, cmq è da pensare meglio.