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

الگوریتم جانسون «Johnson’s algorithm» یکی از الگوریتم‌های معروف در حوزه نظریه گراف است که برای پیدا کردن کوتاه‌ترین مسیر بین تمام جفت‌های رأس‌ها یک گراف استفاده می‌شود. در این مقاله از آموزش‌های پی‌استور می‌خواهیم به آموزش الگوریتم جانسون بپردازیم.

مقدمه

الگوریتم جانسون در گراف‌های جهت‌دار وزن‌دار برای پیدا کردن کوتاه‌ترین مسیر بین تمام جفت‌های رأس‌ها استفاده می‌شود. این الگوریتم برای گراف‌های پراکنده (Sparse)، کارآمدتر از الگوریتم‌های دیگر مثل فلوید-وارشال است. همچنین، می‌تواند گراف‌هایی با وزن‌های یال منفی را (به شرط نداشتن دور منفی) مدیریت کند.

تعریف الگوریتم جانسون

الگوریتم جانسون یک روش برای محاسبه کوتاه‌ترین مسیر بین تمام جفت‌های رأس‌ها در گراف‌های جهت‌دار وزن‌دار است. این الگوریتم برای گراف‌هایی که وزن یال‌های منفی دارند مناسب است، اما تنها به شرطی که گراف شامل دور منفی نباشد. هدف اصلی الگوریتم، تبدیل وزن‌های یال‌های منفی به وزن‌های غیرمنفی است تا بتوان از الگوریتم دیکسترا برای محاسبه کوتاه‌ترین مسیرها استفاده کرد. این فرآیند با افزودن یک رأس مصنوعی به گراف آغاز می‌شود که به تمام رأس‌های موجود با یال‌هایی به وزن صفر متصل است. سپس، الگوریتم بلمن-فورد برای محاسبه وزن‌های مؤثر رأس‌ها و اطمینان از نبود دور منفی اجرا می‌شود.

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

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

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

1. مسیریابی شبکه‌ها: در سیستم‌های مسیریابی مانند شبکه‌های کامپیوتری یا سیستم‌های حمل‌ونقل، الگوریتم جانسون می‌تواند برای پیدا کردن کوتاه‌ترین مسیر بین تمامی گره‌ها (مانند روترها یا ایستگاه‌های حمل‌ونقل) استفاده شود. این کاربرد زمانی مفید است که برخی مسیرها هزینه منفی داشته باشند، مانند تخفیف‌ها یا مزایای اضافی.
2. تحلیل داده‌های گرافی: در تحلیل شبکه‌های اجتماعی یا ساختارهای گرافی پیچیده، الگوریتم جانسون به شناسایی کوتاه‌ترین ارتباط بین تمامی جفت‌های گره‌ها کمک می‌کند. این اطلاعات می‌تواند برای تحلیل میزان نزدیکی یا فاصله بین افراد یا نقاط داده‌ای استفاده شود.
3. مدیریت سیستم‌های حمل‌ونقل: در سیستم‌های حمل‌ونقل، مانند مسیریابی در خطوط هوایی یا زمینی، که ممکن است هزینه‌های منفی (مانند تخفیف‌های فصلی) وجود داشته باشد، الگوریتم جانسون برای برنامه‌ریزی مسیرهای بهینه بسیار کارآمد است.
4. بهینه‌سازی شبکه‌های جریان و ارتباطی: در شبکه‌های جریان مانند انتقال داده یا انرژی، این الگوریتم می‌تواند به یافتن مسیرهای کارآمدتر کمک کند. این مورد به‌ویژه در طراحی شبکه‌های پیچیده که شامل ارتباطات چندگانه است، اهمیت دارد.
5. مدیریت پروژه‌ها و برنامه‌ریزی: الگوریتم جانسون می‌تواند در مسائل برنامه‌ریزی که در آن‌ها گرافی از وظایف با هزینه‌ها یا زمان‌های وابسته به هم وجود دارد، برای تعیین سریع‌ترین یا ارزان‌ترین ترتیب اجرای وظایف مورد استفاده قرار گیرد.
6. سیستم‌های مالی و اقتصادی: در تحلیل سیستم‌های مالی که شامل مبادلات پیچیده بین دارایی‌ها یا ارزها است، الگوریتم جانسون برای تعیین بهینه‌ترین مسیر مبادله یا تحلیل هزینه‌ها کاربرد دارد.
7. حل مسائل علمی و پژوهشی: در پژوهش‌های علمی که شامل مدل‌سازی مسائل گرافی با وزن‌های مختلف است، این الگوریتم به‌عنوان یک ابزار استاندارد برای محاسبات استفاده می‌شود.

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

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

