[Algoritmi] Soluzione esercizio

[Danielking1]

Salve ragazzi sono alle prese con questo esercizio che non riesco a risolvere... Chi può darmi una mano?

Allora sia dato un grafo G= con |V|= n e |E|=m orientato non pesato (ovvero ogni arco pesa esattamente 1). Si definisce cammino un cammino che passa per i nodi p e q ( in qualsiasi ordine questi siano). p e q sono fissi e appartengono a G. Trovare un algoritmo che per ogni coppia di nodi u,v € G trovi, se esiste, un cammino minimo . L'algoritmo deve avere complessità computazionale O(n^2)...

Come si può fare? Io riesco a farlo in tempo O(n^3) o in tempo O(mn)....

[onlyReferee]

Ciao Danielking
Secondo me un'idea può essere quella di modificare l'algoritmo di Dijkstra inserendo un check per determinare di volta in volta se $p$ e $q$ appartengono o meno al cammino da $u$ a $v$ correntemente determinato. Questo dato che abbiamo pesi positivi (banalmente pari a $1$ nella fattispecie).

[Danielking1]

Ciao onlyRefee...
uhm... non credo che la soluzione che mi stai suggerendo mi porti a qualcosa... Dijkstra richiede tempo O(m+nlogn) per ottenere le distanze da un solo vertice a tutti gli altri ma per ogni coppia di vertici bisogna iterare il discorso su ogni nodo del grafo ottenendo O(mn)=O(n^3)

Per ottenere la sicurezza che il cammino sia è semplice: basta costruire un grafo ausiliario a quello dato in questo modo:
- Ripeto quattro volte tutti i nodi del grafo. Diciamo per ogni nodo u creo u,u',u'',u'''
- Per ogni arco (u,v) appartenente al grafo di origine su qualsiasi livello se v <> da p e da q replico l'arco su ogni livello
- Per ogni arco (u,p) appartenente al grafo di origine faccio:
a) per u appartenente al primo livello collego u a p'
b) per u appartenente al terzo livello (ovvero u=u'') collego u'' a p'''
-Per ogni arco (u,q) appartenente al grafo di origine faccio:
a) per u appartenente al primo livello collego u a q''
b) per u appartine al secondo livello (ovvero u=u'') collego u' a q'''

Per come è costruito il grafo un cammino che parte da un nodo al primo livello e raggiunge un nodo al livello terzo deve necessariamente passare per p e q e quindi su questo lato sono tranquillo...
Il tempo di esecuzione per ottenere distanze minime per ogni coppia di nodi in G è un bagno di sangue poichè potrei:
a) Applicare l'algoritmo di Floyd Warshall a partire da s al primo livello e ritornare le distanze per ogni u del quarto livello ma questo mi chiede tempo O(n^3)
b) Applicare la visita in ampiezza BFS ma per ottenere distanze per ogni coppia di nodi la devo eseguire su tutti i nodi del primo livello ottenendo O(mn) ovvero sempre O(n^3)
c) Non so che altro pensare...

Che altro aggiungere?

[onlyReferee]

"Danielking":Ciao onlyRefee...
uhm... non credo che la soluzione che mi stai suggerendo mi porti a qualcosa... Dijkstra richiede tempo O(m+nlogn) per ottenere le distanze da un solo vertice a tutti gli altri ma per ogni coppia di vertici bisogna iterare il discorso su ogni nodo del grafo ottenendo O(mn)=O(n^3)
[...]

Per essere precisi nel caso peggiore in cui abbiamo un grafo denso, ossia $k = n - 1$ la complessità diventa $O(n^2 \log n) \ne O(n^3)$ (che comunque è superiore a $O(n^2)$.
Nel frattempo comunque mi è venuta in mente una possibile soluzione che sfrutta gli alberi di copertura minimi (pertanto entrano in gioco gli algoritmi di Kruskal e Prim). Si può impostare manualmente a $0.5$ ($0$ no perché altrimenti vorrebbe dire che l'arco non esiste) il peso sugli archi adiacenti ai vertici $p$ e $q$ e poi lanciare uno dei due algoritmi suddetti (che a livello di complessità non sono superiori a $n^2$). Il tempo necessario ad effettuare l'aggiornamento dei pesi sugli archi adiacenti a $p$ e $q$ di cui accennavo all'inizio è trascurabile e pertanto a livello di complessità ci dovremmo essere. Che ne pensi
Sebbene questi algoritmi siano progettati appunto per determinare gli alberi di copertura minimi implicitamente nel nostro caso specifico ci potrebbero fornire anche i cammini minimi...