پیاده‌سازی الگوریتم Dijkstra جهت یافتن مسیر بهینه مابین رئوس گراف در پایتون

در مقالۀ Graph چیست و این دیتا استراکچر چه کاربردهایی دارا است؟ به بررسی دیتا استراکچر گراف پرداخته و با کاربردهای آن آشنا شدیم و گفتیم که یکی از کاربردهایش مدل‌سازی نقشۀ راه‌های بین‌شهری است که در آن هر یک از شهرها به عنوان رئوس گراف و جاده‌های مابین آن‌ها نیز به عنوان یال‌های گراف در نظر گرفته می‌شوند.

حال در این آموزش قصد داریم تا به معرفی یکی از الگوریتم‌های کاربردی تحت عنوان Dijkstra به منظور اِعمال روی گراف‌هایی بپردازیم که با به‌کارگیری آن‌ها می‌توان کمترین هزینه مابین دو رأس از گراف مربوطه را به دست آورد. در واقع، واژۀ «هزینه» در این الگوریتم معانی متفاوت می‌تواند داشته باشد که از آن جمله می‌توان به کوتاه‌ترین مسیر مابین نقشۀ جاده‌های بین‌شهری و شبکه‌های تلفنی به منظور هدایت تماس‌ها به خطوطی با پهنای‌باند بالا و مواردی از این دست اشاره کرد به طوری که هدف این الگوریتم جستجو در گراف مدل‌سازی شده و پیدا کردن بهینه‌ترین مسیر مابین رئوس مد نظر می‌باشد.

اکنون به منظور درک بهتر مفهوم کوتاه‌ترین مسیر در گراف مربوط به نقشۀ جاده‌های بین‌شهری سناریویی را در نظر می‌گیریم که در آن قصد داریم تا روشی را به منظور پیدا کردن کوتاه‌ترین مسیر مابین دو نقطه از نقشۀ مثال فوق پیاده‌سازی کنیم به طوری که کاربر دو نقطۀ مبدأ و مقصد مورد نظر خود از گراف را وارد کرده و الگوریتم پیاده‌سازی‌شده کوتاه‌ترین فاصلۀ مابین آن‌ها را روی نقشه به وی پیشنهاد می‌دهد. به طور مثال، فرض کنید قصد داریم تا از شهر بوشهر به گرگان مسافرت کنیم که با پیاده‌سازی الگوریتم مربوطه، کوتاه‌ترین فاصلۀ مابین این دو شهر را یافته و مسیر پیشنهادی را انتخاب می‌کنیم.

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

آشنایی با نحوۀ کار الگوریتم Dijkstra

ابتدا به ساکن نحوۀ عملکرد الگوریتم دایجکسترا را گام‌به‌گام تشریح می‌کنیم تا ببینیم که چگونه می‌توان با به‌کارگیری این الگوریتم مسیری با کمترین هزینه مابین دو رأس گراف را تشخیص داد:

1. ابتدا هزینۀ پیمایش برای رأس مبدأ را برابر با صفر قرار می‌دهیم که این مسئله کاملاً بدیهی است چرا که هزینه‌ای صرف انتقال به خود رأس نمی‌شود.

2. رأس مبدأ را به عنوان رأس اصطلاحاً Visited یا پیمایش‌شده در نظر می‌گیریم.

3. حال برای محاسبۀ هزینۀ پیمایش از رأس مبدأ به هر یک از رئوس همسایۀ آن کافی است تا هزینۀ خود رأس (صفر) را با وزن هر یک از یال‌های مابین رئوس همسایۀ رأس مبدأ جمع کنیم.

4. از میان رئوسی که هزینۀ انتقال آن‌ها محاسبه شده است، رأسی با کمترین هزینه را انتخاب کرده و به عنوان رأس بعدی برای پیمایش در نظر می‌گیریم.

5. اکنون رأسی با کمترین هزینه که در مرحلۀ پیشین مشخص شده است را به عنوان رأس جاری در نظر گرفته و در ادامه باید هزینۀ پیمایش به رئوس همسایۀ آن را محاسبه کنیم.

6. در این مرحله به منظور محاسبۀ هزینۀ پیمایش رئوس همسایه کافی است تا وزن یال مابین رأس کنونی و رأس مد نظر را با هزینۀ انتقال به رأس کنونی جمع کنیم.

