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

[armita]

به نظرتون چجوری می شه کوتاه ترین فاصله ی بین دو راس در یک گراف رو حساب کرد ؟ (اگر جواب رو می دونید یه دفعه نگین که بقیه فکر کنند )

 

[zabolian]

پاسخ : کوتاه ترین مسیر در گراف

گراف وزن دار باشه یا بی وزن؟
الان سعی کردم یه دفعه نگم

 

[trustme]

پاسخ : کوتاه ترین مسیر در گراف

خوب بهتر ه اول بی وزن رو بررسی کنیم ... بعد توی تصمیم گیری بررسی کنیم وزن دار چه فرقی با بی وزن داره

من یه نظر دارم ... هر راس با چند راس دیگه مجاور ه .. اینا رو مشخص می کنیم؛ بعد یه تابع بازگشتی بزاریم، بره تعداد راس هایی که به راس انتخاب شده وصل هستند رو پیدا کنه و چک کنه مسیر پیدا کرده یا نه، طول مسیر رو هم یکی اضافه کنه ... برای اینکه دور خودش بی خود چرخ نزنه، باید توی فرخواندن تابع، بررسی کنیم که آیا از اونجا رد شده یا نه.. ، اگه آره که برگرده یه مرحله بالاتر

اینطوری جواب می ده ؟!

 

[zabolian]

پاسخ : کوتاه ترین مسیر در گراف

تقریبا همینه، بدون تابع بازگشتی هم می شه راحت بیانش کرد، روش فکر کنید، قشنگه

 

[zabolian]

پاسخ : کوتاه ترین مسیر در گراف

اون قسمت بازگشتی رو می شه یه کم توضیح بدید، یعنی اگه رفت به یه همسایه و دید پیدا نکرده بعدش چی کار می کنه؟ یعنی دوباره برمیگرده راس پدر و کار رو ادامه می ده ( روی بقیه همسایه ها) یا اینکه این بار از این راس جدید دنبال مسیر میگرده؟

 

[trustme]

پاسخ : کوتاه ترین مسیر در گراف

اون قسمت بازگشتی رو می شه یه کم توضیح بدید، یعنی اگه رفت به یه همسایه و دید پیدا نکرده بعدش چی کار می کنه؟ یعنی دوباره برمیگرده راس پدر و کار رو ادامه می ده ( روی بقیه همسایه ها) یا اینکه این بار از این راس جدید دنبال مسیر میگرده؟

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

 

[zabolian]

پاسخ : کوتاه ترین مسیر در گراف

اون قسمت که چک می کنید جواب میده یا نه چه جوریه؟
اگه منظور شما رو درست فهمیده باشم:
مثلا فرض کنید ۱ به ۲ و ۳ یال داشته باشه و ۲ هم به ۳
حالا میخواهیم کوتاهترین مسیر رو از ۱ به ۳ چاپ کنیم ، الگوریتم شما ممکنه از ۱ به ۲ بره، بعد برای اینکه چک کنه می شه به ۳ رفت یا نه به طور بازگشتی از ۲ به ۳ بره، حالا یه مسیر جسته، اگه اینو چاپ کنید، که الگوریتم غلطه (چون مستقیم از ۱ به ۳ یال هست )
البته می تونید اینجوری تمام مسیرها را بجورید بعد ببینید کدوم کوتاهتره بعد چاپش کنید، که اصلا بهینه نیست، ولی درسته، یعنی الگوریتم شما برای پیدا کردن یه مسیر از یه راس به راس دیگه درست عمل میکنه، ولی اگه اولین مسیر پیدا شده رو در نظر بگیریم ممکنه کوتاهترین نباشه، در حالی که الگوریتمی وجود داره که اولین مسیری که پیدا می کنه کوتاهترین هم هست و خوب اون بهینه تره، خیلی هم شبیه الگوریتم شماست

 

[armita]

پاسخ : کوتاه ترین مسیر در گراف

دیگه نظری ندارین ؟

 

[zabolian]

پاسخ : کوتاه ترین مسیر در گراف

یه الگوریتم به نام bfs هست که توی گرافهای بدون وزن کوتاهترین مسیر از یه راس به تمام راس‌های دیگه رو حساب میکنه، اونم اینجوریه که دو تا آرایه میگیریم به اندازه تمام راسها یکی واسه‌ی مارک کردن راسهایی که تا حالا رفتیم ( یعنی اگه راس دهم رو یه بار رفتیم مارک خونه دهم رو true میکنیم) اون یکی هم واسه اینکه راسهایی که تاحالا ملاقات کردیم رو به همون ترتیبی که ملاقاتشون میکنیم رو بریزیم تو اون. ( به اینجا که رسید دیدم توضیح فارسی دادن خیلی طول میکشه، کد ++C رو گذاشتم )

