نمودارها در پایتون – تئوری و پیاده سازی

الگوریتم دایکسترا طراحی شده برای یافتن کوتاه ترین مسیرهای بین گره ها در یک نمودار. این توسط یک دانشمند کامپیوتر هلندی، Edsger Wybe Dijkstra، در سال 1956، زمانی که در حال بررسی کوتاه ترین مسیر از روتردام به گرونینگن بود، طراحی شد. سه سال بعد منتشر شد.

در این درس، نگاهی به الگوریتم Dijkstra، شهود پشت آن و سپس پیاده سازی آن در پایتون خواهیم داشت.

الگوریتم دایکسترا – نظریه و شهود

الگوریتم دایکسترا کار می کند روی نمودارهای بدون جهت، متصل، وزن دار.

در ابتدا، ما می خواهیم مجموعه ای از رئوس بازدید شده ایجاد کنیم تا تمام رئوس هایی را که کوتاه ترین مسیر صحیح به آنها اختصاص داده شده است، پیگیری کنیم. همچنین باید «هزینه‌ها» را برای تمام رئوس در نمودار (طول کوتاه‌ترین مسیر فعلی که به آن منتهی می‌شود) تنظیم کنیم.

تمام هزینه ها تعیین خواهد شد ‘بی نهایت’ در ابتدا ، برای اطمینان از این که هر هزینه دیگری که ممکن است آن را با آن مقایسه کنیم ، کوچکتر از شروع است. تنها استثناء هزینه اول ، شروع راس است – این راس هزینه 0 خواهد داشت ، زیرا هیچ راهی برای خودش ندارد – node s.

سپس ، ما دو مرحله اصلی را تا زمانی که نمودار طی شود تکرار می کنیم (تا زمانی که راس ها بدون کوتاهترین مسیر اختصاص داده شده برای آنها وجود داشته باشد):

• ما یک راس را با کمترین هزینه فعلی انتخاب می کنیم ، از آن بازدید می کنیم و آن را به مجموعه رئوس های بازدید شده اضافه می کنیم.
• ما هزینه های تمام رئوس های مجاور آن را که هنوز بازدید نشده است به روز می کنیم. برای هر لبه بین n و m جایی که m بازدید نشده است – اگر cheapestPath(s, n) + cheapestPath(n,m) < cheapestPath(s,m)، به روز رسانی ارزان ترین مسیر بین s و m برابر کردن cheapestPath(s,n) + cheapestPath(n,m).

از آنجا که این ممکن است کمی دشوار باشد که سر خود را بپیچید – بیایید process قبل از اجرای آن! در اینجا یک نمودار بدون جهت، وزن دار و متصل آمده است:

این را بگوییم راس 0 نقطه شروع ما است ما قصد داریم هزینه های اولیه راس ها را در این نمودار به Infinity تنظیم کنیم ، به جز راس شروع:

راس	هزینه رسیدن به آن از راس 0
0	0
1	inf
2	inf
3	inf
4	inf
5	inf
6	inf
7	inf
8	inf

ما راس را با حداقل هزینه انتخاب می کنیم – یعنی راس 0. ما آن را به عنوان بازدید شده علامت گذاری می کنیم و به مجموعه رئوس بازدید شده خود اضافه می کنیم. شروع node اراده همیشه کمترین هزینه را داشته باشید تا همیشه اولین کسی باشد که اضافه می شود:

سپس ، هزینه رئوس های مجاور (1 و 6) را به روز خواهیم کرد. از آنجا که 0 + 4 < infinity و 0 + 7 < infinity، ما هزینه ها را به این رئوس به روز می کنیم:

راس	هزینه رسیدن به آن از راس 0
0	0
1	4
2	inf
3	inf
4	inf
5	inf
6	7
7	inf
8	inf

اکنون از کوچکترین راس هزینه بعدی بازدید می کنیم. وزن از 4 کمتر از 7 بنابراین ما به راس 1:

پس از پیمایش، آن را به عنوان بازدید شده علامت گذاری می کنیم و سپس رئوس مجاور را مشاهده و به روز می کنیم: 2، 6، و 7:

• از آنجا که 4 + 9 < infinity، هزینه جدید راس 2 13 خواهد بود
• از آنجا که 4 + 11 > 7، هزینه راس 6 7 باقی می ماند
• از آنجا که 4 + 20 < infinity، هزینه جدید راس 7 24 خواهد بود

