[Algoritmo] Floyd - warshall si puo' usare?

[Cesaropa12]

Sto cercando il più lungo cammino in un grafo non pesato. Si puo' modificare l'algoritmo di floyd-warshall e anziche' ad ogni soluzione prendere il minimo, prendere il massimo?

[elgiovo]

Come algoritmo per i cammini minimi conosco quello di Dijkstra, che mi sembra invertibile.
Un mio suggerimento: essendo il grafo non pesato, il cammino più lungo è sicuramente quello che copre più spigoli.

[elgiovo]

Un'idea può essere questo procedimento:
1) c'è più di un cammino da A a B? (si $to$ continua; no $to$ finito);
2) usare l'algoritmo di Dijkstra (o quello da te citato) per trovare il cammino minimo da A a B;
3) eliminare tale cammino;
4) c'è più di un cammino da A a B? (si $to$ continua; no $to$ finito);
5) usare l'algoritmo di Dijkstra (o quello da te citato) per trovare il cammino minimo da A a B;
6) eliminare tale cammino;
...

sicuramente funziona.

[codino75]

la butto li' senz apensarci tanto:
se l'algoritmo che trova il cammino minimo in oggetto valuta anche i pesi degli archi, si puo' valutare se funziona con pesi negativi (es. peso=-1)
alex

[vl4dster]

No, non puoi risolvere il problema del cammino piu' lungo non pesato (in tempo polinomiale) con un algoritmo di programmazione dinamica (tipo Floyd).
Esempio classico:
Considera $G=(V,E)=({q,r,s,t}, {(q,r), (r,q), (r,t), (t,r), (t,s), (s,t), (s,q), (q,s)})$ (disegnalo)
Considera ad esempio il cammino $q->r->t$, che e' un cammino piu' lungo da $q$ a $r$.
$q->r$ e' un cammino piu' lungo da $q$ a $r$ ? NO
$r->t$ e' un cammino piu' lungo da $r$ a $t$ ? NO
Dunque non c'e' sottostruttura ottima e dunque non puoi usare la prog dinamica, in qualsiasi
delle sue forme.
(In realta' non puoi neanche ricostruire un cammino piu' lungo conoscendo i sottocammini
piu' lunghi perche' se li unisci puoi formare cicli)

In realta' questo problema e' NP-Completo dunque se ti interessa un algo polinomiale
devi cercare tra le euristiche o algo di approssimazione...(ammesso che ci siano)

[lilengels]

"elgiovo":Un'idea può essere questo procedimento:
1) c'è più di un cammino da A a B? (si $to$ continua; no $to$ finito);
2) usare l'algoritmo di Dijkstra (o quello da te citato) per trovare il cammino minimo da A a B;
3) eliminare tale cammino;
4) c'è più di un cammino da A a B? (si $to$ continua; no $to$ finito);
5) usare l'algoritmo di Dijkstra (o quello da te citato) per trovare il cammino minimo da A a B;
6) eliminare tale cammino;
...

sicuramente funziona.

quindi è possibile floyd warshall per grafi non orientati?
perchè avevo letto che lavora solo su grafi orientiati
grazie

[vict85]

Attenzione però, se il grafo possiede loop nella componente connessa in cui ci sono i due punti da collegare, allora il percorso più lungo è infinito (basta percorrere più volte il loop). La ricerca quindi di un percorso massimale è necessario imporre delle condizioni aggiuntive per evitare questo tipo di casi patologici, per esempio imporre di non passare due volte da uno stesso vertice.

[vict85]

Mi sono reso conto che anche senza cicli, è sufficiente tornare indietro per costruirne uno. Quindi la non ripetizione dei vertici è una condizione necessaria affinché il percorso più lungo non sia infinito per quasi ogni grafo.

Detto questo, con la richiesta della non ripetizione non vedo il problema della programmazione dinamica: ogni sottocammino di un cammino massimale deve essere massimale nel grafo privato dei vertici usati nel resto del cammino. Anche se in effetti non penso sia facilissimo da imporre in questo modo.

[lilengels]

"vict85":Attenzione però, se il grafo possiede loop nella componente connessa in cui ci sono i due punti da collegare, allora il percorso più lungo è infinito (basta percorrere più volte il loop). La ricerca quindi di un percorso massimale è necessario imporre delle condizioni aggiuntive per evitare questo tipo di casi patologici, per esempio imporre di non passare due volte da uno stesso vertice.

quindi se incontrassi un esercizio del tipo: "trovare il cammino minimo tra due vertici i,j in in un grafo tale che ci siano esattamente n archi rossi tra i e j"
quale algoritmo mi consiglieresti di utilizzare?
grazie

[vict85]

I cammini minimi sono ben definiti, sono i cammini massimi che non lo sono (supponendo grafo non pesato o con pesi non-negativi).

[lilengels]

quindi posso usare l'algoritmo di floyd warshall senza problemi?
grazie

[vict85]

Lo devi adattare alla particolare condizione che stai considerando. Cioè non è detto che il percorso minimo sia il minimo che passa per $n$ archi rossi.

[lilengels]

sì, esatto, infatti pensavo di calcolare il percorso minimo con n archi rossi, quindi non è detto che sia anche il percorso minimo da i a j (ma comunque se ci fossero altri percorsi con n archi rossi , non sarebbero più piccoli di quello calcolato)

[lilengels]

"vict85":Lo devi adattare alla particolare condizione che stai considerando. Cioè non è detto che il percorso minimo sia il minimo che passa per $n$ archi rossi.

come potrei modificare l'algoritmo di floyd warshall per ottenre un algoritmo che calcola il cammino minimo tra 2 vertici con esattamente 2 archi rossi?
grazie