کوتاه ترین مسیر

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

BFS - Breadth First Search

این الگوریتم برای پیدا کردن کوتاه ترین مسیر از یک راس دلخواه به تمام رئوس یه گراف به کار میره .

توجه داشته باشید که وزن همه یالها باید با هم برابر باشه ( در غیر این صورت از الگوریتم های بعدی استفاده می کنیم )

این الگوریتم در منابع فارسی با عنوان "جستجوی اول عرض" شناخته میشه .

همچنین به این دسته از الگوریتم ها SSSP یا Single Source Shortest Path هم میگن .

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

به طور خلاصه در این روش با شروع از نقطه ابتدایی ، اول رئوس همسایه این رأس رو پیمایش می کنیم و سپس همسایه های همسایه های رأس ابتدایی و سپس همسایه های همسایه های همسایه های رأس ابتدایی و ...

همین طور اینقدر عمل می کنیم تا تمام رأس های گراف دیده شوند .

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

اگر گره ابتدایی رو سطح 0 در نظر بگیریم ، به صورت زیر الگوریتم اجرا خواهد شد .

1. گره (های) سطح 0 رو به صف اضافه کن

2. تا زمانیکه صف خالی نشده

الف. یک گره از صف بر دار 

ب. تمام همسایه های ( دیده نشده ) رأس فعلی رو به ته صف اضافه کن

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

از آنجا که هر یال حداکثر یک بار پیموده می شود ، زمان اجرا نسبت به تعداد یالها خطی است .

بسته به نحوه نگهداری گراف ( لیست مجاورت یا ماتریس مجاورت ) زمان اجرای الگوریتم (|O(|E یا  (O(N^2 خواهد بود .

شبه کد :

Queue Q;
Set Distance[i] = infinity ( for each i )
Distance[ startNode ] = 0
Q.push( startNode )
while Q is not empty
    X = Q.pop()
    for each Y in Neighbours(X)
        if Distance[Y] > Distance[X] + 1
            Distance[Y] = Distance[X] + 1
            Q.push( Y )

از کاربرد های دیگه این الگوریتم میشه به موارد زیر اشاره کرد

- پیدا کردن مولفه های همبندی یک گراف

- تعیین کردن اینکه گراف دوبخشی (bipartite) هست یا نه

ِDijkstra

این الگوریتم نیز برای بدست آوردن کوتاه ترین مسیر از یک رأس به همه رئوس یک گراف به کار میره .

توجه داشته باشید که یالها می تونن وزندار باشند البته فقط وزن های نامنفی !

این الگوریتم در دسته Greedy Algorithm ها یا "الگوریتم های حریصانه" قرار می گیره .

چون این الگوریتم تو هر لحظه بهترین نقطه ای که می تونه بهش برسه رو انتخاب می کنه و به اونجا میره و گره های همسایه ی اون رو update می کنه .

الگوریتم به صورت زیر عمل می کنه :

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

2. فاصله رسیدن به گره ابتدا رو 0 کن

3. تا زمانیکه همه گره ها mark نشده اند

الف. بین تمام گره های mark نشده ، گره با کمترین زمان رسیدن رو انتخاب کن

ب. گره فعلی رو mark کن

ج. فاصله رسیدن تا همه گره های همسایه ی گره فعلی رو update کن

پیاده سازی :

Distance[i] = infinity
mark[i] = false
Distance[ startNode ] = 0
for( i = 0 ; i < N ; i ++ )
{
    for( j = 0 ; j < N ; j ++ )
        if( mark[j] == false && Distance[j] < mn )
            mn = Distance[j], index = j;
    mark[index] = true;
    for( j = 0 ; j < N ; j ++ )
        if( matrix[index][j] > 0 && Distance[j] > Distance[i] + matrix[i][j] )
            Distance[j] = Distance[i] + matrix[i][j];
}

پیچیدگی زمانی این پیاده سازی (O(N^2 است . در گراف هایی که تعداد یال ها زیاد باشه کاربرد داره .

برای پیاده سازی بهتر می تونیم از یه صف اولویت Priority Queue استفاده کنیم .
تو این حالت پیاده سازی کد بسیار شبیه BFS خواهد شد .

پیاده سازی با صف اولویت

Priority Queue Q;
Set Distance[i] = infinity
Distance[ startNode ] = 0
Q.push( startNode )
while Q is not empty
    X = Q.pop()
    for each Y in Neighbours(X)
        if Distance[Y] > Distance[X] + Matrix[X][Y]
            Distance[Y] = Distance[X] + Matrix[X][Y]
            Q.push( Y )

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

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

از آنجا که هر یال حداکثر 1 بار می تواند یک راس را update کند ، الگوریتم حداکثر |E| گره را به صف اولویت اضافه می کند . حال از آنجا که هر عمل درج در صف اولویت در زمان (O(LogN انجام می شود ( N = تعداد اعضای موجود در صف ) زمان اجرای این الگوریتم |E| * Log|E| خواهد بود .