آمار پرسش:

• پرسیده شده: 2014-08-03 13:20:01 -0500
• مشاهده شده: 1,189 بار
• بروز شده: 2014-11-12 10:42:31 -0500

پرسش‌های مشابه:

آیا گراف قویا همبند است؟

پیدا کردن مولفه های قویا همبند گراف جهت دار

یافتن کوتاه ترین دور در گراف ساده

کد برای بررسی یک ریختی 2 گراف

جزوه ی برنامه نویسی قسمت (گراف)

شبکه $n\times n$ پایدار

پیدا کردن گراف دوبخشی کامل یکرنگ

حداکثر تعداد یال‌های گراف بدون مثلث

یافتن کوچکترین پیچ و مهره با مقایسه آنها

آشپزباشی:‌ مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

پيدا كردن دومين كوتاهترين مسير بين دو راس گراف با توجه به الگوريتم ديكسترا

4

با توجه به اين كه الگوريتم ديكسترا الگوريتمي براي پيمايش گراف و يافتن كوتاهترين مسير بين دو راس يك گراف وزن دار است ، به نظر شما بهترين روش براي پيدا كردن دومين كوتاهترين مسير بين دو راس يك گراف چيست ؟

گراف الگوریتم

2014-08-03 13:20:01 -0500

مبیدیک 234 ● 3 ● 4 ● 12

پاک‌کردن   ویرایش سوال

نظرات

این ایده که کوتاه‌ترین مسیر رو در نظر بگیریم و یال‌هاش رو به نوبت پاک کنیم و بعد رو گراف باقیمانده دنبال کوتاه‌ترین مسیر بگردیم خوب نیست؟

2014-08-03 15:08:34 -0500 فامیل دور

سلام ، ممنون كه نظر دادي . منظورت از اينكه يالها رو به نوبت پاك كنيم چيه ؟ اگه ميشه توضيح بده .

2014-08-03 15:13:28 -0500 مبیدیک

نه این ایده غلطه . چون شاید دومین کوتاهترین مسیر از تعدادی از این یالهای کوتاهترین مسیر استفاده کنه .

2014-08-23 14:42:12 -0500 حمید کاملی

فکر کنم منظور فامیل دور این بود که هر بار یک یال از کوتاه ترین مسیر رو حذف کنیم و توی گراف حاصل دنبال کوتاهترین مسیر بگردیم (که قطعا مساوی کوتاه ترین مسیر گراف اصلی نیست) و دوباره یال رو برگردونیم سرجاش یال بعدی رو حذف کنیم. آخر بین همه کوتاهترین مسیرهای یافته شده، حداقل رو به عنوان جواب اعلام کنیم

2014-08-23 15:37:19 -0500 کلاه قرمزی

سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com

2015-08-06 08:15:47 -0500 امیر شکری

6

مسیر دوم رو در نظر بگیرید٬ قبول دارید فقط در یکجا با کوتاه ترین مسیر برخورد داره؟
چون اگه در ۲ جا برخورد داشته باشه تو فاصله میون ۲ تا برخورد از کوتاه ترین مسیر استفاده میکنیم و به نقطه برخورد دوم میریم. این مسیر از مسیر دومی که فرض کردیم کوتاه تره ولی با کوتاه ترین مسیر هم یکی نیست!
در الگوریتم دایجکسترا کوتاهترین فاصله تا همه نقاط پیدا میشه پس میایم به اضای همه راس های v به طوری که راس v حداقل یه همسایه داشته باشه که عضو کوتاه ترین مسیر باشه for میزنیم:

(for (v: hamsaye kootah tarin masir
[mn = min(mn, dist[v] + yal[v][hamsaye v ke tooye kootahtarin masire

[dist[v هم که بدیهیه چیه! [yal[u][v وزن یال بین این دوتاست.
کوتاه ترین مسیر دوم میشه کوتاه ترین مسیر به راسی که آخرین بار mn رو آپدیت کرده (قسمت اول مسیر)
کوتاه ترین یال آخرین راسی که mn رو آپدیت کرده به کوتاه ترین مسیر (قسمت دوم)
ادامه مسیر از این راسی که توشیم تا راس مقصد به طوری که همون راهی رو طی کنیم که اولین کوتاه ترین مسیر هست.
اردر این روش هم $ O( N + M)$ هست.

و بدین سان دومین کوتاه ترین مسیر پیدا میشود :)
$^_^$

2014-08-24 13:20:56 -0500

کلم برگ 599 ● 2 ● 4 ● 16

پاک‌کردن   ویرایش پاسخ

1

من این ایده رو پیش‌نهاد می‌کنم که شبه کدشو گذاشتم:

shortest path = dijkstra(G)
second shortest path = infinity weight path
for each edge in shortest path do
    let temp be weight of edge
    weight of edge = infinity
    temp path = dijkstra(G)
    second shortest path = min(second shortest path, temp path)
    weight of edge = temp

return second shortest path
 
البته اصلا بهینه نیست، روش دیگه‌ای به ذهنم نمی‌رسه.
 

2014-08-23 12:51:27 -0500

یوسفی 631 ● 2 ● 15

پاک‌کردن   ویرایش پاسخ