Formularea problemei
Opțiunea 1. Există o rețea de autostrăzi care leagă orașele din regiunea Moscovei. Unele drumuri sunt într-o direcție. Găsește calea cea mai scurtă din orașul Moscova în fiecare oraș din regiune (dacă poți să te miști doar pe drumuri).
Opțiunea 2. Există un anumit număr de zboruri între orașele lumii, pentru fiecare cost cunoscut. Costul unui zbor de la A la B nu poate fi egal cu costul unui zbor de la B la A. Găsiți un traseu minim de cost (posibil cu transferuri) de la Copenhaga la Barnaul.
Definiție formală
Se indică un grafic [1] orientat ponderat fără bucle și arce cu greutate negativă [2]. Găsiți cele mai scurte căi de la un anumit vârf al graficului la toate celelalte noduri ale acestui grafic.
denumiri
- Este setul de vârfuri ale graficului
- - set de margini ale graficului
- - greutatea (lungimea) coastei
- - vârful de la care se caută distanța, adică punctul de plecare.
- Este lungimea curentă a celei mai scurte căi de la vârf la vârf
- Vertexul precede vârful în cea mai scurtă cale de la vârf la.
- - vârfurile, distanța până la care a fost deja calculată (dar, eventual, nu definitivă);
- - vârfurile la care se calculează distanța;
- - vârfurile, distanța până la care nu a fost încă calculată.
- - stochează numărul setului la care aparține vertexul i.
typedef pereche
const int inf = 1000 * 1000 * 1000;
Fie matricea D [1..N] să conțină lungimile curente cele mai scurte. Inițial, matricea D este umplută cu valorile "infinit", cu excepția D [s] = 0. După finalizarea algoritmului, această matrice va conține distanțele finale cele mai scurte.
Fie matricea P [1..N] conținând strămoșii actuali. La fel ca matricea D, matricea P se modifică treptat de-a lungul cursului algoritmului și până la final ia valori finale.
Inițial, toate nodurile sunt plasate în setul M2, cu excepția vârfului V0, care este plasat în setul M1.
La fiecare pas al algoritmului luăm vârful din setul M1 (primim elementul de sus din coadă). Fie V vertexul selectat. Transferăm acest vârf la setul M0. Apoi ne uităm prin toate marginile care ies din acest vârf. Fie T cel de-al doilea capăt al muchiei curente (adică nu este egal cu V), iar L este lungimea muchiei curente.
- Dacă T aparține lui M2, atunci T este transferat la setul M1 la sfârșitul coadă. DT este setat egal cu DV + L.
- Dacă T aparține lui M1, atunci încercăm să îmbunătățim valoarea lui DT: DT = min (DT, DV + L). Vertexul T însuși nu se mișcă în coadă.
- Dacă T aparține lui M0 și DT poate fi îmbunătățit (DT> DV + L), atunci vom îmbunătăți DT și vom întoarce vârful T la setul M1, plasându-l la începutul coadă.
Desigur, cu fiecare actualizare a matricei D, ar trebui să actualizați și valoarea în tabloul P.
Complexitatea algoritmului
Timpul de rulare al acestui algoritm. Cu toate acestea, în practică, algoritmul sa dovedit foarte bine: timpul său de lucru este estimat ca (estimare experimentală).
Compararea algoritmilor Dijkstra și Levit
În comparație cu metoda lui Dijkstra, metoda lui Levit pierde din faptul că unele noduri trebuie procesate în mod repetat, dar câștigă pe algoritmi simpli pentru a include și a exclude nodurile din setul M1. Experimentele arată că pentru grafice cu origine "geometrică", adică pentru grafice construite pe baza rețelelor de transport și a distanțelor reale, metoda Levit se dovedește a fi cea mai rapidă. El câștigă și mărimea programului.
Metoda Levite are de asemenea avantajul față de metoda lui Dijkstra, care este aplicabilă în cazul lungimilor negative ale arcului (la urma urmei, "lungimea arcului" este pur și simplu un nume care ne oferă asocieri utile cu realitatea). Dacă presupunem că valorile lui l (u) nu sunt neapărat pozitive, soluția celei mai scurte probleme a căii devine mult mai complicată.
Prima dificultate este că o regulă simplă a metodei Dijkstra se pierde pentru a determina finalitatea distanței calculate la un anumit arc. Această dificultate, așa cum o vom vedea mai jos, este ocolită, deși cu o anumită pierdere a eficienței metodei (toate arcele care duc la un vertex dat trebuie să fie verificate).
A doua dificultate este mai gravă: pentru lungimile negative în grafic pot exista contururi cu o sumă negativă a lungimilor arcului (să numim astfel contururi "negative"). Adăugarea unei căi negative la cale reduce valoarea funcției obiectiv și cu cât sunt mai multe ocurente ale conturului negativ pe care îl adăugăm, cu atât mai bine. A scăpa de scăderea infinită a minimului este pur și simplu imposibilă, dar există două modalități de ieșire din situația dificilă (desigur, alegerea producției nu depinde de noi, ci de rezolvarea problemei practice).
- Pentru a interzice includerea căilor în cale, adică ia în considerare doar căile simple, dar o astfel de interdicție face ca sarcina să fie foarte dificilă.
- În cazul contururilor negative, se presupune că problema nu are o soluție și va fi limitată la rezolvarea problemei în cazurile în care nu există contururi negative. În acest caz, metoda lui Levit va da soluția optimă necesară și, cu unele modificări, va permite "capturarea" contururilor negative.
- Algoritmul Bellman-Ford este o soluție la aceeași problemă dacă graficul poate conține ambele margini de greutate negativă
- Algoritmul Floyd-Worshell este căutarea celor mai scurte distanțe între toate perechile de vârfuri
- Algoritmul lui Johnson
- Algoritmul lui Dijkstra este o soluție la aceeași problemă, dar într-un mod diferit.
notițe
- ↑ Aici graficele ne-orientate și mixte ("parțial orientate") sunt un caz particular al graficului orientat.
- ↑ Pentru un grafic cu greutăți negative, se aplică un algoritm mai general - algoritmul Dijkstra cu potențial