calea cea mai scurtă Algoritm
Rezultatul cel mai scurt algoritm de căutare cale este o secvență de muchii care leagă două vârfuri definite și având cea mai mică lungime între toate astfel de secvențe.
La prima vedere, se pare că putem folosi algoritmul pentru construirea MOU să scadă coaste în plus, și apoi să ia calea pe care se conectează un anumit nod din arborele de acoperire construit. Din păcate, astfel de acțiuni nu conduc întotdeauna la rezultatul dorit.
Să ne amintim că algoritmul pentru construirea MOU se concentrează pe găsirea unui copac, cu o greutate totală minimă a aripioarelor. Luați în considerare, de exemplu, pentru „wrap“ grafic, adică un grafic în care primul Vertex conectat la al doilea, al doilea - al treilea, și așa mai departe, și ultimul vârf, la rândul său conectat la primul. Un astfel de grafic este pur și simplu un inel, în care fiecare nod este conectat la alte două. Un exemplu de un astfel de grafic cu șase vârfuri este prezentată în Fig. 1 (a).
Vă rugăm să rețineți că greutatea fiecărei muchii este egală cu 1, cu excepția marginea de conectare noduri A și B, greutatea care este egală cu 2. Un algoritm pentru construirea unui arbore minim se întinde selectează toate marginile de greutate 1, aruncând doar greutatea marginii 2. Aceasta înseamnă, totuși, că modul în care de la o la b in arborele minim se întinde trebuie să treacă prin toate celelalte vârfuri, iar lungimea sa este egală cu 5 (Fig. 1 (b)). In mod evident, nu este cel mai scurt, ca și în original, graficul nodurile A și B sunt conectate printr-o lungime a muchiei de 2.
Algoritmul lui Dijkstra
Un algoritm greedy pentru construirea unui arbore de acoperire minim nu este potrivit pentru a găsi calea cea mai scurtă dintre două noduri pe fiecare trecere, deoarece ia în considerare numai lungimea unei margini. Dacă vom schimba, astfel încât atunci când selectați marginile, ceea ce duce la bordura, el a ales nervura, care face parte din calea cea mai scurtă în întreaga cale de la vârful inițial, vom obține rezultatul dorit. Mai precis, acest algoritm modificat: Fig. 2 prezintă un exemplu de execuție a algoritmului. Algoritmul ruleaza pe același grafic (fig. 2 (a)), și că algoritmul pentru construirea unui minim care acoperă copac, și vom căuta calea cea mai scurtă de la A la G.
La începutul vârful A, avem patru posibile margine. Dintre cele patru margini AB este cea mai scurtă margine. Prin urmare, vom adăuga la partea de sus a arborelui B (fig. 2 (c)) și a vedea cum să actualizeze setul de căi. Cu copac deja construit este acum conectat la partea de sus a E și G, și, prin urmare, acestea ar trebui să fie adăugate la tiv. Mai mult decât atât, trebuie să ne uităm la vârf D și comparați calea directă de la ea la A, a cărei lungime este egală cu 7, un ocol prin vârful B, a cărei lungime este egală cu 8. calea directă este mai scurt, astfel încât alocate nu ar trebui să fie schimbat la D coaste. Acum studiem oportunitățile disponibile, vom vedea că este calea cea mai scurtă de la A la C, de lungime 4. Edge fi mai scurt, cu toate acestea, considerăm că întreaga lungime a traseului de la A, și o cale de lider pe E, are o lungime de 5. Acum la copac scurt-cale adaugă vertex C (Fig. 2 (d)). Privind la grafic, descoperim că putem merge la partea de sus a F prin vârful C, dar acest lucru este lungimea drumului este egală cu 10 - mai mult decât calea directă de la A la F, astfel încât schimbarea nu este făcută într-un set de căi.
Fig. 2 (g) acum putem selecta fie o cale de la A la F, orice cale de la A la E, care trece prin vârful B: ambele au o lungime de 5. Care dintre căile vor fi selectate în executarea programului depinde de metoda de stocare a datelor în acesta. Tocmai ne-am întâlnit cu nevoia de a adăuga un nod, vom alege întotdeauna partea de sus, eticheta este primul în ordinea lexicografică.
Rezultatul este o situație din Fig. 2 (d). Adăugarea la copac topuri E nu se schimba restul link-uri, astfel încât acum putem adăuga un vârf F, și a obține o imagine cu figura. 2 (e). Rețineți că, deși adăugarea de vârful F și a dus la o schimbare în coaste, ceea ce duce la D, dacă am început cu F, toate la fel, la pasul următor, trebuie să adăugați E.
Fig. 2 (e) arată că drumul spre vârful D mai scurt decât calea spre vârful G. Prin urmare, se adaugă la partea de sus a arborelui D și de a obține situația prezentată în Fig. 2 (g). Rămâne să adăugați numai partea de sus G, și, ca rezultat vom obține cel mai scurt drum de la copac Fig. 2 (h). Lungimea cea mai scurtă cale de la A la G este egal cu 10.
Pe exemplul din Fig. 2, avem de-a face cu un copac plin de căi ca cele mai scurte vârful țintă G a fost adăugat la ultimul copac. Dacă am ajuns la ea înainte, algoritmul ar fi încheiat activitatea imediat. Pot exista situații în care ne interesează în cel mai scurt drum de la un anumit vârf tuturor celorlalte. Dacă, de exemplu, avem de-a face cu o rețea de calculatoare mici, viteza de transmitere a datelor între nodurile care sunt aproximativ constante, atunci pentru fiecare dintre calculatoarele din rețea, putem alege calea cea mai scurtă la fiecare dintre celelalte computere. Prin urmare, dacă este necesar, transmite mesajul către singurul lucru de care avem nevoie este de a profita de precalculați cel mai eficient mod.