7. حال بررسی می‌کنیم ببینیم چنانچه از میان رئوس همسایه رأسی داشته باشیم که هزینۀ انتقال به آن را در مراحل پیشین محاسبه کرده‌ایم و این مقدار بزرگ‌تر از هزینه‌ای است که در گام ششم برای رأس مذکور محاسبه شده، مقدار جدید را جایگزین مقدار مربوط به هزینۀ پیشین می‌کنیم.

8. مجدداً از میان تمامی رئوسی که هزینۀ انتقال برای آن‌ها محاسبه شده است، رأسی با کمترین هزینه را انتخاب کرده و به عنوان رأس کنونی در نظر می‌گیریم.

9. مراحل فوق را تا جایی ادامه می‌دهیم که به رأس مقصدی برسیم که توسط کاربر تعریف شده است.

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

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

برای پیاده‌سازی الگوریتم دایجکسترا، ابتدا لازم است تا لیست یال‌های گراف فوق‌ را تعریف کنیم که برای این منظور کلاسی تحت عنوان Graph ایجاد می‌کنیم:

from collections import defaultdict
class Graph():
    def __init__(self):
        self.edges = defaultdict(list)
        self.weights = {}
    def addEdge(self, fromVerex, toVertex, weight):
        self.edges[fromVerex].append(toVertex)
        self.edges[toVertex].append(fromVerex)
        self.weights[(fromVerex, toVertex)] = weight
        self.weights[(toVertex, fromVerex)] = weight

در کد فوق، ابتدا کلاس defaultdict از ماژول collections را ایمپورت کرده‌ایم سپس کلاسی تحت عنوان Graph ایجاد کرده و در ادامه با رعایت تورفتگی وارد کلاس شده و متد از پیش تعریف‌شدۀ __()init__ را نوشته‌ایم که نقش یک کانستراکتور را بازی می‌کند و دارای یک پارامتر ورودی تحت عنوان self است که به منظور ارجاع دادن به جدیدترین آبجکت ساخته‌شده از روی کلاس مورد استفاده قرار می‌گیرد.

داخل کانستراکتور کلاس نیز اتریبیوت‌هایی را تعریف می‌کنیم که قصد داریم تا در حین ساخت آبجکت از روی کلاس مقداردهی شوند؛ بدین ترتیب اتریبیوتی تحت عنوان edges تعریف می‌کنیم که این اتریبیوت مسئول نگهداری یال‌های گراف مربوطه می‌باشد و آبجکتی خالی از جنس لیست از روی کلاس defaultdict ساخته و آن را به اتریبیوت edges منتسب کرده‌ایم که این کار تضمینی ایجاد می‌کند تا در صورتی که برخی از رئوس مد نظر کاربر در گراف تعریف‌شده وجود نداشتند، اجرای برنامه با خطا مواجه نشود.

در ادامه اتریبیوت دیگری از جنس دیکشنری تحت عنوان weights تعریف کرده و مقدار اولیۀ آن را خالی قرار داده‌ایم که در آن جفت رئوس ابتدا و انتهای یال به عنوان Key و وزن متناظر یال به عنوان Value در نظر گرفته می‌شود (کیورد self در ابتدای تمامی اتریبیوت‌ها نیز به منظور ارجاع دادن به آبجکت ساخته‌شده از روی کلاس نوشته شده است و بدین ترتیب در صورت ساخت آبجکتی از روی کلاس می‌توان به اتریبیوت‌های مد نظر دسترسی داشته و آن‌ها را مقداردهی کرد.)

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

پارامتر اول self بوده و به آبجکت ساخته‌شده از روی کلاس ارجاع می‌دهد و بدین ترتیب می‌توان به متد مذکور دسترسی داشته و آن را روی جدیدترین آبجکت ساخته‌شده از روی کلاس فراخوانی کرد. پارامترهای دوم و سوم تحت عناوین fromVertex و toVertex را به ترتیب به منظور انتساب رئوس ابتدا و انتهایی مربوط به یال مابین‌ آن‌ها در نظر گرفته‌ایم و در نهایت پارامتر ورودیِ weight را جهت اختصاص وزن به یال مد نظر تعریف کرده‌ایم. داخل فانکشن ()addEdge نیز گفته‌ایم در صورت فراخوانی، مقدار منتسب به پارامتر fromVertex (رأس ابتدایی یال) را به عنوان کلید آبجکت edges در نظر گرفته و مقدار منتسب به پارامتر toVertex (رأس انتهایی یال) را با فراخوانی فانکشن از پیش تعریف‌شدۀ ()append به لیست رئوس متصل به یال‌هایی با رأس ابتدایی fromVertex اضافه کند (در واقع، رأس ابتدایی به عنوان کلید در دیکشنری در نظر گرفته شده و رئوس انتهایی مربوط به یال متصل به این رأس در قالب آبجکتی از جنس لیست به عنوان مقدار برای آن تعریف می‌شوند؛ به عبارت بهتر، لیستی از رأس ابتدایی و رئوس همسایۀ آن ایجاد می‌کنیم.)