کلیک کنید

مثال برای الگوریتم جانسون

الگوریتم جانسون کوتاه‌ترین مسیر بین تمام جفت رأس‌ها در یک گراف جهت‌دار را پیدا می‌کند. این الگوریتم وزن‌های منفی یال‌ها را به وزن‌های غیرمنفی تبدیل می‌کند. برای این کار، از الگوریتم بلمن-فورد استفاده می‌کند تا وزن‌های منفی را حذف کند و سپس الگوریتم دیکسترا را روی گراف جدید اعمال می‌کند.

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

گام اول: اضافه کردن یک رأس جدید

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

گام دوم: اجرای الگوریتم بلمن-فورد

الگوریتم جانسون ابتدا کوتاه‌ترین مسیرها را از رأس S به تمام رأس‌های دیگر گراف محاسبه می‌کند. از آنجا که گراف شامل وزن‌های منفی است، برای انجام این محاسبات از الگوریتم بلمن-فورد استفاده می‌شود.

تمام یال‌های خروجی گراف به ترتیب حروف الفبا در جدولی ثبت می‌شوند.

فاصله به هر رأس ابتدا مقدار بی‌نهایت مقداردهی می‌شود، به‌جز رأس مبدا S که مقدار آن صفر است.

یال‌ها به ترتیب Relax می‌شوند (یعنی وزن‌ها بهینه می‌شوند):

• • در ابتدا، یال‌هایی که از رأس S شروع می‌شوند فاصله‌ای برابر با ۰ خواهند داشت.
  • در اولین تکرار، فاصله‌ی رأس‌های دیگر از S محاسبه می‌شود.
  • بعد از هر تکرار، فاصله‌ها به‌روزرسانی شده و اگر تغییری در فاصله‌ها نباشد، محاسبات متوقف می‌شود.

پاورپوینت تکنیک های مرتب سازی

کلیک کنید

در این مثال یال‌های A-D, B-A, B-D, B-F, C-A, C-B, D-F, D-G, E-C, F-C, F-E, و G-E در ابتدا فاصله‌ای برابر با بی‌نهایت دارند. اگر عددی به بی‌نهایت اضافه شود، نتیجه همچنان بی‌نهایت باقی می‌ماند. اما یال‌هایی که از رأس منبع S شروع می‌شوند، فاصله‌ای برابر با صفر تا S دارند، بنابراین فاصله‌ها از S می‌توانند محاسبه شوند.

در طول اولین تکرار، تنها یال‌های S-A, S-B, S-C, S-D, S-E, S-F, و S-G اهمیت دارند. با توجه به گراف، فاصله از منبع به تمام رأس‌ها برابر با صفر است. پیشینۀ (Predecessor) تمام رأس‌ها پس از اولین تکرار، رأس S خواهد بود.

با شروع دومین تکرار، تمام یال‌ها دوباره “شل” (Relax) می‌شوند. اگر نیاز دارید درمورد الگوریتم بلمن-فورد یاد بگیرید پیشنهاد می‌کنیم به مقاله الگوریتم بلمن فورد که در مجله پی‌استور منتشر شده است مراجعه کنید.

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

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

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

