Dijkstra

Înțelegerea algoritmului

Algoritmul funcționează prin selectarea iterativ nodul cu cea mai mică distanță de tentație, apoi actualizarea distanțelor la nodurile sale învecinate. Acesta continuă până la cea mai scurtă cale de nod țintă este găsită sau toate nodurile au fost prelucrate.

Procesul de calcul pas cu pas

Să presupunem că avem un grafic cu nodurile A, B, C, D și E, și următoarele margini ponderate:

  • A-B: 4
  • A-C: 2
  • B-C: 1
  • B - D: 5
  • C - D: 8
  • C-E: 10
  • D-E: 2

Pornind de la nodul A, inițializa distanțe: A = 0, altele = infinit. Marcați toate nodurile ca nevizitat.

Iterație 1

Selectați nodul A (distanța 0). Actualizați nodurile învecinate B și C:

Distanţa până la B: 4 (A + 4), până la C: 2 (A + 2). Mark A este vizitat.

Iterație 2

Selectaţi nodul C (distanţa 2). Actualizarea vecinilor D şi E:

Distanţa până la D: 10 (C + 8), până la E: 12 (C + 10), marca C, aşa cum a fost vizitată.

Iterație 3

Selectaţi nodul B (distanţa 4). Actualizarea vecinului D:

Distanţa până la D: 9 (B + 5), care este mai mică decât cea anterioară 10. Actualizarea distanţei D la 9. Mark B, aşa cum a fost vizitată.

Iterație 4

Selectaţi nodul D (distanţa 9). Actualizarea vecinului E:

Distanţa până la E: 11 (D + 2). Actualizarea distanţei E la 11. Mark D aşa cum a fost vizitat.

Iterație 5

Nodul E rămas are o distanță de 11. Mark E ca vizitat. Cea mai scurtă cale de la A la E este prin nodurile C, B, D, și E cu distanța totală 11.