Dijkstra ed ottimalità sottocammini

[anonymous_f3d38a]

Buongiorno a tutti! Ho una domanda che riguarda l'algoritmo di Dijkstra.

Si consideri un grafo connesso $G$ con $n$ archi ed $m$ nodi.
In entrambi i grafi viene definito un nodo sorgente $s$ ed un noto termine (destinazione) $t$.
Viene applicato l'algoritmo di Dijkstra per trovare il cammino minimo da $s$ a $t$.

---------------------------------------------------------------------------------

DOMANDA

Per quali nodi del grafo $G$, al termine dell’algoritmo di Dijkstra, è stato determinato un cammino ottimo?

$a)$ per tutti i nodi che appartengono al cammino minimo da $s$ a $t$
$b)$ per tutti i nodi che sono stati selezionati
$c)$ per tutti i nodi a cui è stata assegnata un'etichetta
$d)$ per tutti i nodi

Motivare la risposta.
Nota: le risposte corrette possono essere più di una.

---------------------------------------------------------------------------------

Allora, per il teorema di ottimalità dei sottocammini, la $a$ è sicuramente vera. Io risponderei la $a$ e basta.
Voi che ne pensate? Chiedo perché non saprei come dimostrare che la $b$ e la $c$ sono false.

[vict85]

Dijkstra riceve un grafo \(G\) e ne estrae un sottografo orientato \(A\) che possiede la proprietà di essere un albero¹, usando quest'ultimo produce il cammino ottimo richiesto.

Siccome ci si ferma quando si trova il cammino ottimo tra \(s\) e \(t\), non è detto che si visitino tutti i nodi, quindi (d) è senz'altro sbagliato.

Ogni cammino positivo² di \(A\) è un cammino ottimo anche in \(G\). Se il grafo non è orientato, allora lo stesso vale per la direzione negativa (da figli a padri).

Rimangono (b) e (c). Non sono sicuro cosa voglia dire selezionato e etichettato nella terminologia del tuo libro/professore quindi do una risposta un po' più generica. Indico con \(a\rightarrow b\) il cammino ottimo tra \(a\) e \(b\) (per semplicità suppongo sia unico). Nota che \(b\rightarrow a\) non è altro che \(a\rightarrow b\) percorso in direzione opposta (\(G\) non è orientato). Per ogni nodo di \(A\), \(s\rightarrow a\) appartiene a \(A\). Supponiamo quindi che sia abbia \(\ell(s\rightarrow a) < \ell(s\rightarrow b)\). Vogliamo sapere sotto che condizioni \(a\rightarrow b\) appartiene ad \(A\). La risposta è se e solo se \(s\rightarrow b = s\rightarrow a\rightarrow b\). Infatti se fossero diversi allora \(s\rightarrow a\rightarrow b\rightarrow s\) sarebbe un ciclo.

---

Note

1. Un grafo è un albero se è connesso e aciclico. Aggiungo qui la proprietà di essere orientato dalla radice alle foglie perché è sia più simile al significato usuale in informatica che più corretto per l'algoritmo specifico. ↑
2. Chiamo cammino positivo un cammino in cui si va sempre da un padre al figlio e non il viceversa ↑

[anonymous_f3d38a]

Innanzitutto ti ringrazio per la risposta.
Mi sono dimenticato di precisare che il grafo in questione è orientato.

[vict85]

Allora sono tutti falsi. Pensa al caso di una strada a senso unico e un percorso dall'inizio della strada alla sua fine. È evidente che neanche \(t\rightarrow s\) è incluso nella ricerca.

[anonymous_b7df6f]

L'etichettatura o "selezionatura" è una peculiarità dell'algoritmo di Dijkstra, si trova in molti libri, articoli, siti web.

Per quali nodi del grafo $G$, al termine dell’algoritmo di Dijkstra, è stato determinato un cammino ottimo?

$a)$ per tutti i nodi che appartengono al cammino minimo da $s$ a $t$
$b)$ per tutti i nodi che sono stati selezionati
$c)$ per tutti i nodi a cui è stata assegnata un'etichetta
$d)$ per tutti i nodi

Motivare la risposta.
Nota: le risposte corrette possono essere più di una.

Rispondendo a @anonymous_f3d38a, riporto quello che è scritto su un libro in mio possesso.
Definisco $R$ l'insieme dei nodi a cui è stata assegnata un'etichetta definitiva.
Dato un grafo $G$ pesato con costi $c$ non negativi, a ciascuna iterazione dell'algoritmo di Dijkstra, l'etichetta definitiva assegnata a ciascun nodo $v in R$ rappresenta il costo di un cammino minimo da $s$ a tale nodo, mentre l'etichetta temporanea di ogni nodo $v$ non appartenente ad $R$ rappresenta il minimo costo di un cammino da $s$ a tale nodo in cui i nodi intermedi sono tutti in $R$.

Quindi la risposta corretta è la ($b$), si può selezionare anche la ($c$) precisando che tale cammino minimo non è "assoluto", ma è quello che si trova scegliendo tra i nodi appartenenti all'insieme $R$.

[vict85]

Mi sembrava di essere stato chiaro, comunque, i problemi sono i seguenti:
1) I cammini ottimi trovati sono solo quelli che partono da \(s\) e i suoi sotto-cammini,
2) Se il grafo è orientato, i cammini minimi per i percorsi inversi non appartengono mai all'albero di ricerca.
Se lo scopo è quello di trovare tutti i percorsi minimi allora si devono usare altri algoritmi.

Se per esempio hai due strade principali parallele, gli archi tra di loro non verranno inclusi facilmente nell'albero di ricerca anche se sono il cammino ottimale per andare da un nodo di una in un nodo dell'altra.

[anonymous_f3d38a]

Grazie mille a entrambi, molto chiari.

P.s. grafo orientato non significa semplicemente che tutti gli archi hanno un orientamento?

[vict85]

Sì, anche se esistono delle piccole varianti nelle definizioni. Insomma, un grafo pesato normale può essere visto come un particolare grafo pesato orientato (in cui gli archi hanno sempre inverso e i pesi sono gli stessi in entrambe le direzioni) o come qualcosa definito in modo leggermente diverso.
Comunque sono forse stato un po' impreciso. Quello che volevo dire è che l'albero di ricerca è un grado in cui la relazione definita dagli archi è asimmetrica, quindi contiene i percorsi minimi in una certa direzione e mai nella direzione opposta. Però, se la relazione definita dagli archi del grafo è simmetrica e se i costi non dipendono dall'orientamento dell'arco (ovvero se il grafo è non orientato) allora un cammino ottimo è ottimo anche se percorso nella direzione opposta.