Algoritmi di shortest path Dijkstra domande

Qual è l'obiettivo dell'algoritmo di Dijkstra?

Trovare il percorso più breve da un nodo sorgente a tutti gli altri nodi in un grafo pesato.

Dijkstra lavora con grafi positivi? Vero o falso?

Vero. L'algoritmo di Dijkstra funziona correttamente solo con archi di peso positivo.

Cosa rappresenta il termine "nodo"?

Un punto nel grafo che può rappresentare città, intersezioni, o altri elementi.

Qual è il primo passo dell'algoritmo di Dijkstra?

Inizializzare i pesi di tutti i nodi a infinito, tranne il nodo sorgente che è zero.

Qual è la struttura dati principale usata da Dijkstra?

La coda di priorità, per selezionare il nodo con il peso minimo.

Come si aggiornano i pesi dei nodi?

Se un percorso attraverso un nodo è più breve, il peso viene aggiornato con il nuovo valore.

Dijkstra può trovare soluzioni ottimali in grafi non connessi?

No, Dijkstra non trova percorsi per nodi in componenti non connessi.

Qual è la complessità temporale dell'algoritmo usando una coda di priorità?

La complessità è $\displaystyle O((V + E) imes ext{log}(V))$, dove V è il numero di nodi e E il numero di archi.

Quando termina l'algoritmo di Dijkstra?

Quando tutti i nodi sono stati visitati e i loro pesi definitivi sono stati determinati.

Cosa succede se ci sono archi con peso negativo?

L'algoritmo di Dijkstra non garantisce un risultato corretto con pesi negativi.

Esempio pratico: nodo A a nodo C, costi 10 e 15.

Se A → B è 10 e B → C è 5, il percorso A → B → C ha costo 15 (minore di 15).

Qual è il ruolo del nodo sorgente?

Il nodo sorgente è il punto di partenza da cui calcolare i percorsi più brevi.

Qual è la differenza tra Dijkstra e Bellman-Ford?

Dijkstra gestisce solo pesi positivi; Bellman-Ford gestisce anche pesi negativi.

Quale proprietà dei cammini più brevi usa Dijkstra?

La proprietà del cammino ottimale: ogni sotto-percorso di un cammino più breve è anch'esso un cammino più breve.

Cosa si intende per "costo" in Dijkstra?

Il costo è il peso associato agli archi tra i nodi nel grafo.

Qual è la caratteristica principale dell'algoritmo di Dijkstra?

Trova il cammino più breve da un nodo sorgente a tutti gli altri nodi di un grafo pesato, non negativo, usando una strategia greedy.

Qual è la complessità temporale di Dijkstra?

La complessità temporale è $\displaystyle O((V + E) imes ext{log} V)$ con una coda di priorità.

Vero o falso: Dijkstra funziona per grafi con pesi negativi.

Falso. Dijkstra non gestisce pesi negativi, altrimenti produce risultati errati.

Quale struttura dati è comune per l'implementazione?

La coda di priorità è utilizzata per gestire i nodi da esplorare.

Cosa rappresenta V ed E in Dijkstra?

V è il numero di vertici, E è il numero di archi nel grafo.

Qual è l'output dell'algoritmo?

L'output è un array delle distanze minime da un nodo sorgente a tutti gli altri nodi.

Qual è la differenza tra Dijkstra e Bellman-Ford?

Dijkstra è più veloce, $\displaystyle O((V + E) imes ext{log} V)$, mentre Bellman-Ford gestisce pesi negativi con $\displaystyle O(V imes E)$.

Perché Dijkstra è preferito per grafi non negativi?

Dijkstra garantisce soluzioni ottimali più rapidamente rispetto ad altri algoritmi in grafo non negativo.

Qual è la complessità spaziale di Dijkstra?

La complessità spaziale è $\displaystyle O(V)$ per memorizzare le distanze e i predecessori.

Cosa succede se il grafo ha cicli negativi?

Dijkstra non può gestire cicli negativi e può restituire distanze errate.

Implementazione: quali algoritmi per la coda di priorità?

- Heap binario - Fibonacci heap - Array

Fill in the blank: Dijkstra utilizza una ______ per esplorare i nodi.

coda di priorità.

Cos'è un nodo visitato in Dijkstra?

Un nodo visitato ha una distanza finale e non verrà più aggiornato.

Qual è il ruolo del nodo sorgente?

Il nodo sorgente è il punto di partenza per calcolare le distanze minime.

Esempio: Distanza da A a B in un grafo.

Se A ha un arco diretto di peso 5 verso B, la distanza è 5.

Cosa significa 'relaxation' in Dijkstra?

Significa aggiornare la distanza minima di un nodo se si trova una via più corta.

Cosa determina la scelta del nodo successivo?

Il nodo con la distanza minima attualmente nota viene scelto per l'esplorazione.

Qual è un'applicazione pratica dell'algoritmo di Dijkstra?

Navigazione GPS per trovare il percorso più breve tra due località.

Dijkstra è usato in quale settore?

Trasporti, telecomunicazioni, e reti informatiche.

Verità o falsità: Dijkstra trova il percorso più breve in un grafo non pesato.

Falsità. Funziona solo con grafi pesati con valori non negativi.

Compara Dijkstra e Bellman-Ford.

Dijkstra: solo pesi non negativi; Bellman-Ford: gestisce pesi negativi.

Quale algoritmo aiuta nella gestione delle reti di computer?

L'algoritmo di Dijkstra è utilizzato per ottimizzare il routing nei pacchetti dati.

Completa: L'algoritmo di Dijkstra è efficace per ____ .

reti stradali e mappe digitali.

In quale scenario si utilizza Dijkstra?

Per ottimizzare il percorso di consegna in un servizio di logistica.

Quale applicazione in un videogioco può usare Dijkstra?

Navigazione NPC per muoversi in modo efficiente nel mondo di gioco.

Qual è un utilizzo di Dijkstra nella robotica?

Pianificazione del percorso per robot autonomi in ambienti complessi.

Dijkstra può essere usato in quali tipi di grafo?

Grafi diretti e indiretti con pesi non negativi.

Qual è una limitazione nell'uso di Dijkstra?

Non gestisce pesi negativi, il che limita alcuni grafo.

Dijkstra è utile per l'ottimizzazione dei percorsi in ____ .

sistemi di trasporto pubblico e pianificazione urbana.

Quale applicazione può usare Dijkstra nelle telecomunicazioni?

Ottimizzazione della rete per la trasmissione di dati.

Qual è un esempio di utilizzo in una rete stradale?

Calcolo del percorso più veloce per un viaggio in auto.

Quale problema del mondo reale risolve Dijkstra?

Il problema del cammino minimo in molte applicazioni pratiche.

Dijkstra è usato in robotica per ____ .

navigare autonomamente evitando ostacoli.