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 = {x₁, x₂, …, x_n} și I = {1, 2, … N}, mulțimea indicilor vîrfurilor, iar U = mulțimea arcelor. Fiecărui arc (x_k, x_j) 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 = (l_kj) matricea definită prin:

O                       cînd k = j

I_kj = I_kj            cînd (X_k, X_j) există în U

infinit              cînd (X_k, X_j) 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.