پاورپوینت ساختمان داده ها فصل اول الگوریتمهای کوتاهترین مسیر (pptx) 19 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 19 اسلاید
قسمتی از متن PowerPoint (.pptx) :
ساختمان دادهها الگوریتمهای کوتاهترین مسیر
مساله کوتاهترین مسیر برای یک فرستنده
مساله کوتاهترین مسیر برای یک فرستنده
از یک نود شروع کنید و کوتاهترین مسیر به سمت بقیه ی نودها را پیدا کنید.
الگوریتم دکسترا
به صورت حریصانه کوتاهترین مسیرها را پیدا کنید. یعنی هر بار نودی که کمترین فاصله را دارد را انتخاب کرده و فاصله ی بقیه نودها را نسبت به نودهای انتخاب شده تازه کنید.
کاربردها:
مسافرت از طریق نقشه
آنالیز تاخیر مدارات دیجیتال
سیم کشی و جانمایی مدارات دیجیتال
مسیریابی شبکه
تجارت
مساله ی کوتاهترین مسیر
وزن: هزینه، فاصله، مدت زمان صفر، گام ...
1
3
4
10
5
7
2
5
6
u
v
مثالی از الگوریتم دکسترا
الگوریتم حریصانه: کوتاهترین مسیر را ار V0 پیدا کنید.
تمام وزنها بزرگتر از صفر هستند.
0
1
2
3
4
5
10
2
3
1
2
7
4
9
6
source
مثالی از الگوریتم دکسترا
قدم اول: کوتاهترین مسیرها از نود صفر را پیدا کنید.
نود ۲ انتخاب می شود.
0
1
2
3
4
5
10
2
3
1
2
7
4
9
6
source
مثالی از الگوریتم دکسترا
قدم ۲: دوباره کوتاهترین مسیرها را محاسبه کنید.
این بار نود ۴ انتخاب می شود.
0
1
2
3
4
5
10
2
3
1
2
7
4
9
6
source
مثالی از الگوریتم دکسترا
0
1
2
3
4
5
10
2
3
1
2
7
4
9
6
source
قدم ۳: دوباره کوتاهترین مسیرها را محاسبه کنید.
این بار نود ۱انتخاب می شود.
مثالی از الگوریتم دکسترا
0
1
2
3
4
5
10
2
3
1
2
7
4
9
6
source
قدم ۴: دوباره کوتاهترین مسیرها را محاسبه کنید.
این بار نود ۳ انتخاب می شود.
مثالی از الگوریتم دکسترا
حال ما کوتاهترین مسیرها از نود صفر به همه ی نودها را داریم.
0
1
2
3
4
5
10
2
3
1
2
7
4
9
6
source
