Implementarea Algoritumului Dijkstra pentru Calcularea Drumului Optim Folosind Java

1. Introducere

1.1 Ce este un algoritm?Tipuri de algoritmi folositi pentru calcularea drumului optim

Scurt istoric:

“Originile teoriei grafurilor se gasesc in rezolvarea unor probleme de jocuri si amuzamente matematice,care au atras atentia unor matematicieni de seama cum ar fi: Euler, Hamilton, Cayley, Sylvester, Birkoff. Data nasterii teoriei grafului este considerata a fi anul 1736. Cand matematicianul Leonhard Euler a publicat un articol in care a clarificat problema celor 7 poduri si a prezentat metode pentru rezolvarea altor probleme de acelasi tip. Cu 200 ani mai tarziu aparea la Leipzic prima carte de teorie a grafurilor al carei autor este matematicianul maghiar Denes Koreg. In amintirea contributiei lui Euler unele notiuni si tipuri de grafuri de care acesta s-a ocupat sunt denumite de catre Koreg lant eulerian ,graf eulerian,etc. Un alt matematician care s-a ocupat de aceleasi probleme ca si Euler, dar care si-a publicat rezolvarile cercetarilor sale in anul 1873 a fost Carl Hierholzer. Alte izvoare ale teoriei grafurilor sunt:studiul retelelor electrice, problema celor 4 culori, aplicatiile teoriei grafurilor in chimie(initiate de Cayley), probleme hamiltoniene, grafuri planare. Fizicianul Kirchoff a studiat la mijlocul secolului al XIX-lea retele electrice cu metode care apartin astazi teoriei grafului contribuind la dezvoltarea acestei teorii. Termenul graf a fost folosit pentru prima data in sensul sau actual in 1878 de matematicianul Sylvester. Teoria grafurilor are numeroase apeluri in chimie, contribuind in mare masura la rezolvarea problemelor de numarare a grafurilor apartinand unor clase speciale. “

“Un algoritm este un set de instructiuni care trebuie executate pentru a se obtine un raspuns la o problema data.

Un algoritm are urmatoarele proprietati (Knuth):

– finitudine: trebuie sa se termine intotdeauna dupa un numar finit de pasi (instructiuni);

– determinism: fiecare pas trebuie sa fie exact precizat, in mod riguros si neambiguu;

– generalitate: trebuie sa rezolve problema pentru orice date de intrare din domeniul

precizat;

– efectivitate: fiecare instructiune trebuie sa fie exacta si de durata finita.

Ultima proprietate trebuie nuantata, avind in vedere faptul ca memoria oricarui

calculator este limitata. Nu intotdeauna operatiile aritmetice se efectueaza exact, in unele

cazuri obtinindu-se o aproximare a rezultatelor, cum sint de exemplu implementarile bazate

pe aritmetica in virgula mobila (Goldberg).

In cadrul acestei lucrari algoritmii sint descrisi intr-un limbaj de tip Algol, un precursor al

limbajului Pascal.

Avind un algoritm care rezolva o problema data, urmeaza sa determinam resursele

acestuia. Concret, de cita memorie si timp avem nevoie ca sa obtinem solutia problemei? In

acest scop facem urmatoarele simplificari: fiecare operatie elementara a algoritmului se

executa intr-o unitate de timp, informatiile despre un obiect elementar se memoreaza intr-o

locatie de memorie.

Fie f  N  N o functie care indica relatia dintre numarul de valori (date de intrare)

prelucrate de un algoritm, si numarul de operatii elementare efectuate de acesta pentru

obtinerea rezultatelor. Functia f poate avea o expresie analitica destul de complicata, de

aceea consideram inca o functie g  N  N cu o expresie analitica simplificata.

Definitia 1.2. Functia f are ordinul de marime cel mult g(n), notatie: f  O(g(n)), daca

si numai daca exista doua valori, c  0 si n0  N astfel incit pentru orice n  n0 sa avem f(n)

 c g(n).

O(g)  { h  N  N |  c  0, n0  N a. i.  n  n0, h(n)  c g(n) }.

Definitia 1.3. Functia f are ordinul de marime cel putin g(n), notatie: f  (g(n)), daca

si numai daca exista doua valori, c  0 si n0  N astfel incit pentru orice n  n0 sa avem f(n)

 c g(n).

(g)  { h  N  N |  c  0, n0  N a. i.  n  n0, h(n)  c g(n) }.

Definitia 1.4. Functia f are ordinul de marime g(n), notatie: f  (g(n)), daca si numai

daca exista trei valori, c1, c2  0 si n0  N astfel incit pentru orice n  n0 sa avem c1 g(n)  f(n)

 c2 g(n).

(g)  { h  N  N |  c1, c2  0, n0  N a. i.  n  n0,

c1 g(n)  h(n)  c2 g(n) }.

Prezentam doua rezultate remarcabile care vor fi folosite pe parcursul lucrarii:

(1) Se da un sir de n valori dintr-un domeniu pe care este definita o relatie de ordine

totala. Cel mai eficient algoritm de ordonare a sirului dat, care se bazeaza pe comparatii, are

complexitate de ordin (n log n).

(2) Se da un sir de n valori ordonate. Cautarea unei valori (localizarea pozitiei acesteia

sau obtinerea unui raspuns negativ) in sirul dat necesita un timp de ordin O(log n).