اساساً بدین دلیل که گراف مربوطه را دوسویه و بی‌جهت در نظر گرفته‌ایم، مجدداً مقادیر منتسب به پارامتر toVertex را به عنوان رأس ابتدایی یال در نظر گرفته و مقادیر منتسب به پارامتر fromVertex را رأس انتهایی در نظر می‌گیریم و یال دیگری را به لیست یال‌های گراف اضافه می‌کنیم (جهت آشنایی با گراف‌های دوسویه یا بی‌جهت به مقاله‌ای که در ابتدا معرفی کردیم مراجعه نمایید.)

در ادامه همان‌طور که پیش‌تر اشاره کردیم، جفت مقادیر منتسب به پارامترهای fromVertex و toVertex را به عنوان کلید در نظر گرفته و مقدار منتسب به پارامتر weight را به عنوان وزن متناظر یال به دیکشنری weights اضافه می‌کنیم و به دلیل بی‌جهت بودن گراف مد نظر، مقدار منتسب به پارامتر weight را به یال مابین رئوس انتها به ابتدا نیز منتسب می‌کنیم.

حال به پیاده‌سازی متدی تحت عنوان ()dijkstra می‌پردازیم که برای این منظور کدی مانند زیر خواهیم داشت:

def dijkstra(myGraph, initial, end):
    shortestPaths = {initial: (None, 0)}
    currentVertex = initial
    visited = set()
    while currentVertex != end:
        visited.add(currentVertex)
        destinations = graph.edges[currentVertex]
        weightToCurrentVertex = shortestPaths[currentVertex][1]
        for nextVertex in destinations:
            weight = graph.weights[(currentVertex, nextVertex)] + weightToCurrentVertex
            if nextVertex not in shortestPaths:
                shortestPaths[nextVertex] = (currentVertex, weight)
            else:
                currentShortestWeight = shortestPaths[nextVertex][1]
                if currentShortestWeight > weight:
                    shortestPaths[nextVertex] = (currentVertex, weight)        
        nextDestinations = {vertex: shortestPaths[vertex] for vertex in shortestPaths if vertex not in visited}
        if not nextDestinations:
            return "Route Not Possible"
        currentVertex = min(nextDestinations, key=lambda k: nextDestinations[k][1])
    path = []
    while currentVertex is not None:
        path.append(currentVertex)
        nextVertex = shortestPaths[currentVertex][0]
        currentVertex = nextVertex
    path = path[: : -1]
    return path

برای این متد سه پارامتر ورودی در نظر گرفته‌ایم که پارامتر اول به منظور پاس دادن آبجکت ساخته‌شده از روی کلاس Graph به متد مذکور تعریف شده و پارامترهای دو و سوم نیز به ترتیب تحت عناوین initial و end به منظور پاس دادن مقادیر مربوط به رئوس مبدأ و مقصد از گراف به منظور محاسبۀ کوتاه‌ترین مسیر مابین آن‌ها تعریف شده‌اند.

داخل متد ()dijkstra متغیری تحت عنوان shortestPaths از جنس دیکشنری تعریف کرده‌ایم که قرار است تا رأس جاری به عنوان کلید و جفت رأس پیشین و وزن یال مابین آن‌ها را به عنوان مقدار نگهداری کند و از همین روی مقدار اولیۀ این متغیر را برابر با رأس آغازین و مقدار متناظر را برابر با None و 0 به صورت یک جفت قرار داده‌ایم. در واقع، این شیوۀ ذخیره‌سازی در مرحلۀ آخر‌، با رسیدن به رأس مقصد و به منظور بازگشت به عقب و بازیابی رئوسی به ما کمک می‌کند که با کمترین هزینه منتهی به رأس مقصد شده‌اند.

