الگوريتم مسئله کوتاهترین مسیر ( Shortest Path Problem )
http://pnu-club.com/imported/mising.jpg
مسئله کوتاهترین مسیر یکی از مسائل مطرح شده در نظریه گراف ها می باشد . از جمله کاربرد های این مسئله می توان به کاربردهای ارتباطی و حمل و نقل اشاره کرد . هدف این مسئله یافتن کوتاهترین مسیر از یک گره به گره دیگر در یک گراف جهت دار می باشد . یکی از الگوریتم های مطرح شده برای حل این مسئله ، الگوریتم فلوید می باشد . الگوریتم فلوید با استفاده از تکنیک برنامه نویسی پویا ، مسئله کوتاهرین مسیر در گراف جهت دار را حل می کند.
ابتدا ماتریسی دو بعدی که نشان دهنده وزن یالهای جهت دار است ، تشکیل می دهیم . این آرایه را ماتریس وزن ها یا ماتریس 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 نقشه ترسیم شده را ذخیره می کند .
