დეიქსტრას ალგორითმი

ყოველი რუკის აპლიკაცია, ქსელის მარშრუტიზატორი და თამაშის ხელოვნური ინტელექტი ერთსა და იმავეს კითხულობს: როგორ მივიდეთ აქედან ყველგან ყველაზე იაფად? როცა წიბოებს სიგრძე აქვთ, წიბოების დათვლა (BFS) აღარ კმარა, და პასუხი დეიქსტრას ალგორითმია.

★ ლექცია: Graph_Dijkstra · ზაზა გამეზარდაშვილი▶ ვიდეო საშუალო⏱ 20 წთ

←ეყრდნობა

6სიგანეში ძებნა (BFS)დეიქსტრა არის BFS, რომლის ტალღა მანძილით მოძრაობს და არა წიბოების რაოდენობით.5ორობითი გროვა და პრიორიტეტული რიგიდეიქსტრა კანდიდატ მანძილებს მინ-გროვაში ინახავს.7ხარბი იდეა და როდის ცდებადეიქსტრა ხარბია: ყოველთვის უახლოეს დაუმუშავებელ წვეროს აფიქსირებს.

გზას უხსნის→

8ბელმან-ფორდი და უარყოფითი წიბოებიბელმან-ფორდი დეიქსტრას რელაქსაციას იყენებს, ოღონდ ყველა წიბოზე იმეორებს, ამიტომ უარყოფითი წონებიც დასაშვებია.8მინიმალური დამფარავი ხე: კრასკალი და პრიმიპრიმი დეიქსტრაა სხვა გასაღებით: ხესთან უიაფესი წიბო და არა სრული მანძილი.10ფლოიდ-ვორშელი: დპ გრაფზეის ყველა წყვილს ერთად პასუხობს, მაშინ როცა დეიქსტრა ერთ საწყის წვეროს.

1ისწავლე 2უყურე 3ითამაშე 4შეამოწმე 5ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ამოცანის დასმა: უმოკლესი გზები ერთი წვეროდან

მოცემულია წონადი გრაფი (ორიენტირებული ან არაორიენტირებული), ყოველი წიბოს წონა არაუარყოფითია. მითითებული საწყისი წვეროდან უნდა ვიპოვოთ უმოკლესი მანძილები ყველა დანარჩენ წვერომდე და შესაბამისი გზები. ალგორითმი 1959 წელს აღმოაჩინა ჰოლანდიელმა მეცნიერმა ედსგერ დეიქსტრამ.

რატომ არა BFS? ლექციის გრაფში 1-დან 6-მდე ყველაზე ცოტა წიბოიანი გზა (4 წიბო) 23 ჯდება, 6-წიბოიანი კი მხოლოდ 15. გზის სიგრძე წონების ჯამია და არა წიბოების რაოდენობა.

ლექცია მსგავს ამოცანებსაც ჩამოთვლის:

ერთ v წვერომდე ყველა წვეროდან: შევუცვალოთ ყველა წიბოს მიმართულება და გავუშვათ v-დან;
წყვილი u, v: გავუშვათ u-დან (ერთი წყვილისთვის უფრო სწრაფი მეთოდი ნაპოვნი არ არის);
ყველა წყვილი: გავუშვათ ყოველი წვეროდან (ფლოიდ-ვორშელი უფრო კომპაქტურია, მაგრამ ასიმპტოტურად არ ჯობია).

ლექციის გრაფი: 9 წვერო, 14 ორიენტირებული წიბო.

02რელაქსაცია და ქვეამოცანების ოპტიმალურობა

ყოველი წვეროსთვის ვინახავთ მიმდინარე საუკეთესო შეფასებას d[v] (თავიდან ∞) და მშობელს p[v]. (a, b) წიბოს რელაქსაცია (წონით w) ნიშნავს კითხვას: ხომ არ ჯობია a-ს გავლით?

თუ d[a] + w < d[b]: d[b] = d[a] + w, p[b] = a

ლექციის მაგალითში პირდაპირი წიბო იძლევა d[b] = 12-ს; c-ს გავლით 5 + 4 = 9 < 12, ამიტომ d[b] 9-მდე მცირდება, b-ს მშობელი კი c ხდება. d-ს (17) და e, f-ის (14) გავლით გზები ვერ გვეხმარება.

რელაქსაცია საკმარისია ლემის წყალობით: თუ P = ⟨v₁, …, vₖ⟩ უმოკლესი გზაა, მისი ნებისმიერი ინტერვალი vᵢ-დან vⱼ-მდე ასევე უმოკლესი გზაა. უფრო მოკლე შემოვლითი გზა რომ არსებობდეს, მისი ჩასმით P დამოკლდებოდა. ე.ი. უმოკლესი გზები უმოკლესი გზებისგან შედგება.

