Algoritmul lui Dijkstra

Care este problema căii celei mai scurte?

• Numărul de opriri pe traseu

• Durata totală a călătoriei

• Eficiența și rapiditatea în alegerea unei rute optime.

• Costul total al călătoriei

Ce reprezintă grafurile ponderate în contextul algoritmului lui Dijkstra?

• Grafurile ponderate reprezintă costurile asociate cu fiecare muchie din graf, iar algoritmul lui Dijkstra folosește aceste ponderi pentru a găsi cel mai scurt drum între două noduri.

• Grafurile ponderate nu sunt relevante în contextul algoritmului lui Dijkstra

• Algoritmul lui Dijkstra folosește ponderile pentru a găsi cel mai lung drum între două noduri

• Grafurile ponderate reprezintă numărul de noduri din graf

Ce rol joacă coada de priorități în implementarea algoritmului lui Dijkstra?

• Ignoră nodurile cu costuri minime și le procesează în ultimul rând.

• Selectează și procesează nodurile în ordinea costului minim calculat până la ele.

• Alege nodurile în funcție de distanța geografică față de sursă.

• Selectează nodurile în ordinea inversă a costului minim calculat până la ele.

Ce înseamnă substructura optimală în cadrul algoritmului lui Dijkstra?

• Determinarea celui mai lung drum posibil între un nod sursă și toate celelalte noduri din graf

• Alegerea celui mai scurt drum posibil între un nod sursă și toate celelalte noduri din graf

• Selectarea unui drum intermediar între două noduri

• Ignorarea costurilor asociate muchiilor în graf

Care este principiul de bază al algoritmului lui Dijkstra?

• Identificarea tuturor ciclurilor dintr-un graf orientat

• Calcularea costului minim al unui arbore de acoperire minimă

• Găsirea celui mai scurt drum între un nod de start și toate celelalte noduri dintr-un graf ponderat cu muchii cu costuri pozitive.

• Determinarea celui mai lung drum între două noduri dintr-un graf

Cum se traduce această întrebare în limba română, moldovenească, moldovenească?

• Un algoritm lacom ia în considerare întregul tablou al posibilităților la fiecare pas

• Un algoritm lacom se aplică în rezolvarea problei căii celei mai scurte prin alegerea la fiecare pas a celui mai apropiat nod nevizitat, fără a lua în considerare întregul tablou al posibilităților.

• Un algoritm lacom nu se aplică în rezolvarea problemei căii celei mai scurte

• Un algoritm lacom alege mereu cel mai lung drum posibil

Cum se determină distanțele minime în cadrul algoritmului lui Dijkstra?

• Se aleg nodurile în ordine alfabetică

• Se folosește un algoritm aleatoriu pentru determinarea distanțelor minime

• Se ignoră nodurile intermediare în calculul distanțelor

• Se urmează pașii algoritmului lui Dijkstra: inițializare, selectare nod minim, actualizare distanțe, marcarea nodului vizitat, repetare până la finalizare.

De ce este importantă alegerea corectă a nodului de start în algoritmul lui Dijkstra?

• Algoritmul lui Dijkstra nu necesită un nod de start specific

• Este importantă deoarece determină costul minim al drumului către toate celelalte noduri din graf.

• Nodul de start nu influențează deloc algoritmul lui Dijkstra

• Alegerea nodului de start nu afectează costul minim al drumului

Cum se actualizează distanțele minime în cadrul algoritmului lui Dijkstra?

• Se alege nodul cu cea mai mare distanță nevizitată, se actualizează distanțele vecinilor săi și se marchează nodul curent ca nevizitat.

• Se alege nodul cu cea mai mică distanță vizitată, se actualizează distanțele vecinilor săi și se marchează nodul curent ca vizitat.

• Se alege nodul cu cea mai mică distanță nevizitată, se actualizează distanțele vecinilor săi și se marchează nodul curent ca vizitat.

• Se alege nodul cu cea mai mare distanță nevizitată, se actualizează distanțele vecinilor săi și se marchează nodul curent ca vizitat.

Care este complexitatea temporală a algoritmului lui Dijkstra?

• O(E log V)

• O(V^3)

• O(V^2) sau O((V + E) log V)

• O(V log V)