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.