03ალგორითმი: ჯერ უახლოესი მოუნიშნავი წვერო

ლექცია თითო წვეროსთვის სამ სტრიქონს ინახავს: მანძილი, მშობელი, ფერი (0 მიუღწეველი, 1 გროვაშია, 2 მონიშნული), და მინ-გროვას (მანძილი, წვერო) წყვილებით. დასაწყისი: d[1] = 0, გროვაში (0, 1).

ყოველი იტერაცია: ამოვიღოთ უმცირესი წყვილი (d, u), მოვნიშნოთ u და ვცადოთ მისგან გამომავალი ყველა წიბოს რელაქსაცია; როცა d[v] უმჯობესდება, გროვაში ვდებთ (d[v], v)-ს. თუ ამოღებული წვერო უკვე მონიშნულია, წყვილი მოძველებულია: გამოვტოვებთ.

ეს ხარბი ალგორითმია, ზუსტად მე-7 ეტაპის იდეა: ირჩევს უახლოეს მოუნიშნავ წვეროს და მას აღარასდროს უბრუნდება. ლექციის გრაფზე მე-3 იტერაციის შემდეგ მონიშნულია 1, 7, 2; გროვაში დევს (5,3) (8,3) (11,4) (12,4), და (8,3) მოგვიანებით მოძველებულად ამოვა, რადგან 3-მდე მანძილი 7-ის გავლით 8-დან 5-მდე შემცირდა.

წვეროების ქვეშ მიმდინარე d[] მნიშვნელობებია; ლურჯი წიბოები მშობლის კავშირებია.

04გზის აღდგენა: უმოკლესი მანძილების ხე

9 იტერაციის შემდეგ გროვა ცარიელია და ცხრილი საბოლოოა: მანძილები 0 4 5 10 7 15 3 11 8 წვეროებისთვის 1…9, მშობლები Nil 1 7 9 3 8 1 9 5.

6-მდე გზის აღსადგენად მშობლებს მივყვეთ საწყის წვერომდე: 6 ← 8 ← 9 ← 5 ← 3 ← 7 ← 1, ჯამში 15. ლექციის path(n) ამას რეკურსიულად აკეთებს: ჯერ საკუთარ თავს იძახებს parent[n]-ზე, მერე ბეჭდავს n-ს, ამიტომ გზა სწორი რიგით გამოდის.

ლემა (სლაიდი 18): მშობლის კავშირები ქმნის ხეს სათავით საწყის წვეროში, უმოკლესი მანძილების ხეს. ყოველ მისაღწევ წვეროს ზუსტად ერთი მშობელი ჰყავს (9 წვეროსთვის 8 კავშირი), ამიტომ 1-მდე ერთადერთი გზა აქვს. დეიქსტრას ერთი გაშვება ყველა წვეროსთვის ერთად პასუხობს: „რა მანძილია?“ და „რომელი გზით?“.

05რატომ მუშაობს, რა ღირს და სად ტყდება

სისწორე (ინდუქციით, როგორც ლექციაში): d[s] = 0 სწორია. დავუშვათ, ყველა მონიშნული წვერო სწორია და ალგორითმი ახლა ირჩევს b-ს. b-მდე ნებისმიერი სხვა გზა მონიშნულ სიმრავლეს რომელიმე მოუნიშნავი x-ით ტოვებს, სადაც d[x] ≥ d[b], ხოლო არაუარყოფითი წონებით გზის დარჩენილი ნაწილი მხოლოდ ზრდის სიგრძეს. ე.ი. d[b] საბოლოოა.

ასიმპტოტიკა: |V| იტერაცია და სულ |E| რელაქსაციის მცდელობა. ორობითი გროვით (priority_queue greater<>-ით, როგორც ლექციის კოდში) ეს O((V + E) log V)-ია; ფიბონაჩის გროვით O(E + V log V).

მახე: ერთი უარყოფითი წიბოც ანგრევს ინდუქციას. ქვემოთ A მოინიშნა 2-ით, მაგრამ S→B→A = 4 − 3 = 1. უარყოფითი წონებისთვის საჭიროა ბელმან-ფორდი, შემდეგი თემა.

ლექციის C++ კოდიC++