چهارمین تکرار از الگوریتم بلمن-فورد آغاز می‌شود.

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

پنجمین تکرار از الگوریتم بلمن-فورد آغاز می‌شود.

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

نتیجه اجرای بلمن-فورد

پس از اجرای بلمن-فورد، فاصله به هر رأس از رأس S به‌روزرسانی می‌شود. برای مثال، اگر فاصله اولیه رأس A از S برابر ۰ باشد، پس از اجرای بلمن-فورد ممکن است مقدار آن به یک مقدار منفی به‌روزرسانی شود.

پاورپوینت درباره الگوریتم فلوید وارشال — کاربرد، اجرا و نکات مهم

کلیک کنید

پس از پنجمین تکرار، هیچ تغییری رخ نمی‌دهد، بنابراین می‌توانیم بخش بلمن-فورد از الگوریتم جانسون را به پایان برسانیم. فاصله به هر رأس از رأس S در گراف به‌روزرسانی شده است. در ابتدا، کوتاه‌ترین فاصله از  S به A برابر با ۰ بود، اما پس از اجرای الگوریتم بلمن-فورد، کوتاه‌ترین فاصله به A برابر با ۹- شده است که مسیر آن S→F→C→B→A است.

رأس S دیگر برای ادامه الگوریتم ضروری نیست، بنابراین این رأس و یال‌های متصل به آن از گراف حذف می‌شوند.

گام سوم: بازنویسی وزن‌ها

الگوریتم جانسون برای تبدیل و تغییر وزن یال‌ها به مقادیر غیرمنفی از فرمول زیر استفاده می‌کند:

$$w(u,v) = w(u,v) + h[u] – h[v]$$

این فرمول برای هر لبه توسط الگوریتم جانسون اعمال می‌شود. وزن جدید به صورت (h[u] – h[v] + وزن اصلی) حساب می‌شود.

برای یال A−D، الگوریتم جانسون با طول اولیه آن که برابر با ۱۱ است، شروع می‌کند. سپس وزن مبدأ یال (A) که الگوریتم مقدار آن را ۹- تعیین کرده است، به آن اضافه می‌کند و وزن انتهای یال (D) که ۷- است، از آن کم می‌کند.

فرمول محاسبه به صورت زیر خواهد بود:

$${w(u,v)_{A – D}} = 11 + ( – ۹) – ( – ۷) = 9$$

این فرآیند برای تمامی یال‌ها تکرار می‌شود.

$${w(u,v)_{B – A}} = – ۷ + ( – ۹) – ( – ۹) = 7$$

$${w(u,v)_{B – D}} = – ۵ + ( – ۲) – ( – ۷) = 0$$

$${w(u,v)_{B – F}} = 3 + ( – ۲) – ۰ = 1$$

$${w(u,v)_{C – A}} = 17 + ( – ۵) – ( – ۹) = 21$$

$${w(u,v)_{C – B}} = 3 + ( – ۵) – ( – ۲) = 0$$

$${w(u,v)_{D – F}} = 12 + ( – ۷) – ۰ = 5$$

$${w(u,v)_{D – G}} = 9 + ( – ۷) – ۰ = 2$$

$${w(u,v)_{E – C}} = 5 + ( – ۳) – ( – ۵) = 7$$

$${w(u,v)_{F – C}} = – ۵ + ۰ – ( – ۵) = 0$$

$${w(u,v)_{F – E}} = 4 + 0 – ( – ۳) = 7$$

$${w(u,v)_{G – E}} = – ۳ + ۰ – ( – ۳) = 0$$

به‌روزرسانی گراف با وزن‌های جدید

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

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

گراف به‌روزرسانی شده با وزن‌های جدید به صورت زیر خواهد بود.

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

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

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

کلیک کنید

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

