برنامه‌ریزی تا کنکور ارشد و دکتری: مشاوره خصوصیت با استاد رضوی رو رزرو کن!
ویس توضیحات مشاوره رزرو مشاوره
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

0 تا 100 الگوریتم دایجسترا (Dijkstra)، الگوریتم دایکسترا

این صفحه الگوریتم دایجسترا (Dijkstra) (یا همان الگوریتم دایکسترا) را از 0 تا 100 بررسی کرده، همین طور به پیاده سازی و آموزش الگوریتم دایجسترا پرداخته است.

الگوریتم دایجسترا چیست؟ در این مقاله به الگوریتم دایجسترا (Dijkstra's Algorithm) که یکی از الگوریتم‌های مهم نظریه گراف است، می‌پردازیم. این الگوریتم کاربردهای زیادی در فناوری‌های امروزی مانند مسیریابی در نقشه و شبکه های کامپیوتری و ... دارد. در ادامه ابتدا به معرفی و مرور مختصری از درس گراف و هر آنچه برای یادگیری الگوریتم دایجسترا نیاز دارید، پرداخته و سپس وارد شرح این الگوریتم خواهیم شد. همچنین برای مطالعه بیشتر در مورد اینکه بطورکلی الگوریتم چیست و آشنایی با انواع الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد ها به صفحه مذکور مراجعه کنید، همچنین برای آشنایی و یادگیری طراحی الگوریتم و ساختمان داده می‌توانید به صفحه ساختمان دادهآموزش ساختمان داده و الگوریتمآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است و طراحی الگوریتمآموزش طراحی الگوریتم به زبان سادهآموزش طراحی الگوریتم به زبان سادهدرس طراحی الگوریتم‌ یکی از مهم‌ترین و بنیادیترین دروس‌ رشته کامپیوتر است. هدف از این درس، معرفی روش‌های مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است. مراجعه فرمائید.

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

فیلم الگوریتم دایجسترا

آشنایی با گراف

گراف ها، ساختمان داده هایی هستند که برای نمایش ارتباط بین هر جفت عنصر بکار می‌روند. به این عناصر گره گراف یا نود گراف (Node) گفته می‌شود.  نودها در گراف نمایش دهنده‌ی شی‌ها، اشخاص و موجودیت‌ها در زندگی واقعی ما هستند. به ارتباط بین نودها، یال گراف (Edge) گفته می‌شود. شکل زیر یک نمایش گرافیکی از گراف است.

در این تصویر یک گراف نشان داده شده است.

در شکل بالا نودها با دایره‌های رنگی و یال‌ها با خطوطی که این دایره‌ها را به هم وصل کرده‌اند، نمایش داده شده است.

توجه: دو نود با یکدیگر در ارتباط هستند (به هم متصل هستند)، اگر بین آن‌ها یک یال وجود داشته باشد

در صورتی که به یادگیری کامل گراف علاقه مند باشید می‌توانید به مقاله گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... مراجعه کنید.

کاربرد گراف

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

این تصویر برای درک مثال بالا قرار گرفته است.

انواع گراف

گراف‌ها می‌توانند جهت‌دار یا غیرجهت‌دار باشند.

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

گراف جهت دار: اگر به ازای هر جفت نود متصل، تنها بتوان از یک نود به نود دیگر در یک جهت مشخص رفت، آن گراف جهت دار است. در این مدل از گراف ما از فلش به جای خطوط ساده برای نمایش جهت یال استفاده می‌کنیم.

در این تصویر انواع گراف نشان داده شده است.

گراف وزن دار

گراف وزن دار، گرافی است که یال‌های آن دارای وزن یا هزینه هستند. وزن هر یال می‌تواند نشان دهنده‌ی فاصله، زمان یا هر چیزی که در آن مدل، دو نود را به هم متصل می‌کند باشد. به عنوان مثال در گراف وزن دار زیر شماره‌های با رنگ آبی روی هر یال نمایشگر وزن آن یال است.

در این تصویر گراف وزن دار نشان داده شده است.

الگوریتم دایجسترا یا دایکسترا – Dijkstra’s Algorithm

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

تاریخچه الگوریتم دایجسترا

این الگوریتم توسط Edsger W. Dijkstra، مهندس نرم افزار و دانشمند برجسته علوم کامپیوتر ارائه و منتشر شد. در سال 1959، او یک مقاله 3 صفحه‌ای با تیتر "A note on two problems in connexion with graphs"  منتشر کرد که در آن الگوریتم جدید خود را توضیح داد. دایجسترا در سال 2001 طی مصاحبه‌ای، چرایی و نحوه طراحی الگوریتم خود را چنین توضیح داد:

کوتاه‌ترین راه بین Rotterdam و  Groningen چیست؟ این الگوریتم برای کوتاه‌ترین مسیر است که در حدود 20 دقیقه آن را طراحی کردم! یک روز صبح، به همراه نامزدم در آمستردام، که خسته (!) در حال خرید کردن بودیم، در تراس یک کافه برای خوردن یک لیوان قهوه نشستیم. آن زمان من داشتم فکر می‌کردم که چگونه می‌توانم اینکار را انجام دهم و همانطور که گفتم به اندازه 20 دقیقه طول کشید! یکی از دلایلی که آن اتفاق برایم خیلی خوشایند آمد این بود که من این الگوریتم را بدون هیچ مداد و کاغذی در آن زمان طراحی کردم! شما بدون مداد و کاغذ مجبور هستید که از کلیه پیچیدگی‌های طراحی اجتناب کنید. در نهایت این الگوریتم، در کمال تعجب، یکی از سنگ بناهای شهرت من شد!

الگوریتم دایجسترا برای پیدا کردن کوتاه ترین مسیرهای هم مبدا

الگوریتم دایجسترا در گراف، یک روش حریصانه برای یافتن کوتاه ترین مسیر از یک مبداء واحد اتخاذ می‌کند. در این الگوریتم لازم است که وزن تمامی یال‌ها غیر منفی باشد چرا که در غیر این صورت الگوریتم قادر به حل مسأله نیست.

با فرض این که مسأله مورد نظر یافتن کوتاه ترین مسیر از گره مبداء s در گراف G=(V,E) باشد الگوریتم دایجسترا با شروع از رأس s کوتاه ترین مسیرها را از مبداء s به تمامی رئوس دیگر پیدا می‌کند. برای درک بهتر مراحل اجرای این الگوریتم به مثال زیر توجه کنید:

این تصویر مثالی از الگوریتم دایجسترا  را نشان می‌دهد.

همان‌طور که از شکل مشخص است ابتدا تمامی رئوس به غیر از منبع s با علامت‌گذاری شده‌اند. یعنی هنوز مسیری از s به آن‌ها کشف نشده است. در مرحله بعد کوتاه‌ترین مسیر بین رأس s و تمامی رئوسی که از s مستقیماً یالی به آن‌ها وجود دارد محاسبه می‌شود. رأس بعدی که انتخاب می‌شود همان رأسی است که کوتاه‌ترین مسیر را به s داشته (انتخاب حریصانه) و مراحل ذکر شده برای رأس منبع اکنون برای این رأس تکرار شده و کوتاه‌ترین مسیرها از رأس فعلی به تمامی رئوسی که از رأس مذکور مستقیماً یالی وجود دارد محاسبه می‌شود. لیستی به صورت زیر که فاصله گره‌ها تا منبع (S) را نمایش می‌دهد تهیه می‌کنیم.

در این تصویر جدولی برای حل مثال فوق نشان داده شده است.

در مرحله اول گره s را انتخاب و کوتاه‌ترین فاصله از این گره تا هر یک از گره‌های مجاور آن را محاسبه می‌کنیم و سپس بعد از محاسبه، گره s را از لیست حذف می‌کنیم. به عنوان مثال در ابتدا فاصله s تا گره a برابر بینهایت است. در گراف داده شده با عبور از مسیر با وزن 10 می‌توان از گره s به گره a رسید و از آنجایی که 10 کوچکتر از (فاصله فعلی گره s تا گره a) است پس کوتاه‌ترین فاصله از گره s تا گره a در لیست فوق، بروز می‌شود. این امر برای گره‌های b و d نیز که مجاور با s هستند رخ می‌دهد. در نهایت پس از پایان این مرحله به لیست زیر می‌رسیم:

در این تصویر جدولی برای حل مثال فوق نشان داده شده است.

گراف اولیه نیز به صورت زیر بروز می‌شود:

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

حال در لیست جدیدِ بدست آمده (مرحله 2) گره با فاصله min، که در اینجا گره a است، را انتخاب کرده و مراحل فوق را روی آن انجام می‌دهیم. یعنی گره a را انتخاب و کوتاه‌ترین فاصله از این گره تا هر یک از گره‌های مجاور آن را محاسبه می‌کنیم و سپس بعد از محاسبه، گره a را از لیست حذف می‌کنیم.

تنها گره مجاور a نود c است که با هزینه 50 می‌توان به آن رفت. همچنین بر اساس لیست، فاصله گره منبع تا c برابر بینهایت است. با گذر از یال با وزن 50 که بین دو گره a و c است، می‌توان با مجموع 60 (10 + 50) از گره s به گره a و سپس به گره c رسید. از آنجایی که 60 از کوچکتر است میبایست لیست و گراف داده شده را بروز کرد.

در مرحله بعد گراف اولیه ما به این مرحله می‌رسد.

حال در لیست جدیدِ بدست آمده (مرحله 3) گره با فاصله min، که در اینجا گره d است، را انتخاب کرده و مراحل فوق را روی آن انجام می‌دهیم. یعنی گره d را انتخاب و کوتاه‌ترین فاصله از این گره تا هر یک از گره‌های مجاور آن را محاسبه می‌کنیم و سپس بعد از محاسبه، گره d را از لیست حذف می‌کنیم.

گره‌های مجاور d، c و b هستند. از گره منبع تا گره d به اندازه 30تا هزینه دارد. حال اگر بخواهیم در ادامه‌اش از گره d به گره b برویم با توجه به اینکه هزینه d تا b برابر 60 است، در نتیجه هزینه مسیر s->d->b برابر 30 + 60 یعنی 90 است. این هزینه کمتر از هزینه مسیر فعلی‌اش یعنی مسیر s->b است. در نتیجه مسیر با هزینه کمتر را در لیست و گراف‌مان بروز می‌کنیم.

حال اگر بخواهیم بعد از اینکه از گره منبع به گره d آمدیم، از d به c برویم، با توجه به اینکه هزینه d تا c برابر 20 است در نتیجه هزینه مسیر s->d->c برابر 30 + 20 یعنی 50 است. این هزینه کمتر از هزینه مسیر فعلی‌اش یعنی مسیر s->a->c است. در نتیجه مسیر با هزینه کمتر را در لیست و گراف‌مان بروز می‌کنیم. به شکل زیر توجه کنید.

در مرحله سوم گراف اولیه ما به این حالت می رسد.

حال در لیست جدیدِ بدست آمده (مرحله 4) گره با فاصله min، که در اینجا گره c است، را انتخاب کرده و مراحل فوق را روی آن انجام می‌دهیم. یعنی گره c را انتخاب و کوتاه‌ترین فاصله از این گره تا هر یک از گره‌های مجاور آن را محاسبه می‌کنیم و سپس بعد از محاسبه، گره c را از لیست حذف می‌کنیم.

تنها گره مجاور c نود b است که با هزینه 10 می‌توان به آن رفت. حال با توجه به اینکه کوتاه‌ترین مسیر از منبع تا نود c برابر 50 است (بر اساس آخرین بروز رسانی لیست) در نتیجه می‌توان با رفتن از گره c به b، یعنی با هزینه 50 + 10 = 60، از گره منبع به گره b رفت. (s->d->c->b)

از آنجایی که 60 از 90 کوچکتر است میبایست لیست و گراف داده شده را بروز کرد.

اکنون با حذف گره c از لیست فاصله‌ها، الگوریتم دایجسترا خاتمه میابد و در نهایت گراف و لیست زیر را خواهیم داشت.

در مرحله چهارم گراف اولیه ما به این حالت می رسد.

در گراف بدست آمده یال‌های قرمز رنگ کوتاه‌ترین مسیرها از گره منبع تا هر یک از گره‌های گراف هستند.

در پایان گراف ما به این حالت درمی‌آید.

فیلم آموزشی الگوریتم دایجسترا

0 تا 100 الگوریتم دایجسترا با ساده ترین بیان ممکن توسط استاد رضوی

شبه کد الگوریتم دایجسترا

برای نوشتن شبه کد الگوریتم دایجسترا نیاز به ذخیره‌سازی فاصله مسیر برای هر راس داریم. از این رو آرایه ای به اندازه v تعریف می‌کنیم (v برابر تعداد رئوس گراف است). همچنین برای دریافت راس با کمترین فاصله مسیر می‌توان از یک صف اولویت استفاده کرد.

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

 
function Dijkstra (G, S)
  for each vertex V in G
    distance[V] <- infinite
    previous[V] <- NULL
    If V != S, add V to Priority Queue Q
  distance[S] <- 0

  while Q IS NOT EMPTY
    U <- Extract MIN from Q
    for each unvisited neighbor V of U
      tempDistance <- distance[U] + edge_weight(U, V)
      if tempDistance < distance[V]
        distance[V] <- tempDistance
        previous[V] <- U
  return distance[], previous[]

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

پیچیدگی الگوریتم دایجسترا

برای فهم پیچیدگی زمانی الگوریتم دایجسترا باید گفت که این الگوریتم مشابه الگوریتم پریم دارای 3 پیاده‌سازی متفاوت است.

  1.  آرایه دو بعدی : با پیچیدگی زمانی $O({\upsilon }^{\mathrm{2}})$
  2. صف اولویت یا Heap : با پیچیدگی زمانی $O(E{\mathrm{log} \upsilon \ })$
  3. هیپ فیبوناچی : با زمان سرشکنی $O(E+\upsilon {\mathrm{log} \upsilon \ })$

همچنین میتوان گفت که پیچیدگی فضایی الگوریتم دایجسترا برابر $O(v)$ است.

کد الگوریتم دایجسترا در پایتون

پیاده سازی الگوریتم دایجسترا با آرایه

 
				  
# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph
 
# Library for INT_MAX
import sys
 
 
class Graph():
 
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]
 
    def printSolution(self, dist):
        print("Vertex \tDistance from Source")
        for node in range(self.V):
            print(node, "\t", dist[node])
 
    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):
 
        # Initialize minimum distance for next node
        min = sys.maxsize
 
        # Search not nearest vertex not in the
        # shortest path tree
        for u in range(self.V):
            if dist[u] < min and sptSet[u] == False:
                min = dist[u]
                min_index = u
 
        return min_index
 
    # Function that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):
 
        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V
 
        for cout in range(self.V):
 
            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # x is always equal to src in first iteration
            x = self.minDistance(dist, sptSet)
 
            # Put the minimum distance vertex in the
            # shortest path tree
            sptSet[x] = True
 
            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shortest path tree
            for y in range(self.V):
                if self.graph[x][y] > 0 and sptSet[y] == False and \
                        dist[y] > dist[x] + self.graph[x][y]:
                    dist[y] = dist[x] + self.graph[x][y]
 
        self.printSolution(dist)
 
 
