توضیحات
پیدا کردن کوتاهترین مسیر به صورت موازی با +C
در این پروژه از الگوریتم دایجسترا برای پیدا کردن کوتاه ترین مسیر به صورت موازی استفاده شده است. الگوریتم دایجسترا برای شروع نیاز به یک گراف وزن دار دارد که یال های این گراف میتواند دو طرفه و یا یک طرفه باشد. ما در این پروژه چند یال را دو طرفه و چند یال را یک طرفه در نظر گرفته ایم. برای پیدا کردن کوتاه ترین مسیر دو روش وجود دارد.
الف)پیدا کردن کوتاه ترین مسیر بین دو گره
ب)پیدا کردن کوتاه ترین مسیر بین از یک گره به همه گره ها
که ما از روش (ب) استفاده کرده ایم و کوتاه ترین مسیر از گره G به همه گره ها را به دست آورده ایم.
این پروژه شامل چند کلاس اصلی به شرح زیر میباشد:
- Graph
- Node
- NodeConnection
- DistanceCalculator
کلاس Graph برای ساختن و نگه داری گراف مورد نظر که از فایل خوانده می شود، می باشد.
هر گراف شامل چندین گره است که ما آن را با کلاس Node نشان می دهیم.
گره ها با یال هایی به هم متصل می شوند که در اینجا همان کلاس NodeConnection میباشد.
پیاده سازی و روند الگوریتم دایجسترا هم در کلاس DistanceCalculator آمده است.
Node:
کلاس Node شامل یک متغییر برای نگه داری نام گره (Name) و یک متغییر دیگر برای نگه داشتن فاصله از نقطه شروع(DistanceFromStart) که در اینجا پیش فرض G میباشد است.
این کلاس همچنین یک لیست از NodeConnection برای نگه داری یال ها(_connections) و یک تابع برای اضافه کردن یال به گره دارد(AddConnection)
NodeConnection:
این کلاس تنها دو متغییر دارد. یکی برای نگه داری مقصد(Target) که از جنس کلاس Node می باشد و دیگری برای نگه داری فاصله تا مقصد(Distance)
Graph:
کلاس گراف از یک دیکشنری برای نگه داری گره ها استفاده میکند. یال ها هم درون گره ها ذخیره میشوند.
کلاس گراف برای اضافه کردن گره و یال دو تابع در دسترس قرار داده است.
AddNode و AddConnection توابع مذکور می باشند.
خواندن گراف از فایل و پر کردن کلاس Graph نیز در فایل اصلی برنامه یا همان Program.cs انجام میشود.
DistanceCalculator :
در این کلاس توابع به صورت زیر می باشد:
- InitialiseGraph
- ProcessGraph
- ProcessNode
- ExtractDistances
- CalculateDistance
تابع InitialiseGraph ، گرافی را که program.cs از فایلی به نام graph.txt ساخته است، مقدار دهی اولیه میکند. به این صورت که مقدار “DistanceFromStart” را برای همه گره ها غیر از گره شروع (G) مثبت بی نهایت و برای گره شروع صفر می گذارد.
تابع ProcessGraph همه ی گره ها را به نسبت فاصله از نقطه شروع(DistanceFromStart) مرتب می کند و نزدیک ترین گره را برمیگرداند.
سپس این گره را از لیست موقت گره ها خارج میکند و برای پردازش به یک Thread دیگر میدهد و دوباره شروع به مرتب کردن گره ها میکند.
تابع ProcessNode ، در یک Thread جدید و با گره ای که ProcessGraph به آن داده است، کار می کند. به این صورت که فاصله گره ورودی از نقطه شروع را با فاصله اش تا گره های متصل به خودش جمع میکند. اگر این مجموع از فاصله گره های متصل نسبت به نقطه شروع کوتاه تر باشد، در DistanceFromStart آن گره متصل ثبت میشود.و این کار آنقدر تکرار میشود که تنها یک گره در لیست وجود داشته باشد.
تابع ExtractDistances یک دیکشنری از اسم گره به طول کوتاهترین مسیر به همه گره ها را بر میگرداند.
تابع CalculateDistance توابع دیگر را فراخوانی و اجرا میکند و تابع اصلی می باشد که در program.cs فراخوانی می شود.
فایل گراف(graph.txt)
در خط اول آن هر تعداد گره میخواهیم قرار میدهیم. و در خط های بعدی اتصالات را می گذاریم. آن true و false هم به معنای دوطرفه و یک طرفه میباشد.
نکات قابل ذکر:
- پیدا کردن کوتاهترین مسیر به صورت موازی با +C توسط کارشناسان گروه ۱.۲.۳ پروژه پیاده سازی گردیده و به تعداد محدودی قابل فروش می باشد.
- فایلهای پروژه به صورت کامل پس از خرید فایل بلافاصله در اختیار شما قرار خواهد گرفت.
دیدگاهها
هیچ دیدگاهی برای این محصول نوشته نشده است.