Răspuns: 009 Algoritmul lui Dijkstra

[•GooDy]

Poate sa-mi explice si mie cineva "Algoritmul lui Dijkstra", ca nu prea am priceput, cu ce se mananca?

A, si care ar fi cel mai bun algoritm, dupa parerea voastra, pentru calcularea drumului minim?

Va multumesc anticipat.

[•cos_min]

Consulta asta: http://infoarena.ro/problema/dijkstra.

[•Cosmin]

Se vede ca se apropie olimpiada

Ai putea separa intrebarile in threaduri diferite ...

[•GooDy]

O sa le separ de acuma, imi cer scuze.

Consulta asta: http://infoarena.ro/problema/dijkstra.

Citisem deja si nu am inteles nimica, deaceea am cerut ajutor.
Plz. sa-mi explice si mie cineva .

[•fireatmyself]

Algoritmul lui Dijkstra este un algoritm de tip greedy. In randurile de mai jos D[ i ] reprezinta distanta de la nodul sursa (S), iar C[ i ][ j ] = costul muchiei (i,j).

Initial D[ i ] = INF (pt i dif de S) .
pasul 1: cautam nodul i pentru care D[ i ] este minim.
pasul 2: parcurgem toti vecinii lui i si reactualizam distanta pentru un vecin j, daca D[ j ] este mai mare decat            D[ i ]+C[ i ][ j ]. reluam de la pasul 1.

pasul 1 se poate face in O(n) (parcurgand vectorul D si luand minimul), iar complexitatea finala va fi  O(N*N+M). Daca vrei sa faci acest pas mai repede, de fiecare data cand reactualizezi distanta pentru un vecin o introduci intr-un heap (in O(log N)) si vei face pasul 1 in O(1), iar complexitatea finala va fi O(NlogN + M).

(prin log x se intelege log2 x)

Iti sugerez sa citest ceea ce am zis mai sus uitandu-te, in paralel, pe sursa lui Filip: http://infoarena.ro/job_detail/153886?action=view-source

[•GooDy]

Care ar fi cel mai bun algoritm, dupa parerea voastra, pentru calcularea drumului minim?

[•amadaeus]

Depinde de problema: daca ai sursa unica, poti folosi Dijkstra (cu heap-uri) sau Bellman-Ford (cu coada). Eu il prefer, in general, pe al doilea, pentru simplitate, cu toate ca primul se comporta, teoretic, mai bine.
Daca te intereseaza drumuri minime intre toate perechile de varfuri, folosesti Floyd-Warshall (sau Roy-Floyd, cum mai este numit).

Problema drumurilor minime este foarte bine tratata in CLR, o carte de care vei avea nevoie, daca te hotarasti sa incepi studiul serios

Iti sugerez, totusi, sa te documentezi putin mai mult inainte de a pune o astfel de intrebare pe forum, sunt pe internet suficiente surse de informare, in care vei gasi pe larg explicatii asupra algoritmului, poate mai complete sau mai usor de inteles decat iti va putea da cineva aici (eforturile lui Bogdan sunt cu adevarat de apreciat  un + de la mine). Abia dupa ce te vei convinge singur "cu ce se mananca" e indicat sa ceri sfaturi legate de anumite particularitati sau aplicatii.

[•byndrsn]

In plus, depinde si ce costuri sunt pe muchii. Dijkstra merge doar pe grafuri cu costuri non-negative.

[•Cosmin]

In general vrei sa stii mai multi algoritmi nu doar cel mai bun. Probabil nici nu exista unul cel mai bin. Daca stii mai multi in detaliu poti sa alegi in functie de cerinte cel care se potriveste mai bine la problema.