# Driver's code
if __name__ == "__main__":
    g = Graph(9)
    g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
               [4, 0, 8, 0, 0, 0, 0, 11, 0],
               [0, 8, 0, 7, 0, 4, 0, 0, 2],
               [0, 0, 7, 0, 9, 14, 0, 0, 0],
               [0, 0, 0, 9, 0, 10, 0, 0, 0],
               [0, 0, 4, 14, 10, 0, 2, 0, 0],
               [0, 0, 0, 0, 0, 2, 0, 1, 6],
               [8, 11, 0, 0, 0, 0, 1, 0, 7],
               [0, 0, 2, 0, 0, 0, 6, 7, 0]
               ]
 
    g.dijkstra(0)

خروجی کد:


Vertex          Distance from Source
0                  0
1                  4
2                  12
3                  19
4                  21
5                  11
6                  9
7                  8
8                  14

فضای کمکی: $O(v)$

پیچیدگی زمانی: $O(v^2)$

توجه:

  • کد نوشته شده کوتاه‌ترین فاصله را محاسبه می‌کند اما اطلاعات مسیر را حفظ نمی‌کند.
  • کد نوشته شده برای گراف بدون جهت است. همان تابع Dijkstra را می‌توان برای گراف جهت دار نیز استفاده کرد.