اینها هزینه های جدید ما هستند:

راس	هزینه رسیدن به آن از راس 0
0	0
1	4
2	13
3	inf
4	inf
5	inf
6	7
7	24
8	inf

راس بعدی که قرار است از آن بازدید کنیم این است راس 6. ما آن را به عنوان بازدید شده علامت گذاری می کنیم و هزینه های رئوس مجاور آن را به روز می کنیم:

راس	هزینه رسیدن به آن از راس 0
0	0
1	4
2	13
3	inf
4	inf
5	inf
6	7
7	8
8	inf

این process ادامه دارد به راس 7:

راس	هزینه رسیدن به آن از راس 0
0	0
1	4
2	13
3	inf
4	9
5	inf
6	7
7	8
8	11

و دوباره، به راس 4:

راس	هزینه رسیدن به آن از راس 0
0	0
1	4
2	11
3	19
4	9
5	24
6	7
7	8
8	11

و دوباره، به راس 2:

تنها رأسی که می خواهیم در نظر بگیریم این است راس 3. از آنجا که 11 + 6 < 19، هزینه راس 3 به روز می شود.

سپس، به ادامه می‌دهیم راس 8:

در نهایت، ما در حال به روز رسانی راس 5:

راس	هزینه رسیدن به آن از راس 0
0	0
1	4
2	11
3	17
4	9
5	24
6	7
7	8
8	11

ما رئوس ساختار حلقه مانند را در پایان به روز کرده ایم – بنابراین اکنون فقط باید از آن عبور کنیم – ابتدا راس 3:

و در نهایت، به راس 5:

هیچ رئوس بازدید نشده دیگری وجود ندارد که ممکن است نیاز به به روز رسانی داشته باشد. هزینه های نهایی ما نشان دهنده کوتاه ترین مسیرها است node 0 به هر دیگری node در نمودار:

راس	هزینه رسیدن به آن از راس 0
0	0
1	4
2	11
3	17
4	9
5	24
6	7
7	8
8	11

شما می توانید این جدول را هرس کنید و فقط فاصله بین *گره X* و *گره Y* را حفظ کنید، هرچند، به هر حال باید این محاسبه را اجرا کنید تا واقعاً هزینه محاسباتی را کاهش ندهید.

پیاده سازی الگوریتم Dijkstra در پایتون

حالا که مرحله به مرحله را مرور کردیم process، بیایید ببینیم چگونه می توانیم الگوریتم Dijkstra را در پایتون پیاده سازی کنیم! برای مرتب‌سازی و پیگیری رئوس‌هایی که هنوز بازدید نکرده‌ایم – از a استفاده می‌کنیم PriorityQueue:

from queue import PriorityQueue

اکنون یک سازنده برای کلاسی به نام پیاده سازی می کنیم Graph:

class Graph:
    def __init__(self, num_of_vertices):
        self.v = num_of_vertices
        self.edges = ((-1 for i in range(num_of_vertices)) for j in range(num_of_vertices))
        self.visited = ()

در این سازنده پارامتری ساده، تعداد رئوس نمودار را به عنوان آرگومان ارائه کردیم و سه فیلد را مقداردهی اولیه کردیم:

• v: تعداد رئوس نمودار را نشان می دهد.
• edges: فهرست یال ها را به صورت ماتریس نشان می دهد. برای گره ها u و v، self.edges(u)(v) = weight از لبه
• visited: مجموعه ای که شامل رئوس بازدید شده است.

حالا بیایید تابعی را تعریف کنیم که یک یال به نمودار اضافه می کند:

    def add_edge(self, u, v, weight):
        self.edges(u)(v) = weight
        self.edges(v)(u) = weight

با تعریف گراف ما خارج از مسیر – بیایید الگوریتم Dijkstra را تعریف کنیم:

def dijkstra(graph, start_vertex):
    D = {v:float('inf') for v in range(graph.v)}
    D(start_vertex) = 0

    pq = PriorityQueue()
    pq.put((0, start_vertex))

    while not pq.empty():
        (dist, current_vertex) = pq.get()
        graph.visited.append(current_vertex)

        for neighbor in range(graph.v):
            if graph.edges(current_vertex)(neighbor) != -1:
                distance = graph.edges(current_vertex)(neighbor)
                if neighbor not in graph.visited:
                    old_cost = D(neighbor)
                    new_cost = D(current_vertex) + distance
                    if new_cost < old_cost:
                        pq.put((new_cost, neighbor))
                        D(neighbor) = new_cost
    return D