const int maxn=100*1000;
bool mark[maxn];
int q[maxn];
int dis[maxn];
int par[maxn];


void bfs(int v){
int start=0;
int end=0;
mark[v]=true;
dis[v]=0;
par[v]=-1;
q[end++]=v;
while(start<end){
v=q[start++];
for(int i=0;i<adj[v].size();i++){
if(!mark[adj[v]])
mark[adj[v]=true;
par[adj[v]=v;
q[end++]=adj[v];
dis[adj[v]]=dis[v]+1;
}
}
return;
}​

کد بالا کوتاهترین مسیر از راس v به بقیه راس ها رو پیدا میکنه، برای چاپ اندازه مسیر از v به راس i ام از dis و برای چاپ این مسیر با یه تابع بازگشتی از آرایه‌ی par استفاده میکنیم ( پدر هر راس رو تو درخت ریشه دار با ریشه v رو تو خودش نگه میداره)
آرایه adj هم همسایه‌ی های هر راس رو تو خودش نگه میداره

فکر کنم با این توضیحات و با خوندن کد بالا بتونید الگوریتم رو متوجه بشید

 

[سروش ربیعی]

پاسخ : کوتاه ترین مسیر در گراف

... و برای گراف‌های وزن‌دار دو فقره الگوریتم هست به اسمای وارشال-کروسکال و دیجکسترا. البته این الگوریتم‌ها درخت‌های فراگیر بهینه رو بیرون میدن. تو این درخت‌ها کوتاه‌ترین فاصله بین دو رأس کمترین وزن مسیر رابط بین اوناست. توضیحات مربوطه رو نمی‌نویسم چون اولاً حال ندارم. دوماً می‌تونین خیلی کامل‌ترشو از ویکی فارسی پیدا کنید:

http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%DA%A9%D8%B1%D9%88%D8%B3%DA%A9%D8%A7%D9%84

http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AF%DB%8C%DA%A9%D8%B3%D8%AA%D8%B1%D8%A7

حواستون باشه که اگه تو گرافتون وزن منفی دارین دایجسترا روش کار نمی‌کنه ها حسن! باید همۀ وزن‌ها رو شیفت بدین تا از منفی بودن دران. و یا اینکه اگه این کار به دلایل معناشناختی ممکن نباشه؛ از الگوریتم بلمن-فورد استفاده کنید.

 

[narenjak]

پاسخ : کوتاه ترین مسیر در گراف

... و برای گراف‌های وزن‌دار دو فقره الگوریتم هست به اسمای وارشال-کروسکال و دیجکسترا. البته این الگوریتم‌ها درخت‌های فراگیر بهینه رو بیرون میدن. تو این درخت‌ها کوتاه‌ترین فاصله بین دو رأس کمترین وزن مسیر رابط بین اوناست. توضیحات مربوطه رو نمی‌نویسم چون اولاً حال ندارم. دوماً می‌تونین خیلی کامل‌ترشو از ویکی فارسی پیدا کنید:

http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%DA%A9%D8%B1%D9%88%D8%B3%DA%A9%D8%A7%D9%84

http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AF%DB%8C%DA%A9%D8%B3%D8%AA%D8%B1%D8%A7

حواستون باشه که اگه تو گرافتون وزن منفی دارین دایجسترا روش کار نمی‌کنه ها حسن! باید همۀ وزن‌ها رو شیفت بدین تا از منفی بودن دران. و یا اینکه اگه این کار به دلایل معناشناختی ممکن نباشه؛ از الگوریتم بلمن-فورد استفاده کنید.

و اضافه کنم روش های داینامیک هم هست ها (البته تا اونجا که یادمه)

 

[maziar]

پاسخ : کوتاه ترین مسیر در گراف

کلن برایه فکر کردن برایه حل مسائل بهتره اول یه راهه بازگشتی پیدا کنی
چرا که استقرا دقیقن داره بهت اجازه میده با راهه بازگشتی مساله رو حل کنی.
دقیقن ایده ی بی اف اس و دی اف اس همینه
با این فرق که بی اف اس با تفاوتی که با دی اف اس داره کوتاه ترین مسیر رو میده ولی دی اف اس فقط یه مسیر میده جالا کوتاه ترین یا بلند ترین

ولی تو گراف وزن دار باید با دیچیکسترا بری

کد زدنش شاید یه ذره سخت باشه ولی می تونی الگوریتمشو راحت پیده کنی

BFS , DFS
Djkstra

بعد سعی کن خودت کدشو بزنی بی خیاله بیسیک شو.

بعد می تونی راهه حل هایه بهترشو گوگل کنی با اون زبان خاصی که می خوای

 

[Dark Eagle]

پاسخ : کوتاه ترین مسیر در گراف

کلن برایه فکر کردن برایه حل مسائل بهتره اول یه راهه بازگشتی پیدا کنی
چرا که استقرا دقیقن داره بهت اجازه میده با راهه بازگشتی مساله رو حل کنی.
دقیقن ایده ی بی اف اس و دی اف اس همینه
با این فرق که بی اف اس با تفاوتی که با دی اف اس داره کوتاه ترین مسیر رو میده ولی دی اف اس فقط یه مسیر میده جالا کوتاه ترین یا بلند ترین

ولی تو گراف وزن دار باید با دیچیکسترا بری

کد زدنش شاید یه ذره سخت باشه ولی می تونی الگوریتمشو راحت پیده کنی

BFS , DFS
Djkstra

بعد سعی کن خودت کدشو بزنی بی خیاله بیسیک شو.

بعد می تونی راهه حل هایه بهترشو گوگل کنی با اون زبان خاصی که می خوای

اگه هدفتون پیدا کردن کوتاه ترین مسیر بین هر دو راس باشه با n تا BFS میشه به جواب رسید که اوردرش n به توانه 3 اه.........
از یه روش دیگه هم میشه استفاده کرد که تقریبا شبیه پویا میمونه .............
اونم اوردرش n به توان 3 اه ولی کلا با BFS فرق داره ............
الان اسمش یادم نیس ولی تو مایه های پویاست............
BFS / DFS رو زیاد گنده نکنید .......... B-)
چیزه خیلی خاصی نداره فقط یادتون باشه قبل مرحله 3 چند بار کدشو بزنید دستتون راه بیفته...........
داش مازیمون دایسترا اه نه دیجکسترا ..........(فارسیشو میگم)
یک سوال : میشه BFS / DFS رو با هم قاطی کرد یعنی تو بعضی حالت ها با چک کردن یه if یکیشون رو بزنه تو else اش اون یکی رو..........
؟؟؟
B-)

 