سپس متغیری تحت عنوان currentVertex تعریف کرده‌ایم که قرار است تا رأس جاری در آن نگهداری شود که از همین روی رأس آغازین را به عنوان رأس جاری به آن منتسب می‌کنیم و در ادامه متغیر دیگری به نام visited تعریف کرده‌ایم که قرار است تا رئوس پیمایش‌شده از گراف را به آن منتسب کنیم؛ بنابراین فانکشن از پیش تعریف‌شدۀ ()set را فراخوانی کرده‌ایم و آن را به متغیر visited منتسب کرده‌ایم که بدین ترتیب آبجکتی از جنس Set ساخته می‌شود که با به‌کارگیری این آبجکت می‌توانیم یکسری مقادیر منحصربه‌فرد از رئوس پیمایش‌شدۀ گراف را در آن ذخیره و نگهداری کنیم.

سپس یک حلقۀ while تعریف کرده‌ایم که در آن گفته‌ایم دستورات داخل حلقه را تا زمانی اجرا کند که رأس جاری برابر با رأسی نباشد که به عنوان رأس مقصد توسط کاربر تعریف شده است؛ به عبارت دیگر، حلقۀ while تا زمانی تکرار می‌شود که به رأس مقصد از گراف مد نظر برسیم سپس با رعایت تورفتگی وارد حلقه شده و در آن مقدار منتسب به متغیر currentVertex (رأس جاری) را به عنوان آرگومان ورودی به فانکشن از پیش تعریف‌شدۀ ()add داده و آن را روی آبجکت visited فراخوانی کرده‌ایم.

در واقع، با فراخوانی فانکشن ()add روی آبجکت visited و دادن رأس جاری به عنوان آرگومان ورودی به این فانکشن گفته‌ایم تنها در صورتی که رأس جاری داخل مجموعه رئوس پیمایش‌شدۀ گراف وجود نداشته باشد، آن را به مجموعۀ visited اضافه کند و در ادامه متغیری تحت عنوان destinations تعریف کرده‌ایم که مقادیر منتسب به کلید currentVertex از دیکشنری edges را نگهداری می‌کند بدین ترتیب تمامی رئوسی که از طریق یال‌های گراف به رأس جاری متصل می‌شوند، به متغیر destinations منتسب می‌شوند و بدین طریق به رأس‌های همسایۀ رأس جاری دسترسی پیدا می‌کنیم. همچنین متغیر دیگری به نام weightToCurrentVertex تعریف کرده‌ایم که قرار است تا وزن یال مابین این رأس و رأس پیشین پیمایش‌شده از دیکشنری shortestPaths را نگهداری کند.

اکنون یک حلقۀ for تعریف کرده‌ایم که بدین طریق قصد داریم تا هزینۀ پیمایش از رأس جاری به هر یک از رأس‌های همسایۀ آن یا به عبارتی هر یک از رئوس منتسب به متغیر destinations را محاسبه کنیم به طوری که در این حلقه گفته‌ایم به ازای هر یک از رئوس منتسب به متغیر destinations وزن یال مابین رأس جاری و رئوس همسایه را با وزنی که برای رأس جاری محاسبه شده است جمع کرده و آن را به متغیر weight منتسب کند و در دستور if چک کند چنانچه پیش از این هزینۀ انتقال به هر یک از رئوس همسایه محاسبه نشده بود، هزینۀ محاسبه‌شده را به دیکشنری shortestPaths بیفزاید و در غیر این صورت هزینۀ محاسبه‌شده در این مرحله را با هزینۀ ذخیره‌شده در دیکشنری shortestPaths مقایسه کند تا اگر مقدار جدید کوچک‌تر بود، آن را جایگزین هزینۀ انتقال به رأس مد نظر کند.

متغیر دیگری تحت عنوان nextDestinations از جنس دیکشنری در نظر گرفته‌ایم تا بتوانیم از میان تمامی رأس‌هایی که پیمایش نشده‌اند، رأسی با کمترین میزان هزینه را انتخاب کرده و آن را به عنوان رأس جاری در نظر بگیریم؛ بنابراین یک آبجکت از جنس دیکشنری تعریف کرده و تمامی رئوسی از دیکشنریِ shortestPaths که هزینۀ پیمایش برای‌ آن‌ها محاسبه شده اما پیمایش نشده‌اند را به همراه جفت «رأس پیشین و هزینۀ انتقال به رأس پیشین +‌ وزن یال متصل به رأس مد نظر» را به متغیر nextDestinations منتسب کرده‌ایم.