در این کد ابتدا یک لیست ایجاد کردیم D از اندازه v. کل لیست به بی نهایت مقدار دهی اولیه می شود. این لیستی خواهد بود که ما کوتاه ترین مسیرها را از آن دور می کنیم start_vertex به تمام گره های دیگر

مقدار راس شروع را روی 0 قرار می دهیم، زیرا فاصله آن از خودش است. سپس، یک صف اولویت را راه‌اندازی می‌کنیم، که از آن برای مرتب‌سازی سریع راس‌ها از کمترین به دورترین استفاده می‌کنیم. راس شروع را در صف اولویت قرار می دهیم. حال، برای هر رأس در صف اولویت، ابتدا آنها را به عنوان بازدید شده علامت گذاری می کنیم و سپس از طریق همسایگان آنها تکرار می کنیم.

در صورت عدم مراجعه به همسایه هزینه قدیمی و جدید را با هم مقایسه می کنیم. هزینه قدیمی مقدار فعلی کوتاهترین مسیر از راس شروع به همسایه است، در حالی که هزینه جدید مقدار مجموع کوتاهترین مسیر از راس شروع به راس فعلی و فاصله بین راس فعلی و راس فعلی است. همسایه اگر هزینه جدید کمتر از هزینه قبلی باشد، همسایه و هزینه آن را در صف اولویت قرار می دهیم و لیستی را که کوتاه ترین مسیرها را در آن نگه می داریم، به روز می کنیم.

در نهایت، پس از بازدید همه رئوس و خالی شدن صف اولویت، لیست را برمی گردانیم D.

بیایید نموداری را که قبلاً برای تأیید مراحل دستی خود استفاده کرده‌ایم مقداردهی اولیه کنیم و الگوریتم را آزمایش کنیم:

g = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 6, 7)
g.add_edge(1, 6, 11)
g.add_edge(1, 7, 20)
g.add_edge(1, 2, 9)
g.add_edge(2, 3, 6)
g.add_edge(2, 4, 2)
g.add_edge(3, 4, 10)
g.add_edge(3, 5, 5)
g.add_edge(4, 5, 15)
g.add_edge(4, 7, 1)
g.add_edge(4, 8, 5)
g.add_edge(5, 8, 12)
g.add_edge(6, 7, 1)
g.add_edge(7, 8, 3) 

اکنون به سادگی تابعی را که الگوریتم دایکسترا را انجام می دهد فراخوانی می کنیم روی این نمودار و print از نتایج:

D = dijkstra(g, 0)

print(D)

یا، می توانیم آن را کمی زیباتر قالب بندی کنیم:

for vertex in range(len(D)):
    print("Distance from vertex 0 to vertex", vertex, "is", D(vertex))

پس از کامپایل برنامه، این خروجی را دریافت می کنیم:

Distance from vertex 0 to vertex 0 is 0
Distance from vertex 0 to vertex 1 is 4
Distance from vertex 0 to vertex 2 is 11
Distance from vertex 0 to vertex 3 is 17
Distance from vertex 0 to vertex 4 is 9
Distance from vertex 0 to vertex 5 is 22
Distance from vertex 0 to vertex 6 is 7
Distance from vertex 0 to vertex 7 is 8
Distance from vertex 0 to vertex 8 is 11

فاصله بین شروع node و یکدیگر node در درخت محاسبه و خروجی می شود.

پیچیدگی زمانی

در این الگوریتم هر یال را یک بار رد می کنیم که نتیجه آن پیچیدگی زمانی است O(|E|)، جایی که |E| تعداد لبه ها را نشان می دهد.

از هر کدام هم بازدید می کنیم node یک بار که منجر به پیچیدگی زمانی می شود O(|V|)، جایی که |V| تعداد رئوس را نشان می دهد. هر راس در یک صف اولویت قرار می گیرد، جایی که پیدا کردن نزدیکترین راس بعدی به صورت ثابت انجام می شود. O(1) زمان. با این حال، ما استفاده می کنیم O(Vlog|V|) زمان مرتب کردن رئوس در این صف اولویت است.

این منجر به پیچیدگی زمانی از وجود این الگوریتم O(|E|+|V|log|V|).