[PSEUDOCODICE] Come trovare tutti i cammini tra 2 nodi di un grago diretto e pesato?

[e-commerce84]

Ciao,
è veramente importante...orale di algoritmi in vista...

Se ho un grafo G = (V, E, w) DIRETTO e CONNESSO e PESATO con:

V = {Insieme dei nodi)
E = {Insieme degli archi diretti}
w: E----> R (una funzione peso che ad ogni arco associa un peso reale)

Esiste un modo per trovare l'INSIME DI TUTTI I CAMMINI MINIMI tra una coppia di nodi u,v (cioè...se u e v sono collegati da 5 cammini di cui 3 minimi mi ritorna i 3 cammini minimi)

Eventualmente alle brutte andrebbe bene anche che calcoli semplicemente l'INSIEME DI TUTTI I CAMMINI (minimi e non) tra una coppia di nodi u,v (poi eventualmente la ordino dal meno costoso al più costoso e potrei selezionare i primi k cammini che pesano come il primo ed avere così l'insieme di tutti i cammini minimi calcolata)

Qualche idea?

Grazie
Andrea

[wingman87]

Ma la domanda è legata all'altro thread che hai aperto?
Se sì, mi permetto di farti notare che non ti servono tutti i cammini minimi in quanto la centralità di un arco era definita come:
La centralità di un arco e in un grafo G = (V, E, w) non diretto e pesato (V è l'insieme dei nodi, E è l'insieme degli archi e w è una funzione peso che associa un peso reale ad ogni arco) la definiamo come il numero di coppie di nodi che sono collegati da almeno un cammino minimo passante per e.

[e-commerce84]

Originariamente inviato da wingman87

Ma la domanda è legata all'altro thread che hai aperto?
Se sì, mi permetto di farti notare che non ti servono tutti i cammini minimi in quanto la centralità di un arco era definita come:
La centralità di un arco e in un grafo G = (V, E, w) non diretto e pesato (V è l'insieme dei nodi, E è l'insieme degli archi e w è una funzione peso che associa un peso reale ad ogni arco) la definiamo come il numero di coppie di nodi che sono collegati da almeno un cammino minimo passante per e.

Non è così strettamente legata all'altro 3d...quel discorso l'ho capito perfettamente...

Il problema è che visto che io l'ho risolto male dicendogli che mi calcolavo tutti i cammini minimi tra una coppia di nodi non vorrei che esistesse un algoritmo che fà questa cosa e che comunque me lo chiedesse...del tipo: "mi hai deto che ti calcoli tutti i cammini minimi tra due nodi, la tua soluzione fà cagare come complessità ma a parte questo...visto che non mi hai detto come fai a fare questa cosa sul compito...beh dimmelo adesso"

E non vorrei trovarmi ammutolito...

Quindi è un'altra domanda...slegata da quella dell'altro 3d e come detto mi accontento pure di sapere come calcolare tutti i cammini tra 2 nodi del grafo...

[wingman87]

Allora secondo me potresti usare Dijkstra, con esso ottieni tutti i cammini minimi volendo

[banryu79]

Originariamente inviato da wingman87

Allora secondo me potresti usare Dijkstra, con esso ottieni tutti i cammini minimi volendo

Beh, se deve calcolarli proprio tutti potrebbe usare il Floyd-Warshall.

[wingman87]

Se gli servono tutti i cammini minimi tra due nodi meglio Dijkstra.
In verità Floyd-Warshall non lo conoscevo, l'ho letto di sfuggita e non capisco se permette di avere tutti i cammini minimi da un nodo all'altro

[banryu79]

Originariamente inviato da wingman87

Se gli servono tutti i cammini minimi tra due nodi meglio Dijkstra.
In verità Floyd-Warshall non lo conoscevo, l'ho letto di sfuggita e non capisco se permette di avere tutti i cammini minimi da un nodo all'altro

Una singola esecuzione dell'algoritmo calcola tutte le lunghezze di tutti i cammini minimi tra tutte le coppie di vertici del grafo.
Se non ho capito male, per gli scopi di e-commerce84 dovrebbe bastare.