[kerpoocoder]

پاسخ : کوتاه ترین مسیر در گراف

پستا رو که می خوندم به نظرم از سال 2009 تا الان خیلی مطلب جامعی در مورد این مسئله ارائه نشده من سعی می کنم ی توضیح کاملی ارائه بدم باشد که مفید واقع گردد.

کلا چهار تا الگوریتم معروف برای حل این مسئله وجود داره که هر کدوم جایی کاربرد دارن و نقاط ضعف و قوتی نسبت به بقیه دارن

هر کدوم از اینا رو تو ویکی سرچ کنید همه چی رو درباره شون میاره من فقد نقاط ضعف و قوتشون و رو می گم

1- Floyed-Warshall

یه الگوریتمه داینامیک از (O(n^3 هست[nb]منظور از n و |V| همون تعداد راس و |E| همون تعداد یال هست .[/nb] که پیاده سازی راحتی داره کوتاهترین فاصله بین هر دو راس از گراف رو بعد از اجرا توی ی ماتریس دارین برای تمام گراف ها هم درست کار می کنه (یال های وزن دار حتی منفی به شرطی که دور منفی نداشته باشیم) ایراد این الگوریتم اولا زمان اجراشه ثانیا کوتاهترین مسیر رو تو گراف بین دوتاراس نمی تونید چاپ کنید فقط میتونید طولشو داشته باشید.

2- dijkstra

یه الگوریتم گریدی که برای گراف های با یال وزن دار (وزن های غیر منفی) کوتاهترین مسیر رو ارائه می ده زمانش هم (|O(|E|log|v هست البته با ساختمان داده fibonacci heap می شه با زمان (|O(|v|^2+|v|log|v پیاده ش کرد که زمانش بسته به گراف بین vlogv و v^2 متغیره.
فقط کوتاهترین فاصله بین یک راس و سایر راس ها رو بهتون می ده و خوبی دیگه ای هم داره اینه که می تونید ی درخت dijkstra موقع اجرا درست کنید که بعد از اجرا یکی از کوتاهترین مسیر های بین دو راس رو با یه DFS یا BFS تو درخته چاپ یا ذخیره کنید. اما برای گراف هایی با یال منفی درست کار نمی کنه.

3- Bellman-ford

این الگوریتم برای گراف های با دور منفی هم کوتاهترین مسیر رو چاپ می کنه زمانش هم (|O(|E|*|V و می تونه تشخیص بده بین دو راس یک کوتاهترین مسیر وجود داره یا یک دور منفی وجود دارد (دور منفی باعث ایجاد یک لوپ میشود که کوتاهترین فاصله را در هر مرحله کم تر می کند)

4- BFS

این الگوریتم از (|O(|E هست (E تعداد یال های اون مولفه همبندی مونه البته توی این مسئله خاص زمانش کم شده توی کابرد های دیگه تعداد راس ها و کل یال ها هم مهم می شه) که فقد برای گراف های بی وزن درست کار می کنه در واقع توی این مسئله حالت خاص الگوریتم دایکسترا برای گراف های بی وزنه که عمل سرچ کردن ازش حذف شده و اون logv که به صورت ضرب اومده بود برداشته می شه. چون همه یال های هم وزنن دیگه نیازی به سرچ نیست و سطح به سطح یال ها رو طی می کنیم. :)
پس بچه اون محسوب می شه و برای گراف های بی وزن همون خواص دایکسترا رو داره. :) مثه چاپ مسیر و درخت BFS

خب فک کنم برای کسایی که می خوان برن رو شاخ این مسئله الان بدونن باید چه کار کنن

 

[Anita H]

پاسخ : کوتاه ترین مسیر در گراف

2- dijkstra

یه الگوریتم گریدی که برای گراف های با یال وزن دار (وزن های غیر منفی) کوتاهترین مسیر رو ارائه می ده زمانش هم (|O(|E|log|v هست البته با ساختمان داده fibonacci heap می شه با زمان (|O(|v|^2+|v|log|v پیاده ش کرد که زمانش بسته به گراف بین vlogv و v^2 متغیره.
فقط کوتاهترین فاصله بین یک راس و سایر راس ها رو بهتون می ده و خوبی دیگه ای هم داره اینه که می تونید ی درخت dijkstra موقع اجرا درست کنید که بعد از اجرا یکی از کوتاهترین مسیر های بین دو راس رو با یه DFS یا BFS تو درخته چاپ یا ذخیره کنید. اما برای گراف هایی با یال منفی درست کار نمی کنه.

همش قبول ولی دایسترا گریدیه؟

 

[kerpoocoder]

پاسخ : کوتاه ترین مسیر در گراف

آره دیگه شبیه پریم هم هست.
تو هر مرحله از بین مجموعه راس هایی که به راس های درختمون تا الان وصلن اونی رو به درخت اضافه میکنیم که مجموع یال بین خودش و پدرش+فاصله پدر از ریشه از بقیه راس ها کمتر باشه بچه هاش رو هم اضافه که می کنیم با یال پدر فعلی شون+فاصله پدر تا ریشه در صورت وجود مقایسه می کنیم کمترین رو پدر اون راس قرار میدیم کاملا نگرش گریدی داره. خود مسئله هم که دنبال ی کمینه ست.

 

[Anita H]

پاسخ : کوتاه ترین مسیر در گراف

ولی من هنوزم فکر میکنم دی پیه
ولی قبول دارم که نگرش گریدی هم داره
مثل اون سواله پیدا کردن زیردنباله ی متوالی با بیشینه مجموع عناصر هست که هم میشه به دید گریدی نگاهش کرد و هم میشه به دید دی پی نگاهش کرد :/

پ.ن: #نبش_قبر

 

[hamid.iran]

سلام به همه عزیزان
دوستان بزرگوار برای حل این مسئله نیاز به کمک دارم.بی نهایت سپاسگزارم

سوال:
یک آرایه دو بعدی با ۴ ستون و n سطر مفروض است.
۱- ستون اول نام نود (مثلاً A)
۲- ستون دوم نام نود بعدی (مثلا B)
۳- ستون سوم هزینه ناخالص رفتن از نقطه A به نقطه B
۴- ستون چهارم خالص هزینه رفتن از نقطه A به نقطه B
۵- هزینه رفتن از A به B یا از B به A یکی است
A -> B = B -> A

۶- حداقل باید بیش از ۲ نود پیمایش شود مثلا
A -> B -> C -> A
--------------------------------------
خواسته الگوریتم:

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

نکته: گاهی اوقات ممکن است خالص هزینه محاسبه شده در یک مرحله منفی هم باشد.
-------------------------------------
بطور مثال ماتریس زیر :
A - B - 0.6 - (0.03)
B - C - 8.18 - (-1.05)
A - C - 4.16 - (2.01)
C - D - 7.22 - (-0.52)
B - D - 12.01 - (0.71)
A - D - 3.45 - (1.35)