سپس در شرط if چک می‌کنیم چنانچه رأسی در دیکشنری nextDestinations موجود نبود، استرینگ «Route Not Possible» را در خروجی ریترن کند بدین معنی که «از رأس مد نظر یالی برای انتقال به رئوش دیگر وجود ندارد» و در غیر این صورت تابعِ بی‌نامی تعریف کرده‌ایم که در آن گفته‌ایم به ازای اِلِمان یکم از لیستی که به عنوان مقدار به دیکشنری nextDestinations منتسب شده است (هزینۀ انتقال به رأس مد نظر)، فانکشن از پیش تعریف‌شدۀ ()min را فراخوانی کرده و رأسی با کمترین هزینۀ انتقال را به متغیر currentVertex منتسب کند (Anonymous Function یا «تابع بی‌نام» در زبان برنامه‌نویسی پایتون با کیورد lambda تعریف می‌شود بدین صورت که در ابتدا به تعداد دلخواه آرگومان ورودی برایش تعریف کرده و در ادامه علامت : را قرار داده و پس از آن دستور مد نظر به منظور اِعمال روی آرگومان‌های ورودی نوشته می‌شود.)

حال متغیری از جنس لیست تحت عنوان path تعریف می‌کنیم تا کوتاه‌ترین مسیر مشخص‌شده مابین رئوس مبدأ و مقصد را در خروجی چاپ کنیم که برای این منظور یک حلقۀ while تعریف کرده‌ایم و گفته‌ایم تا زمانی که مقادیر منتسب به متغیر currentVertex برابر با مقدار None یا تهی نشده است، دستورات داخلی را تکرار کند.

داخل حلقۀ while فانکشن از پیش تعریف‌شدۀ ()append را روی آبجکت لیست فراخوانی کرده و گفته‌ایم هر یک از مقادیر منتسب به متغیر currentVertex را تک‌تک به آبجکتِ لیستِ path اضافه کند بدین صورت که از رأس جاری به عقب بازگشته و مقدار ذخیره‌شده به عنوان رأس پیشین برای رأس جاری که منتهی به کوتاه‌ترین مسیر تا رأس جاری شده است را بازیابی کرده و آن را به متغیر nextVertex منتسب کند. حال رأس پیشین را به متغیر currentVertex منتسب کرده و به همین ترتیب در گراف به عقب بازمی‌گردیم تا زمانی که تمامی رئوس پیشین ذخیره‌شده برای این رأس که منجر به کوتاه‌ترین مسیر شده‌اند را از دیکشنری shortestPaths بازیابی کنیم که در نهایت لیستی داریم که با شروع از رأس مقصد به عقب بازگشته و تمامی رئوسی با کمترین هزینه و منتهی به این رأس را بازیابی کرده‌ایم.

