|
|
مسئله کوتاهترین مسیر ( Shortest Path Problem )
|
|
|
مسئله کوتاهترین مسیر یکی از مسائل مطرح شده در نظریه گراف ها می باشد . از جمله
کاربرد های این مسئله می توان به کاربردهای ارتباطی و حمل و نقل اشاره کرد . هدف
این مسئله یافتن کوتاهترین مسیر از یک گره به گره دیگر در یک گراف جهت دار می باشد
. یکی از الگوریتم های مطرح شده برای حل این مسئله ، الگوریتم فلوید می باشد .
الگوریتم فلوید با استفاده از تکنیک برنامه نویسی پویا ، مسئله کوتاهرین مسیر در
گراف جهت دار را حل می کند.
ابتدا ماتریسی دو بعدی که نشان دهنده وزن یالهای جهت دار است ، تشکیل می دهیم . این
آرایه را ماتریس وزن ها یا ماتریس weight می نامند . ماتریس دیگری نیز با نام
distance ایجاد می کنیم که مقدار اولیه آن برابر مقدار ماتریس وزن ها است . شبه کد
زیر نحوه پیاده سازی الگوریتم فلوید را شرح می دهد :
|
Procedure Floyd
Begin
Copy weight matrix to distance matrix
N = number of nodes
For k = 0 to N
For i = 0 To N
For j = 0 To N
distance[i,j]=Min( distance[i,j],distance[i,k]+distance[k,j])
End For
End For
End For
End
|
|
نحوه استفاده از برنامه
برنامه فقط شامل یک پنجره اصلی است که همه ورودی ها در این پنجره وارد می شوند .
پنجره اصلی برنامه از سه قسمت تشکیل یافته است . در سمت راست صفحه ترسیم نقشه قرار
دارد . در این صفحه می توانید گراف بدون جهت مورد نظر را ترسیم کنید . در سمت چپ
نیز یالهای خارج شده و وارد شده از هر گره به همراه وزن هریک از یالها و همچنین
فاصله مستقیم هر گره از بقیه گره ها نشان داده می شود . قسمت بالایی فرم نیز شامل
نوار ابزاری است که همه عملیات توسط دگمه های قرار گرفته بر روی نوار ابزار انجام
می شوند .
ترسیم گراف در صفحه ترسیم
صفحه ترسیم در سمت راست فرم قرار دارد . برای قرار دادن گره ها بر روی این صفحه
کافی است بر روی نقطه مورد نظر یک بار کلیک کنید . با یک بار کلیلک کردن بر روی
صفحه ترسیم گره ای به صفحه اضافه می شود . برای حذف گره نیز می توانید بر روی گره
مورد نظر دابل کلیک کنید . برای انتخاب گره نیز کافی است بر روی گره یک بار کلیک
کنید . گره انتخاب شده رنگ متفاوتی نسبت به سایر گره ها خواهد داشت .
زمانی که گره ای را انتخاب می کنید ، نام آن گره به همراه همه یالهای متصل به این
گره در قسمت بالای سمت چپ پنجره به نمایش در می آیند . نام گره و وزن یال ها را می
توانید در این قسمت تغییر دهید . در صورتی که یالی از گره انتخاب شده به دیگر گره
ها وجود نداشته باشد ، بخش بالایی سمت چپ فقط نام گره را نشان خواهد داد . در قسمت
پایینی سمت چپ نیز فاصله مستقیم گره انتخاب شده از بقیه گره ها به نمایش در می آیند
. این مقادیر را نیز می توانید تغییر دهید . به صورت پیش فرض هنگامی که یالی بین دو
گره رسم می شود ، فاصله بین این دو گره ( وزن یال ) فاصله اقلیدسی بین آن ها در نظر
گرفته می شود.
ترسیم یال از گره 1 به گره 2
ابتدا با کلیک کردن بر روی گره 1 آن گره را انتخاب کنید . سپس کلید Ctrl را فشار
داده و و بر روی گره 2 کلیک کنید . در این هنگام یالی بین گره 1 و گره 2 ترسیم می
شود . در صورتی که یالی بین گره اول و گره دوم وجود داشته باشد و سعی در ترسیم
دوباره یال داشته باشید ، برنامه از ترسیم یال خودداری کرده و سیگنالی را برای
آگاهی شما پخش می کند .
می توانید نقشه ترسیم شده را ذخیره کرده و یا نقشه ذخیره شده ای را باز کنید . برای
این منظور می توانید از دکمه های قرار گرفته بر روی فرم استفاده کنید . دکمه New یک
صفحه ترسیم جدید باز می کند . دکمه Load فایل نقشه را باز می کند و دکمه Save نقشه
ترسیم شده را ذخیره می کند .
|
|