مسیریابی در گراف با استفاده از پایتون

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

فرض کنید که ما نقشه‌ای(گراف) به صورت شکل پایین داشته باشیم:

طبق نقشه بالا خانه A به خانه های D و B راه دارد؛ خانه B به خانه های A و C راه دارد و ...

A -> B
A -> D
B -> A
B -> C
B -> D
B -> E
C -> E
C -> B
E -> B
E -> C
E -> D
D -> A
D -> B
D -> E

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

graph = {
    'A' : ['B', 'D'],
    'B' : ['A', 'C', 'D', 'E'],
    'C' : ['E', 'B'],
    'E' : ['B', 'C', 'D'],
    'D' : ['A', 'B', 'E']
}

در کد بالا ما راه های هر خانه را نوشتیم. برای مثال گفتیم که اگر در خانه A هستی، میتوانی به خانه های B و D بروی.

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

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

همانطور که معلوم است، تکه کد بالا سه ورودی دارد؛ اول گرافمان، دوم خانه شروع و سوم خانه پایانی.

start = 'A'
end = 'D'
print(find_all_paths(graph, start, end))

حال این کد را برای گرافی که ساخته ایم اجرا نماییم:

>>> [['A', 'B', 'C', 'E', 'D'], ['A', 'B', 'D'], ['A', 'B', 'E', 'D'], ['A', 'D']]

همینطور که مشاهده میکنید، این تابع تمام راه هایی که من میتوانم از خانه A به خانه D بروم را چاپ کرد.

حالا با خودتون فکر میکنید که چطور میتونم بهترین راه را از بین این راه ها انتخاب کنم.

def find_shortest_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = find_shortest_path(graph, node, end, path)
            if newpath:
                 if not shortest or len(newpath) < len(shortest):
                      shortest = newpath
    return shortest

آموزش جذاب پایگیم

سوال هایتان را در بخش کامنت مطرح کنید.