اگر گراف ورودی با استفاده از لیست مجاورت نمایش داده شود، می‌توان مرتبه آن را با کمک یک Binary Heap  به O(E * log V) کاهش داد.

پیاده سازی الگوریتم دایجسترا با لیست مجاورتی

 
# A Python program for Dijkstra's shortest
# path algorithm for adjacency
# list representation of graph
 
from collections import defaultdict
import sys
 
 
class Heap():
 
    def __init__(self):
        self.array = []
        self.size = 0
        self.pos = []
 
    def newMinHeapNode(self, v, dist):
        minHeapNode = [v, dist]
        return minHeapNode
 
    # A utility function to swap two nodes
    # of min heap. Needed for min heapify
    def swapMinHeapNode(self, a, b):
        t = self.array[a]
        self.array[a] = self.array[b]
        self.array[b] = t
 
    # A standard function to heapify at given idx
    # This function also updates position of nodes
    # when they are swapped.Position is needed
    # for decreaseKey()
    def minHeapify(self, idx):
        smallest = idx
        left = 2*idx + 1
        right = 2*idx + 2
 
        if (left < self.size and
           self.array[left][1]
            < self.array[smallest][1]):
            smallest = left
 
        if (right < self.size and
           self.array[right][1]
            < self.array[smallest][1]):
            smallest = right
 
        # The nodes to be swapped in min
        # heap if idx is not smallest
        if smallest != idx:
 
            # Swap positions
            self.pos[self.array[smallest][0]] = idx
            self.pos[self.array[idx][0]] = smallest
 
            # Swap nodes
            self.swapMinHeapNode(smallest, idx)
 
            self.minHeapify(smallest)
 
    # Standard function to extract minimum
    # node from heap
    def extractMin(self):
 
        # Return NULL wif heap is empty
        if self.isEmpty() == True:
            return
 
        # Store the root node
        root = self.array[0]
 
        # Replace root node with last node
        lastNode = self.array[self.size - 1]
        self.array[0] = lastNode
 
        # Update position of last node
        self.pos[lastNode[0]] = 0
        self.pos[root[0]] = self.size - 1
 
        # Reduce heap size and heapify root
        self.size -= 1
        self.minHeapify(0)
 
        return root
 
    def isEmpty(self):
        return True if self.size == 0 else False
 
    def decreaseKey(self, v, dist):
 
        # Get the index of v in  heap array
 
        i = self.pos[v]
 
        # Get the node and update its dist value
        self.array[i][1] = dist
 
        # Travel up while the complete tree is
        # not heapified. This is a O(Logn) loop
        while (i > 0 and self.array[i][1] <
                  self.array[(i - 1) // 2][1]):
 
            # Swap this node with its parent
            self.pos[ self.array[i][0] ] = (i-1)//2
            self.pos[ self.array[(i-1)//2][0] ] = i
            self.swapMinHeapNode(i, (i - 1)//2 )
 
            # move to parent index
            i = (i - 1) // 2;
 
    # A utility function to check if a given
    # vertex 'v' is in min heap or not
    def isInMinHeap(self, v):
 
        if self.pos[v] < self.size:
            return True
        return False
 
 
def printArr(dist, n):
    print ("Vertex\tDistance from source")
    for i in range(n):
        print ("%d\t\t%d" % (i,dist[i]))
 
 
class Graph():
 
    def __init__(self, V):
        self.V = V
        self.graph = defaultdict(list)
 
    # Adds an edge to an undirected graph
    def addEdge(self, src, dest, weight):
 
        # Add an edge from src to dest.  A new node
        # is added to the adjacency list of src. The
        # node is added at the beginning. The first
        # element of the node has the destination
        # and the second elements has the weight
        newNode = [dest, weight]
        self.graph[src].insert(0, newNode)
 
        # Since graph is undirected, add an edge
        # from dest to src also
        newNode = [src, weight]
        self.graph[dest].insert(0, newNode)
 
    # The main function that calculates distances
    # of shortest paths from src to all vertices.
    # It is a O(ELogV) function
    def dijkstra(self, src):
 
        V = self.V  # Get the number of vertices in graph
        dist = []   # dist values used to pick minimum
                    # weight edge in cut
 
        # minHeap represents set E
        minHeap = Heap()
 
        #  Initialize min heap with all vertices.
        # dist value of all vertices
        for v in range(V):
            dist.append(1e7)
            minHeap.array.append( minHeap.
                                newMinHeapNode(v, dist[v]))
            minHeap.pos.append(v)
 
        # Make dist value of src vertex as 0 so
        # that it is extracted first
        minHeap.pos[src] = src
        dist[src] = 0
        minHeap.decreaseKey(src, dist[src])
 
        # Initially size of min heap is equal to V
        minHeap.size = V;
 
        # In the following loop,
        # min heap contains all nodes
        # whose shortest distance is not yet finalized.
        while minHeap.isEmpty() == False:
 
            # Extract the vertex
            # with minimum distance value
            newHeapNode = minHeap.extractMin()
            u = newHeapNode[0]
 
            # Traverse through all adjacent vertices of
            # u (the extracted vertex) and update their
            # distance values
            for pCrawl in self.graph[u]:
 
                v = pCrawl[0]
 
                # If shortest distance to v is not finalized
                # yet, and distance to v through u is less
                # than its previously calculated distance
                if (minHeap.isInMinHeap(v) and
                     dist[u] != 1e7 and \
                   pCrawl[1] + dist[u] < dist[v]):
                        dist[v] = pCrawl[1] + dist[u]
 
                        # update distance value
                        # in min heap also
                        minHeap.decreaseKey(v, dist[v])
 
        printArr(dist,V)
 
 
# Driver program to test the above functions
graph = Graph(9)
graph.addEdge(0, 1, 4)
graph.addEdge(0, 7, 8)
graph.addEdge(1, 2, 8)
graph.addEdge(1, 7, 11)
graph.addEdge(2, 3, 7)
graph.addEdge(2, 8, 2)
graph.addEdge(2, 5, 4)
graph.addEdge(3, 4, 9)
graph.addEdge(3, 5, 14)
graph.addEdge(4, 5, 10)
graph.addEdge(5, 6, 2)
graph.addEdge(6, 7, 1)
graph.addEdge(6, 8, 6)
graph.addEdge(7, 8, 7)
graph.dijkstra(0)

خروجی کد:

		  
Vertex   Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14

پیچیدگی زمانی: پیچیدگی زمانی کد بالا$O(v)$ به نظر می رسد زیرا دو حلقه while تو در تو وجود دارد. اگر نگاه دقیق‌تری بیندازیم، می‌توانیم مشاهده کنیم که دستورات در حلقه داخلی با مرتبه O(V+E) اجرا می‌شوند (مشابه BFS). حلقه داخلی دارای عملیات ()smallKey است که زمان O(LogV) را می‌گیرد. بنابراین پیچیدگی زمانی کلی O(E+V)*O(LogV) است که O((E+V)*LogV) = O(ELogV) است. توجه داشته باشید که کد بالا از Binary Heap برای اجرای صف اولویت استفاده می‌کند. پیچیدگی زمانی را می‌توان با استفاده از فیبوناچی هیپ به O(E + VLogV) کاهش داد. دلیل این امر این است که هیپ فیبوناچی برای عملیات کاهش کلید به زمان O(1) نیاز دارد در حالی که هیپ باینری به زمان O(Logn) نیاز دارد.

 

کد الگوریتم دایجسترا در جاوا


// A Java program for Dijkstra's single source shortest path
// algorithm. The program is for adjacency matrix
// representation of the graph
import java.io.*;
import java.lang.*;
import java.util.*;
 
class ShortestPath {
    // A utility function to find the vertex with minimum
    // distance value, from the set of vertices not yet
    // included in shortest path tree
    static final int V = 9;
    int minDistance(int dist[], Boolean sptSet[])
    {
        // Initialize min value
        int min = Integer.MAX_VALUE, min_index = -1;
 
        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
 
        return min_index;
    }
 
    // A utility function to print the constructed distance
    // array
    void printSolution(int dist[])
    {
        System.out.println(
            "Vertex \t\t Distance from Source");
        for (int i = 0; i < V; i++)
            System.out.println(i + " \t\t " + dist[i]);
    }
 
    // Function that implements Dijkstra's single source
    // shortest path algorithm for a graph represented using
    // adjacency matrix representation
    void dijkstra(int graph[][], int src)
    {
        int dist[] = new int[V]; // The output array.
                                 // dist[i] will hold
        // the shortest distance from src to i
 
        // sptSet[i] will true if vertex i is included in
        // shortest path tree or shortest distance from src
        // to i is finalized
        Boolean sptSet[] = new Boolean[V];
 
        // Initialize all distances as INFINITE and stpSet[]
        // as false
        for (int i = 0; i < V; i++) {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }
 
        // Distance of source vertex from itself is always 0
        dist[src] = 0;
 
        // Find shortest path for all vertices
        for (int count = 0; count < V - 1; count++) {
            // Pick the minimum distance vertex from the set
            // of vertices not yet processed. u is always
            // equal to src in first iteration.
            int u = minDistance(dist, sptSet);
 
            // Mark the picked vertex as processed
            sptSet[u] = true;
 
            // Update dist value of the adjacent vertices of
            // the picked vertex.
            for (int v = 0; v < V; v++)
 
                // Update dist[v] only if is not in sptSet,
                // there is an edge from u to v, and total
                // weight of path from src to v through u is
                // smaller than current value of dist[v]
                if (!sptSet[v] && graph[u][v] != 0
                    && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }
 
        // print the constructed distance array
        printSolution(dist);
    }
 
    // Driver's code
    public static void main(String[] args)
    {
        /* Let us create the example graph discussed above
         */
        int graph[][]
            = new int[][] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                            { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                            { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                            { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                            { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                            { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                            { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                            { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                            { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
        ShortestPath t = new ShortestPath();
 
        // Function call
        t.dijkstra(graph, 0);
    }
}

خروجی کد:


Vertex          Distance from Source
0                  0
1                  4
2                  12
3                  19
4                  21
5                  11
6                  9
7                  8
8                  14

فضای کمکی: $O(v)$

پیچیدگی زمانی: $O(v^2)$

کد الگوریتم دایجسترا در ++C


// C++ program for Dijkstra's single source shortest path
// algorithm. The program is for adjacency matrix
// representation of the graph
#include <iostream>
using namespace std;
#include <limits.h>
 
// Number of vertices in the graph
#define V 9
 
// A utility function to find the vertex with minimum
// distance value, from the set of vertices not yet included
// in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
 
    // Initialize min value
    int min = INT_MAX, min_index;
 
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
 
    return min_index;
}
 
// A utility function to print the constructed distance
// array
void printSolution(int dist[])
{
    cout << "Vertex \t Distance from Source" << endl;
    for (int i = 0; i < V; i++)
        cout << i << " \t\t\t\t" << dist[i] << endl;
}
 
// Function that implements Dijkstra's single source
// shortest path algorithm for a graph represented using
// adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
    int dist[V]; // The output array.  dist[i] will hold the
                 // shortest
    // distance from src to i
 
    bool sptSet[V]; // sptSet[i] will be true if vertex i is
                    // included in shortest
    // path tree or shortest distance from src to i is
    // finalized
 
    // Initialize all distances as INFINITE and stpSet[] as
    // false
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
 
    // Distance of source vertex from itself is always 0
    dist[src] = 0;
 
    // Find shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum distance vertex from the set of
        // vertices not yet processed. u is always equal to
        // src in the first iteration.
        int u = minDistance(dist, sptSet);
 
        // Mark the picked vertex as processed
        sptSet[u] = true;
 
        // Update dist value of the adjacent vertices of the
        // picked vertex.
        for (int v = 0; v < V; v++)
 
            // Update dist[v] only if is not in sptSet,
            // there is an edge from u to v, and total
            // weight of path from src to  v through u is
            // smaller than current value of dist[v]
            if (!sptSet[v] && graph[u][v]
                && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
 
    // print the constructed distance array
    printSolution(dist);
}
 
// driver's code
int main()
{
 
    /* Let us create the example graph discussed above */
    int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                        { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                        { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                        { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                        { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
 
    // Function call
    dijkstra(graph, 0);
 
    return 0;
}

خروجی کد:

 
Vertex          Distance from Source
0                  0
1                  4
2                  12
3                  19
4                  21
5                  11
6                  9
7                  8
8                  14
 

فضای کمکی: $O(v)$

پیچیدگی زمانی: $O(v^2)$

کد الگوریتم دایجسترا در #C


// C# program for Dijkstra's single
// source shortest path algorithm.
// The program is for adjacency matrix
// representation of the graph
using System;
 
class GFG {
    // A utility function to find the
    // vertex with minimum distance
    // value, from the set of vertices
    // not yet included in shortest
    // path tree
    static int V = 9;
    int minDistance(int[] dist, bool[] sptSet)
    {
        // Initialize min value
        int min = int.MaxValue, min_index = -1;
 
        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
 
        return min_index;
    }
 
    // A utility function to print
    // the constructed distance array
    void printSolution(int[] dist)
    {
        Console.Write("Vertex \t\t Distance "
                      + "from Source\n");
        for (int i = 0; i < V; i++)
            Console.Write(i + " \t\t " + dist[i] + "\n");
    }
 
    // Function that implements Dijkstra's
    // single source shortest path algorithm
    // for a graph represented using adjacency
    // matrix representation
    void dijkstra(int[, ] graph, int src)
    {
        int[] dist
            = new int[V]; // The output array. dist[i]
        // will hold the shortest
        // distance from src to i
 
        // sptSet[i] will true if vertex
        // i is included in shortest path
        // tree or shortest distance from
        // src to i is finalized
        bool[] sptSet = new bool[V];
 
        // Initialize all distances as
        // INFINITE and stpSet[] as false
        for (int i = 0; i < V; i++) {
            dist[i] = int.MaxValue;
            sptSet[i] = false;
        }
 
        // Distance of source vertex
        // from itself is always 0
        dist[src] = 0;
 
        // Find shortest path for all vertices
        for (int count = 0; count < V - 1; count++) {
            // Pick the minimum distance vertex
            // from the set of vertices not yet
            // processed. u is always equal to
            // src in first iteration.
            int u = minDistance(dist, sptSet);
 
            // Mark the picked vertex as processed
            sptSet[u] = true;
 
            // Update dist value of the adjacent
            // vertices of the picked vertex.
            for (int v = 0; v < V; v++)
 
                // Update dist[v] only if is not in
                // sptSet, there is an edge from u
                // to v, and total weight of path
                // from src to v through u is smaller
                // than current value of dist[v]
                if (!sptSet[v] && graph[u, v] != 0
                    && dist[u] != int.MaxValue
                    && dist[u] + graph[u, v] < dist[v])
                    dist[v] = dist[u] + graph[u, v];
        }
 
        // print the constructed distance array
        printSolution(dist);
    }
 
    // Driver's Code
    public static void Main()
    {
        /* Let us create the example
graph discussed above */
        int[, ] graph
            = new int[, ] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                            { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                            { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                            { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                            { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                            { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                            { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                            { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                            { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
        GFG t = new GFG();
 
        // Function call
        t.dijkstra(graph, 0);
    }
}

خروجی کد:


Vertex          Distance from Source
0                  0
1                  4
2                  12
3                  19
4                  21
5                  11
6                  9
7                  8
8                  14

فضای کمکی: $O(v)$

پیچیدگی زمانی: $O(v^2)$

کد الگوریتم دایجسترا در جاوا اسکریپت

  
// A Javascript program for Dijkstra's single
// source shortest path algorithm.
// The program is for adjacency matrix
// representation of the graph    
let V = 9;
 
// A utility function to find the
// vertex with minimum distance
// value, from the set of vertices
// not yet included in shortest
// path tree
function minDistance(dist,sptSet)
{
     
    // Initialize min value
    let min = Number.MAX_VALUE;
    let min_index = -1;
     
    for(let v = 0; v < V; v++)
    {
        if (sptSet[v] == false && dist[v] <= min)
        {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}
 
// A utility function to print
// the constructed distance array
function printSolution(dist)
{
    document.write("Vertex \t\t Distance from Source");
    for(let i = 0; i < V; i++)
    {
        document.write(i + " \t\t " +
                 dist[i] + "");
    }
}
 
// Function that implements Dijkstra's
// single source shortest path algorithm
// for a graph represented using adjacency
// matrix representation
function dijkstra(graph, src)
{
    let dist = new Array(V);
    let sptSet = new Array(V);
     
    // Initialize all distances as
    // INFINITE and stpSet[] as false
    for(let i = 0; i < V; i++)
    {
        dist[i] = Number.MAX_VALUE;
        sptSet[i] = false;
    }
     
    // Distance of source vertex
    // from itself is always 0
    dist[src] = 0;
     
    // Find shortest path for all vertices
    for(let count = 0; count < V - 1; count++)
    {
         
        // Pick the minimum distance vertex
        // from the set of vertices not yet
        // processed. u is always equal to
        // src in first iteration.
        let u = minDistance(dist, sptSet);
         
        // Mark the picked vertex as processed
        sptSet[u] = true;
         
        // Update dist value of the adjacent
        // vertices of the picked vertex.
        for(let v = 0; v < V; v++)
        {
             
            // Update dist[v] only if is not in
            // sptSet, there is an edge from u
            // to v, and total weight of path
            // from src to v through u is smaller
            // than current value of dist[v]
            if (!sptSet[v] && graph[u][v] != 0 &&
                   dist[u] != Number.MAX_VALUE &&
                   dist[u] + graph[u][v] < dist[v])
            {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
     
    // Print the constructed distance array
    printSolution(dist);
}
 
// Driver code
let graph = [ [ 0, 4, 0, 0, 0, 0, 0, 8, 0 ],
              [ 4, 0, 8, 0, 0, 0, 0, 11, 0 ],
              [ 0, 8, 0, 7, 0, 4, 0, 0, 2 ],
              [ 0, 0, 7, 0, 9, 14, 0, 0, 0],
              [ 0, 0, 0, 9, 0, 10, 0, 0, 0 ],
              [ 0, 0, 4, 14, 10, 0, 2, 0, 0],
              [ 0, 0, 0, 0, 0, 2, 0, 1, 6 ],
              [ 8, 11, 0, 0, 0, 0, 1, 0, 7 ],
              [ 0, 0, 2, 0, 0, 0, 6, 7, 0 ] ]
dijkstra(graph, 0);

خروجی کد:


Vertex          Distance from Source
0                  0
1                  4
2                  12
3                  19
4                  21
5                  11
6                  9
7                  8
8                  14

فضای کمکی: $O(v)$

پیچیدگی زمانی: $O(v^2)$

الگوریتم دایجسترا چیست؟

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

الگوریتم دایجسترا چه کاربردهایی دارد؟

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

همچنین هر گونه سوالی در مورد کلاس‌های آنلاین کنکور کامپیوتر و یا تهیه فیلم‌ها و یا رزرو مشاوره تک جلسه‌ای تلفنی با استاد رضوی دارید می‌توانید به طرق زیر از تیم پشتیبانی بپرسید:

آی دی تلگرام تیم پشتیبانی:     konkurcomputer_admin@

تماس با پشتیبانی:   09378555200

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (5 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200