Implementarea unui algoritm pentru determinarea drumurilor minime într-un graf

Mat. Draga Bălan

Software ITC – Filiala Suceava

Considerăm un graf G(X,U), cu mulțimea vîrfurilor X = {x1, x2, …, xn} și I = {1, 2, … N}, mulțimea indicilor vîrfurilor, iar U = mulțimea arcelor. Fiecărui arc (xk, xj) din U i se asociază o valoare pozitivă reprezentînd lungimea sa.

În practică, aceasta poate însemna durata între două operaţii, distanța între două localităţi, costul unei piese etc.

Notăm L = (lkj) matricea definită prin:

O                       cînd k = j

lkj = lkj            cînd (Xk, Xj) există în U

infinit              cînd (Xk, Xj) nu există în U

Valoarea infinită se consideră pozitivă atunci cînd căutăm drumurile minime şi negativă atunci cînd le căutăm pe cele maxime. […]

Vizualizează articolul complet

COORDONATELE PENTRU CITAREA ACESTUI ARTICOL SUNT URMĂTOARELE:
Draga Bălan, Implementarea unui algoritm pentru determinarea drumurilor minime într-un graf, Revista Română de Informatică şi Automatică (Romanian Journal of Information Technology and Automatic Control), ISSN 1220-1758, vol. 2(3-4), pp. 83-84, 1992.