მე-20, 21 და 22 სლაიდები ერთ პროგრამად: greater-იანი priority_queue წყვილებს {მანძილი, წვერო} მინიმალური გროვის სახით ინახავს, parent[] კი path() ფუნქციას 1-ლი წვეროდან n-ურამდე გზის დაბეჭდვის საშუალებას აძლევს. გაშვებამდე ორი რამ უნდა იცოდე. პირველი: main() ყოველ წიბოს ორივე მიმართულებით ამატებს, ანუ გრაფს არაორიენტირებულად განიხილავს: ლექციის ორიენტირებულ მაგალითზე ეს d[6] = 13-ს იძლევა 15-ის ნაცვლად. სლაიდის ორიენტირებული გრაფისთვის მეორე push_back წაშალე. მეორე: სლაიდის კოდი რიგში დარჩენილ მოძველებულ წყვილებს არ ამოწმებს. pop-ის წინ წაიკითხე long long d = q.top().first;, მის შემდეგ კი დაამატე if (d > dis[u]) continue;, რომ წვერო, რომლის მანძილიც უკვე გაუმჯობესდა, ხელახლა არ დამუშავდეს.

#include<bits/stdc++.h>
#define inf 1000000000000
using namespace std;
vector < pair<int, int> >g[1000000];
long long dis[1000000], parent[1000000];
int n, m;
void path(int n) {
    if(n!=1) path(parent[n]);
    cout<<n<<" ";
}
void dijkstra(){
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    for(int i=0; i<=n; i++) dis[i]=inf;
    dis[1]=0;
    q.push({0, 1});
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        for(int i=0; i<g[u].size(); i++){
            int v=g[u][i].first;
            int w=g[u][i].second;
            if(dis[u]+w < dis[v]){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
                parent[v]=u;
            }
        }
    }
}
int main(){
    int u, v, w;
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dijkstra();
    if(dis[n]==inf) cout<<"-1";
    else path(n);
}

ფასი ერთი შეხედვით

ორობითი გროვა (priority_queue)O((V + E) log V)

ფიბონაჩის გროვაO(E + V log V)

ერთ წვერომდე გზის აღდგენაO(path length)

მეხსიერებაO(V + E)

დაიმახსოვრე

დეიქსტრა მინ-გროვიდან ყოველთვის უახლოეს მოუნიშნავ წვეროს იღებს; მონიშვნის შემდეგ მისი მანძილი საბოლოოა.
რელაქსაცია d[v] = min(d[v], d[u] + w) და მშობლის მიმთითებლები ერთად გვაძლევს მანძილებსაც და უმოკლესი მანძილების ხესაც.
ეს ხარბი ალგორითმია და არაუარყოფით წონებს საჭიროებს; უარყოფითი წიბოებისას გამოიყენე ბელმან-ფორდი.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე მინ-გროვას: პირველი წყვილი ყოველთვის შემდეგი მოსანიშნი წვეროა. შეადარე ყოველი ცხრილი ლექციის სლაიდებს 7–15.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

ორიენტირებული წონადი გრაფი (საწყისი წვერო: 1)

0: მიუღწეველი1: გროვაშია2: მონიშნულიუმოკლესი მანძილების ხე

მინ-გროვა (მანძილი, წვერო)

(0, 1)

მდგომარეობა

v	1	2	3	4	5	6	7	8	9
მანძილი	0	∞	∞	∞	∞	∞	∞	∞	∞
მშობელი	nil	∞	∞	∞	∞	∞	∞	∞	∞
ფერი	1	0	0	0	0	0	0	0	0

ინიციალიზაცია: dist[1] = 0, დანარჩენი მანძილები ∞-ია, მშობლები Nil. მინ-გროვაში ვდებთ წყვილს (0, 1).

ფსევდოკოდი

 1 dist[*]=∞; dist[s]=0; heap.push((0,s)) 2 while (!heap.empty()) { 3   (du, u) = heap.popMin() 4   if (u is marked) continue  // stale pair 5   mark u  // dist[u] is provably shortest 6   for (edge u→v with weight w) { 7     if (dist[u] + w >= dist[v]) skip 8     dist[v] = dist[u]+w; p[v] = u 9     heap.push((dist[v], v))10 } }  // relaxation / რელაქსაცია

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

ლექციის გრაფი: 1-ის მონიშვნის შემდეგ d[3] = 8. შემდეგ მოინიშნა 7 (d = 3), 7→3 წიბოს წონა 2-ია. რას უდრის ახლა d[3]?

№2

გროვიდან ამოვიდა (8, 3), მაგრამ წვერო 3 უკვე მონიშნულია მანძილით 5. რას აკეთებს ალგორითმი?

№3

რატომ შეიძლება უარყოფითმა წიბომ დეიქსტრა შეაცდინოს?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeNetwork Delay Time საშუალო↗CSESShortest Routes I საშუალო↗LeetCodePath With Minimum Effort საშუალო↗CSESFlight Discount მოწინავე↗