Mod minim

În teoria graficelor , cea mai scurtă cale (sau cea mai scurtă cale) între două vârfuri (sau noduri) ale unui grafic este calea care leagă vârfurile menționate mai sus și care minimizează suma costurilor asociate traversării fiecărui arc (sau latură) ).

Problemă

Cea mai scurtă problemă de căutare a căilor poate fi definită atât pe graficele orientate, cât și pe cele neorientate. Poate fi formalizat după cum urmează: dat un grafic ponderat (adică un set $V.$ ${\ displaystyle V}$ $V.$ de vârfuri, un set $ȘI$ ${\ displaystyle E}$ $ȘI$ de arce și o funcție care asociază un cost sub forma unui număr real fiecărei părți: $f:E\rightarrow \mathbb {R}$ ${\ displaystyle f: E \ rightarrow \ mathbb {R}}$ ${\ displaystyle f: E \ rightarrow \ mathbb {R}}$ ) și a dat, de asemenea, două vârfuri distincte $v,v\prime \in V$ ${\ displaystyle v, v \ prime \ în V}$ ${\ displaystyle v, v \ prime \ în V}$ , găsi o cale ${\textstyle P=(e_{v,v_{2}},e_{v_{2},v_{3}},\ldots ,e_{v_{n},v\prime })}$ ${\ textstyle P = (e_ {v, v_ {2}}, e_ {v_ {2}, v_ {3}}, \ ldots, e_ {v_ {n}, v \ prime})}$ ${\ textstyle P = (e_ {v, v_ {2}}, e_ {v_ {2}, v_ {3}}, \ ldots, e_ {v_ {n}, v \ prime})}$ din $v$ ${\ displaystyle v}$ $v$ la ${\textstyle v\prime }$ ${\ textstyle v \ prime}$ ${\ textstyle v \ prime}$ asta, printre toți cei care leagă vârfurile $v$ ${\ displaystyle v}$ $v$ Și ${\textstyle v\prime }$ ${\ textstyle v \ prime}$ ${\ textstyle v \ prime}$ , minimizați suma $\sum _{e\in P}f(e)$ ${\ displaystyle \ sum _ {e \ în P} f (e)}$ ${\ displaystyle \ sum _ {e \ în P} f (e)}$ .

Există câteva variante ale acestei probleme în care, pornind de la un vârf dat, poate fi necesar să se găsească cele mai scurte căi spre toate celelalte vârfuri; sau găsiți cele mai scurte căi pentru fiecare pereche de vârfuri ale graficului.

O problemă similară este cea a vânzătorului călător , în care se caută cea mai scurtă cale care traversează toate nodurile graficului o singură dată, și apoi revine la punctul de plecare. Cu toate acestea, această problemă este NP-Complete , deci este posibil să nu existe o soluție eficientă.

În domeniul telecomunicațiilor , această problemă este uneori numită problema căii de întârziere min .

O altă aplicație a acestei probleme este prezentă în jocul Șase grade de separare, care încearcă să demonstreze că fiecare persoană este conectată la o altă persoană aleatorie printr-o cale de cunoaștere cu cel mult 5 intermediari.

Soluţie

O soluție la cea mai scurtă problemă de cale este obținută prin algoritmul de parcurs. Cei mai importanți algoritmi din această categorie sunt:

Algoritmul lui Dijkstra - rezolvă probleme cu o singură sursă dacă toate greutățile arcurilor sunt mai mari sau egale cu zero. Fără a necesita un timp de execuție ridicat, acest algoritm poate calcula de fapt cea mai scurtă rută de la un nod de pornire dat "p" și de la toate celelalte noduri ale graficului.
Algoritmul Bellman-Ford - rezolvă probleme cu o singură sursă, chiar dacă greutățile arcului sunt negative
Algoritmul A * - rezolvă problemele cu o singură sursă folosind euristică pentru a încerca să accelereze căutarea
Algoritmul Floyd-Warshall - rezolvă toate perechile posibile
Algoritmul lui Johnson - rezolvă toate perechile, poate fi mai rapid decât algoritmul lui Floyd-Warshall pe grafice rare

Bibliografie

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein .Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001. ISBN 0-262-03293-7 . Capitolele 24: Cele mai scurte căi cu o singură sursă și 25: Cele mai scurte căi din toate perechile, pp. 580-642.

Controlul autorității	GND ( DE ) 4138403-9

Portal IT

Portalul de matematică