در ادامه با دستور [path[ : : -1 لیست مذکور را معکوس می‌کنیم تا کوتاه‌ترین مسیر با شروع از رأس مبدأ به مقصد در خروجی ریترن شود. در واقع، دستور فوق‌الذکر بدین صورت عمل می‌کند که المان اول به اندیس مربوط به عضو ابتدایی لیست و المان دوم به اندیس مربوط به عضو انتهایی آن اشاره می‌کند که در این دستور خالی بودن مقادیر اندیس‌ها بدین معنی است که قصد داریم تا به تمامی عناصر لیستِ path دسترسی بیابیم. در واقع، عدد 1- در دستور [path[ : : -1 به منظور اشاره به انتهای لیست به کار گرفته شده است به طوری که اولین عضو از سمت راست لیست را با عدد 1- اندیس‌گذاری کرده و به همین ترتیب اِلِمان‌های بعدی از سمت چپ لیست با افزایش یک واحد منفی اندیس‌گذاری می‌شوند که بدین ترتیب می‌توانیم هر یک از رئوس را به صورت معکوس در خروجی ریترن کنیم.

حال آبجکتی تحت عنوان graph از روی کلاس Graph ساخته و در ادامه هر یک از رئوس مربوط به دو سَر یال از گراف مد نظر خود و وزن متناظر هر یال را به صورت زیر تعریف می‌کنیم:

graph = Graph()
edges = [
    ('Orumiyeh', 'Kermanshah', 54),
    ('Kermanshah', 'ShahrKord', 52),
    ('Kermanshah', 'Ilam', 17),
    ('Kermanshah', 'Yasooj', 78),
    ('Ilam', 'Yasooj', 87),
    ('Ilam', 'Ahvaz', 45),
    ('Ahvaz', 'Boushehr', 45),
    ('Boushehr', 'Yasooj', 29),
    ('Boushehr', 'Mashhad', 160),
    ('Yasooj', 'ShahrKord', 26),
    ('Yasooj', 'Esfahan', 33),
    ('ShahrKord', 'Esfahan', 10),
    ('Esfahan', 'Gorgan', 82),
    ('Esfahan', 'Mashhad', 110)
]

در کد فوق، آبجکتی از جنس لیست تعریف کرده‌ایم که هر یک از عناصر داخلی آن به منزلۀ یالی از گراف مد نظر بوده و از جنس تاپل می‌باشند که مقادیر مربوط به رئوس ابتدایی و انتهایی یال و وزن یال متناظر را شامل می‌شوند. سپس یک حلقۀ for می‌نویسیم تا به ازای هر یک از مقادیر منتسب به یال‌های گراف، متد ()addEdge را روی آبجکت ساخته‌شده از کلاس Graph با پارامتر ورودی مربوط به هر یک از یال‌های تعریف‌شده فراخوانی کند:

for edge in edges:
    graph.addEdge(*edge)

همان‌طور که می‌بینید، پارامتر ورودی فانکشن ()addEdge را با علامت * به آن پاس داده‌ایم و بدین ترتیب این امکان را برای کاربر فراهم کرده‌ایم که قابلیت تعریف تعداد دلخواهی یال برای گراف مورد نظر خود داشته باشد که برای کسب اطلاعات بیشتر در رابطه با نحوۀ عملکرد چنین فانکشن‌هایی می‌توانید به آموزش آشنایی با نحوۀ تعریف و فراخوانی فانکشن‌هایی با تعداد پارامترهای ورودی متغیر در پایتون مراجعه کنید.

اکنون یال‌های ورودی توسط کاربر برای گراف مد نظر ایجاد شده است و از همین روی در ادامه متد ()dijkstra را با آرگومان‌های ورودی مربوط به آبجکت ساخته‌شده از روی کلاس Graph تحت عنوان graph و رئوس مبدأ و مقصد از گراف مد نظر فراخوانی می‌کنیم:

dijkstra(graph, 'Boushehr', 'Gorgan')

در نهایت، با اجرای متد ()dijkstra روی گراف مربوط به نقشۀ فوق‌الذکر، کوتاه‌ترین مسیر مابین دو شهر بوشهر و گرگان در خروجی ریترن می‌شود به طوری که داریم:

['Boushehr', 'Yasooj', 'Esfahan', 'Gorgan']

بنابراین اگر بخواهیم نحوۀ محاسبۀ کوتاه‌ترین فاصله مابین دو شهر بوشهر و گرگان را به طور خلاصه در قالب جدولی نمایش دهیم، خواهیم داشت:

لازم به یادآوری است که به منظور سادگی در نمایش وزن یال‌های گراف و همچنین انجام محاسبات مد نظر، تمامی وزن‌ها كه برحسب كيلومتر بوده‌اند را بر عدد 100 تقسیم نموده‌ايم به علاوه اینکه اسامی شهرها جهت نمایش بهتر در قالب حروف اول نام شهر مربوطه آورده شده‌اند.

جدول فوق را با رأس مبدأ مورد نظر خود (بوشهر) شروع کرده‌ایم بدین صورت که در ابتدا هزینۀ سفر به خود این شهر برابر با صفر در نظر گرفته شده و همان‌طور که در توضیحات مربوط به متد ()dijkstra اشاره کردیم، به منظور دست‌یابی به رأس پیشین در محاسبۀ کوتاه‌ترین مسیر لازم است تا هزینۀ پیمایش در قالب جفت «رأس پیشین و هزینۀ انتقال به رأس پیشین + وزن یال مابین دو رأس» ذخیره شود.

در ادامه هزینۀ انتقال به هر یک از رئوس همسایۀ شهر بوشهر را به صورت مجموع وزن یال مابین و هزینۀ انتقال به خود رأس بوشهر محاسبه کرده‌ایم و در مورد رئوسی که یال مستقیم با رأس بوشهر ندارند، هزینۀ انتقال را برابر با مقدار خالی قرار داده‌ایم.

حال از میان هزینه‌هایی که برای انتقال به هر یک از رئوس گراف محاسبه شده‌اند، رأسی با کمترین هزینه را انتخاب کرده و آن را در سطر بعد می‌نویسیم و توجه داشته باشیم که هزینۀ انتقال به این رأس در طی محاسبۀ کوتاه‌ترین مسیر برای سایر رئوس تحت هیچ عنوان تغییر نمی‌کند که از همین روی مقدار ذخیره‌شده برای این رأس را عیناً به سطر بعد منتقل کرده‌ایم چرا که می‌دانیم هزینۀ سفر به شهر یاسوج از طریق شهر بوشهر و با کوتاه‌ترین فاصلۀ ممکن معادل 29 واحد انجام می‌شود؛ بنابراین هزینۀ معادل برای رئوسی که به عنوان کمترین مقدار در هر مرحله انتخاب می‌شوند، عیناً به سطر بعد منتقل می‌شوند.

در سطر مربوط به رأس یاسوج هزینۀ انتقال به رئوس همسایۀ رأس مذکور را بدین صورت محاسبه می‌کنیم که وزن یال مابین هر یک از رئوس همسایه و رأس یاسوج را با هزینۀ انتقال به شهر یاسوج معادل عدد 29 جمع می‌کنیم و در ادامه از میان هزینه‌های انتقال محاسبه‌شده، رأسی با کمترین مقدار (اهواز) را انتخاب کرده و در سطر بعد می‌نویسیم.

در سطر مربوط به رأس اهواز مجدداً مقادیر مربوط به کمترین هزینه‌های انتخاب‌شده در مراحل قبل را بدین سطر منتقل می‌کنیم سپس هزینۀ انتقال به رئوس همسایۀ شهر اهواز را همانند مراحل پیشین محاسبه می‌کنیم و نکتۀ قابل‌توجه در رابطه با رأس ایلام این است که هزینۀ محاسبه‌شده برای رأس مذکور در مرحلۀ قبل برابر با 116 و از طریق رأس یاسوج می‌باشد اما این در حالی است که در این مرحله هزینه‌ای معادل 90 از طریق شهر اهواز را برایش محاسبه کرده‌ایم و بدیهی است که می‌باید رأس مربوط به مسیر کوتاه‌تر (اهواز) را جایگزین مسیر طولانی‌تر نماییم.

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

همان‌طور که می‌بینید، مقدار «Esfahan, 144» برای این رأس درج شده است بدین معنی که کوتاه‌ترین مسیر برای رسیدن به رأس گرگان از رأس اصفهان با هزینۀ 144 واحد عبور می‌کند بنابراین در ادامه باید به سراغ ستون مربوط به رأس اصفهان برویم و می‌بینیم که مقدار «Yasooj, 62» برای این رأس ذخیره شده است و در ادامه به رأس یاسوج مراجعه کرده و به مقدار «Boushehr, 29» می‌رسیم. در نهایت، می‌توان گفت که کوتاه‌ترین مسیر مابین دو رأس بوشهر و گرگان برابر است با گرگان، اصفهان، یاسوج و بوشهر و همان‌طور که در توضیحات متد ()dijkstra اشاره کردیم، در مرحلۀ آخر لیست خروجی را معکوس می‌نماییم تا رئوس مد نظر از رأس ابتدایی به انتهایی در خروجی ریترن شود که هزینۀ انتقال از طریق کوتاه‌ترین مسیر فوق‌الذکر مقداری معادل 235 = 144 + 62 + 29 در واحد مسافت را دارا است.

جمع‌بندی
در این مقاله به بررسی الگوریتم‌ پرکاربردی تحت عنوان Dijkstra به منظور اِعمال روی دیتا استراکچر گراف پرداختیم و دیدیم که الگوریتم مذکور را می‌توان جهت تشخیص مسیری بهینه در رابطه با تمامی مسائلی به کار برد که قابلیت مدل‌سازی با استفاده از دیتا استراکچر گراف را دارند. در پایان، اگر علاقه‌مند به فراگیری زبان برنامه‌نویسی پایتون هستید، توصیه می‌کنیم به دورۀ آموزش پایتون در سکان آکادمی مراجعه نمایید.