در این بخش کد پیاده‌سازی الگوریتم جانسون (Johnson’s Algorithm) برای پیدا کردن کوتاه‌ترین مسیرها بین تمامی جفت‌های رأس‌ها در یک گراف که می‌تواند گراف‌هایی با یال‌های منفی را نیز پردازش کند، به زبان پایتون آورده شده است.

# Implementation of Johnson's algorithm in Python3

# Import function to initialize the dictionary
from collections import defaultdict
MAX_INT = float('Inf')

# Returns the vertex with minimum
# distance from the source
def minDistance(dist, visited):

    (minimum, minVertex) = (MAX_INT, 0)
    for vertex in range(len(dist)):
        if minimum > dist[vertex] and visited[vertex] == False:
            (minimum, minVertex) = (dist[vertex], vertex)

    return minVertex


# Dijkstra Algorithm for Modified
# Graph (removing negative weights)
def Dijkstra(graph, modifiedGraph, src):

    # Number of vertices in the graph
    num_vertices = len(graph)

    # Dictionary to check if given vertex is
    # already included in the shortest path tree
    sptSet = defaultdict(lambda : False)

    # Shortest distance of all vertices from the source
    dist = [MAX_INT] * num_vertices

    dist[src] = 0

    for count in range(num_vertices):

        # The current vertex which is at min Distance
        # from the source and not yet included in the
        # shortest path tree
        curVertex = minDistance(dist, sptSet)
        sptSet[curVertex] = True

        for vertex in range(num_vertices):
            if ((sptSet[vertex] == False) and
                (dist[vertex] > (dist[curVertex] +
                modifiedGraph[curVertex][vertex])) and
                (graph[curVertex][vertex] != 0)):
                
                dist[vertex] = (dist[curVertex] +
                                modifiedGraph[curVertex][vertex]);

    # Print the Shortest distance from the source
    for vertex in range(num_vertices):
        print ('Vertex ' + str(vertex) + ': ' + str(dist[vertex]))

# Function to calculate shortest distances from source
# to all other vertices using Bellman-Ford algorithm
def BellmanFord(edges, graph, num_vertices):

    # Add a source s and calculate its min
    # distance from every other node
    dist = [MAX_INT] * (num_vertices + 1)
    dist[num_vertices] = 0

    for i in range(num_vertices):
        edges.append([num_vertices, i, 0])

    for i in range(num_vertices):
        for (src, des, weight) in edges:
            if((dist[src] != MAX_INT) and
                    (dist[src] + weight < dist[des])):
                dist[des] = dist[src] + weight

    # Don't send the value for the source added
    return dist[0:num_vertices]

# Function to implement Johnson Algorithm
def JohnsonAlgorithm(graph):

    edges = []

    # Create a list of edges for Bellman-Ford Algorithm
    for i in range(len(graph)):
        for j in range(len(graph[i])):

            if graph[i][j] != 0:
                edges.append([i, j, graph[i][j]])

    # Weights used to modify the original weights
    modifyWeights = BellmanFord(edges, graph, len(graph))

    modifiedGraph = [[0 for x in range(len(graph))] for y in
                    range(len(graph))]

    # Modify the weights to get rid of negative weights
    for i in range(len(graph)):
        for j in range(len(graph[i])):

            if graph[i][j] != 0:
                modifiedGraph[i][j] = (graph[i][j] +
                        modifyWeights[i] - modifyWeights[j]);

    print ('Modified Graph: ' + str(modifiedGraph))

    # Run Dijkstra for every vertex as source one by one
    for src in range(len(graph)):
        print ('\nShortest Distance with vertex ' +
                        str(src) + ' as the source:\n')
        Dijkstra(graph, modifiedGraph, src)

# Driver Code
graph = [[0, -5, 2, 3],
        [۰, ۰, ۴, ۰],
        [۰, ۰, ۰, ۱],
        [۰, ۰, ۰, ۰]]

JohnsonAlgorithm(graph)

پیچیدگی زمانی: پیچیدگی زمانی الگوریتم بالا به صورت زیر است:

