Lecţia 3

Problema drumurilor minime într-un graf arbitrar G=(X,Y), muchiile căruia au ponderi nenegative, date de matricea costurilor C[ci,j] este de a determina distanţa minimală între două vârfuri date ale grafului: s şi t, în condiţia că aşa un drum există. Pentru problema dată există mai multe generalizări. Iată doar câteva din ele:

•De a determina toate distanţele minime de la un punct dat (dacă ele există)•Să se determine distanţele minimale între toate perechile de puncte

Algoritmul Dijkstra se bazează pe aplicarea marcherilor pentru nodurile în care ajungem cu indicarea distanţelor de la nodul iniţial până la ele. Iniţial marcherile au valori mari, care pe parcursul realizării algoritmului se micşorează, până nu ating valoarea distanţei minime între punctul iniţial şi cel, căruia îi este aplicat marcherul. La fiecare iteraţie a algoritmului exact un marcher devine permanent, adică indică drumul minim. Deci algoritmul va avea cel mult n iteraţii.Pentru nodul xi marcherul său îl vom nota prin l(xi). Marcherul va fi format din două componente (spre deosebire de algoritmul clasic Dijkstra): a)costul drumului minimal de la s la xi şi b)b) nodul xj din care am venit în xi.

Pasul 1. Considerăm l(s) = (0,s) – marcher permanent pentru vârful iniţial. Considerăm l(xi) = (, nedefinit) marchere temporare pentru toate celelalte vârfuri. Considerăm s = p. Pasul 2. (Recalcularea marcherilor) Pentru toţi xi(p) cu marcheri temporari, vom recalcula marcherii în corespundere cu formula: l(xi) min[ l(xi), l(p)+c(p,xi )] Pasul 3 (Determinarea marcherului, care devine permanent) Între toate nodurile cu marchere temporare îl determinăm pe cel cu marcherul minim l(x*i) = min[ l(xi)] .  A doua componentă a marcherului permanent o considerăm p. Considerăm p = x*i

 Pasul 4. (Repetarea iteraţiei) Dacă p = t atunci marcherul l(t) indică costul minim a drumului di s în t. Pentru restabilirea drumului minim trecem la pasul 5. În caz contrar (p t) trecem la pasul 2. Pasul 5. Pentru restabilirea traiectoriei folosim a doua componentă a marcherului: considerăm x=t. Includem în traiectorie muchia (x, l(×, xi)) . Considerăm x xi Repetăm procesul, până când nu revenim în punctul s

Fie, la un careva pas marcherii permanenţi dau drumurile de cost minim pentru o submulţime S1 X . S2 = X/S1

Presupunem că pentru un careva x din S drumul minimal trece prin S2.  

Fie, la un careva pas marcherii permanenţi dau drumurile de cost minim pentru o submulţime S1 X .

S2 = X/S1

Presupunem că pentru un careva x din S drumul minimal trece prin S2.

Fie xj primul punct di S2, care aparţine drumului minim (s xi ). Drumul de la xj la x*i este = > 0. Atunci l(xj) l(x*i) - < l(x*i). Atunci rezultă, că l(x*i) nu este cea mai mică, ceea ce contrazice condiţia de selectare a nodului. Deci drumul minimal trece integral prin S1.

Fie cii = 0 , cij = ∞ dacă nu există muchia (i,j), altfel cij = dij

 Pas 1. k=0

 Pas 2 k=k+1

 Pas 3 pentru toţi i k, astfel că cik ∞ şi pentru toţi j k, astfel că ckj ∞ vom calcula cij = min [cij,

(cik + ckj)].

 Pas 4 dacă k = n – sfârşit, în caz contrar revenim la pasul 2. 

Pentru restabilirea drumurilor folosim maricea T Ininţial rîndul i al matricei se completează cu i. apoi, la transformarea elementului cij din matricea de bază vom transforma şi matricea secundară: tij = tkj dacă cij > (cik + ckj)].  Drumul va fi xi, x1, x2, ... xr, xr+1, xj

 

xr+1 = ti,j

xr = ti,x(r+1)

xr-1 = ti,x(r)

Pentru graful reprezentat pe desen, determinaţi drumurile minime de la vârful 1 la toate celelalte vârfuri.

1

2

4

3

5

5

6

6

9

810

10 15

20

4

65

8

7

Varianta 1Realizaţi într-un limbaj de programare de nivel înalt algoritmul Dijkstra pentru grafuri neorientate cu cel mult 100 vârfuri

Varianta 2Realizaţi într-un limbaj de programare de nivel înalt algoritmul Floyd pentru grafuri neorientate cu cel mult 100 vârfuri.

Note:1.Realizarea GUI al aplicaţiei va constitui un avantaj2.Realizarea unui editor de grafuri incorporat va constitui un avantaj

Lucrarea de laborator va conţine:1.Descrierea algoritmului2.Analiza complexităţii3.Codul sursă al programului4.Exemple ale rezultatelor de lucru al programului