[PSEUDOCODICE] Problemuccio algoritmico relativo a cammini minimi, esame in vista...

[e-commerce84]

Salve a tutti,
allora...a breve avrò l'orale di algoritmi e strutture dati nel quale sono stato ammesso insieme ad altre 2 persone (su 40 partecipanti circa e tutti e 3 ammessi senza la sufficienza con l'intimidazione che o facciamo un ottimo orale o verremmo bocciati)

Visto che sono innumerevoli volte che provo questo esame vi chiedo un aiutino su di un esercizio che ho risolto solo parzialmente bene allo scritto e che mi chiederà sicuramente (lui a quanto pare lo risolve in maniera più efficiente...)

Il testo dell'esercizio dice:
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.

Indichiamo c(e) la CENTRALITÀ DI e che può essere formalmente espressa nel seguente modo:

c(e) = |{(u,v) appartenente a V^2 : Esiste P appartenente a R(u,v), e appartiene a P}|

con R(u,v) che indica l'INSIEME DI TUTTI I CAMMINI MINIMI TRA u E v

Si progetti un algoritmo EFFICIENTE che calcoli la centralità di tutti gli archi del grafo G


In pratica se un arco e = (x, y) (con x ed y che sono 2 nodi del grafo) appartiene a 3 cammini minimi tra 3 rispettive coppie di nodi, allora la centralità dell'arco e sarà 3.

La mia soluzione (solo parzialmente corretta) prevedeva di CALCOLARE TUTTI I CAMMINI MINIMI tra ogni coppia di nodi del grafo creando così un INSIEME R che contiene tutti i vari insieme R(u,v) per ogni u,v (dove R(u,v) erano appunto l'insieme dei cammini minimi tra un nodo u ed un nodo v)

Una volta che ho questo insieme R, per ogni arco e=(x,y) del grafo G pensavo di scorrere tutti i cammini in R, e quando in un certo cammino trovavo l'arco e aggiornavo un contatore relativo a quell'arco, passando direttamente al cammino successivo visto che non posso passare 2 volte per lo stesso arco.

Per quanto riguarda il contatore avevo pensato ad una matrice di adiacenza M, dove se ad esempio trovavo un arco tra il nodo 3 ed il nodo 5, andavo ad aggiungere un +1 al valore di M[3][5]

Con il senno di poi questa soluzione è molto stupida per i seguenti motivi:

1) Credo che calcolare l'INSIEME DI TUTTI I CAMMINI TRA 2 NODI u e v sia un problema computazionalmente molto costoso (a proposito, come potrei farlo?)
2) Calcolare l'INSIEME DI TUTTI I CAMMINI MINIMI TRA 2 NODI u e v credo sia ancora più complesso perchè credo che debba essere fatto calcolandosi prima tutti i cammini tra 2 nodi, ordinarli in base al loro peso complessivo e poi selezionare i k cammini che hanno lo stesso peso dello shortest path...

Insomma...un bell'impiccio...

Il professore ha dato una mezza indicazione dopo aver fatto uscire i risultati dello scritto e dice

A mio avviso la soluzione era molto piu' semplice: e=(x,y) si trova in un cammino minimo tra u e v se e solo se d(u,x)+w(x,y)+d(y,v) a che cosa e' uguale? E quindi come procedere?

A questo punto a me viene la seguente idea:

e=(x,y) è l'arco FISSO (perchè voglio trovare tutti i cammini tra un nodo di partenza u ed un nodo di destinazione v...quindi anche tali nodi u e v sono fissi !!!)

In pratica secondo me d(u,x) deve essere un CAMMINO MINIMO da u ad x. d(y,v) deve essere un CAMMINO MINOMO da y a v

Quindi mi viene da pensare che in qualche modo devo sfruttare un algoritmo che ricorsivamente poi và a lavorare sul cammino minimo P(u,x) e sul cammino minimo P(u,y)

booo...forse usando qualcosa tipo l'algoritmo di Floyd-Roy-Warshall...

Solo che non ne stò uscendo vivo...è un pomeriggio che ci sbatto la testa...

Vi prego è veramente importante...da questa cosa dipende la sorte del mio esame...

Grazie mille a chiunque mi aiuterà a capire

Grazie

[wingman87]

A mio avviso la soluzione era molto piu' semplice: e=(x,y) si trova in un cammino minimo tra u e v se e solo se d(u,x)+w(x,y)+d(y,v) a che cosa e' uguale?
A d(u,v)