$$O({V^3} + V * E)$$

زیرا الگوریتم دیکسترا برای ماتریس مجاورت پیچیدگی زمانی O(n^۲) دارد. توجه داشته باشید که الگوریتم بالا می‌تواند با استفاده از لیست مجاورت به جای ماتریس مجاورت برای نمایش گراف، کارآمدتر شود. در ادامه هر بخش از کد را توضیح می‌دهیم:

۱- تعریف توابع کمکی:

1. minDistance(dist, visited): این تابع برای انتخاب رأس با حداقل فاصله از منبع استفاده می‌شود که هنوز در درخت کوتاه‌ترین مسیر قرار نگرفته است.
2. Dijkstra(graph, modifiedGraph, src): این تابع الگوریتم دیکسترا را برای گراف تغییر یافته (که تمامی یال‌ها وزنی غیر منفی دارند) اجرا می‌کند تا کوتاه‌ترین مسیرها از یک رأس مشخص به تمام سایر رأس‌ها را پیدا کند.
3. BellmanFord(edges, graph, num_vertices): این تابع الگوریتم بلمن-فورد را برای حذف یال‌های منفی در گراف اجرا می‌کند و برای هر رأس، کوتاه‌ترین فاصله را از یک رأس فرضی جدید محاسبه می‌کند.
4. JohnsonAlgorithm(graph): این تابع پیاده‌سازی اصلی الگوریتم جانسون است که مراحل مختلف الگوریتم جانسون را شامل می‌شود:
   • اجرای الگوریتم بلمن-فورد برای پیدا کردن وزن‌های جدید.
   • تغییر وزن‌های گراف با استفاده از وزن‌های جدید.
   • اجرای الگوریتم دیکسترا برای هر رأس به‌عنوان منبع.

۲- عملکرد الگوریتم جانسون:

• ابتدا، یک رأس فرضی جدید به گراف اضافه می‌شود که به همه رأس‌های دیگر متصل است (در الگوریتم بلمن-فورد از این رأس برای محاسبه کوتاه‌ترین فاصله‌ها استفاده می‌شود).
• سپس با استفاده از الگوریتم بلمن-فورد، کوتاه‌ترین فاصله‌ها از این رأس جدید به رأس‌های دیگر محاسبه می‌شود.
• وزن‌های یال‌ها بر اساس این فواصل به‌روزرسانی می‌شوند.
• پس از این تغییرات، الگوریتم دیکسترا برای هر رأس به‌عنوان منبع اجرا می‌شود تا کوتاه‌ترین مسیرها از هر رأس به سایر رأس‌ها محاسبه شوند.

۳- عملکرد کد:

• گراف ورودی به شکل ماتریس وزنی است که نشان‌دهنده گراف ورودی است.
• گراف تغییر یافته (که پس از به‌روزرسانی وزن‌های یال‌ها از طریق الگوریتم بلمن-فورد ساخته می‌شود) به‌عنوان ورودی به الگوریتم دیکسترا داده می‌شود تا مسیرهای کوتاه را محاسبه کند.
• نتایج به‌عنوان کوتاه‌ترین فاصله‌ها از هر رأس به سایر رأس‌ها در خروجی چاپ می‌شود.

خروجی:

Modified Graph: [[0, 0, 3, 3], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Shortest Distance with vertex 0 as the source:

Vertex 0: 0
Vertex 1: 0
Vertex 2: 0
Vertex 3: 0

Shortest Distance with vertex 1 as the source:

Vertex 0: inf
Vertex 1: 0
Vertex 2: 0
Vertex 3: 0

Shortest Distance with vertex 2 as the source:

Vertex 0: inf
Vertex 1: inf
Vertex 2: 0
Vertex 3: 0

Shortest Distance with vertex 3 as the source:

Vertex 0: inf
Vertex 1: inf
Vertex 2: inf
Vertex 3: 0

نتیجه گیری

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