برگزیده های پرشین تولز

الگوریتم مسیریابی در گراف

scorpion8108

Registered User
تاریخ عضویت
24 می 2005
نوشته‌ها
344
لایک‌ها
0
سلام دوستان
می خواستم کوتاهترین مسیر رو در یه گراف پیدا کنم، همچنین با قطع شدن برخی یالها بشه بازهم مسیر رو پیدا کرد
کسی الگوریتم این مسئله رو داره
فکر کنم توی درس نرم افزار رشته مهندسی کامپیوتر باشه، یادم رفته :blush:
مرسی
 

pirmard

Registered User
تاریخ عضویت
21 آگوست 2007
نوشته‌ها
841
لایک‌ها
5
الگوریتم دیجسترا و بلمن فورد رو توی اینترنت سرچ کنین .
توی درس طراحی الگوریتم احتمالا خوندین .
مهندسی نرم رو نمی دونم .
توی درس شبکه هم هست .

اما اینکه با قطع شدن یالها باز هم بشه مسیر رو پیدا کرد رو نفهمیدم یعنی چی :(
 

pirmard

Registered User
تاریخ عضویت
21 آگوست 2007
نوشته‌ها
841
لایک‌ها
5
دیچسترا :
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

بلمن فورد :
http://en.wikipedia.org/wiki/Bellman-Ford_algorithm


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

The most important algorithms for solving this problem are:

* Dijkstra's algorithm — solves single source problem if all edge weights are greater than or equal to zero. Without worsening the run time, this algorithm can in fact compute the shortest paths from a given start point s to all other nodes.
* Bellman-Ford algorithm — solves single source problem if edge weights may be negative.
* A* search algorithm solves for single source shortest paths using heuristics to try to speed up the search
* Floyd-Warshall algorithm — solves all pairs shortest paths.
* Johnson's algorithm — solves all pairs shortest paths, may be faster than Floyd-Warshall on sparse graphs.
* Perturbation theory; finds (at worst) the locally shortest path
 

scorpion8108

Registered User
تاریخ عضویت
24 می 2005
نوشته‌ها
344
لایک‌ها
0
الگوریتم دیجسترا و بلمن فورد رو توی اینترنت سرچ کنین .
توی درس طراحی الگوریتم احتمالا خوندین .
مهندسی نرم رو نمی دونم .
توی درس شبکه هم هست .

اما اینکه با قطع شدن یالها باز هم بشه مسیر رو پیدا کرد رو نفهمیدم یعنی چی :(

ممنون پیرمرد، خدا عمرت بده :D
منظورم از قطع شدن یالها اینه که اگه مسیری بین دو تا node قطع بشه،الگوریتم کار کنه
ولی فکر می کنم این سوال مسخرس :D
الگوریتم خودش اینکار رو انجام میده
 

scorpion8108

Registered User
تاریخ عضویت
24 می 2005
نوشته‌ها
344
لایک‌ها
0
سلام
چطور میشه source و destination رو به الگوریتم داد و کوتاه ترین مسیر بین این دو نقطه و همچنین مسیری که برای این کوتاهترین مسیر طی می شه رو بدست آورد؟
مرسی
 

nsh

Registered User
تاریخ عضویت
19 ژانویه 2006
نوشته‌ها
685
لایک‌ها
4
محل سکونت
i & j : 2 & 3
در حقیقت اینا ماله طراحی الگوریتم و ساختمان های گسسته است
 

pirmard

Registered User
تاریخ عضویت
21 آگوست 2007
نوشته‌ها
841
لایک‌ها
5
سلام
چطور میشه source و destination رو به الگوریتم داد و کوتاه ترین مسیر بین این دو نقطه و همچنین مسیری که برای این کوتاهترین مسیر طی می شه رو بدست آورد؟
مرسی

سلام
یعنی نحوه ی فراخوانی تابع ؟ :wacko:
کدوم یکی ؟
 

pirmard

Registered User
تاریخ عضویت
21 آگوست 2007
نوشته‌ها
841
لایک‌ها
5
الگوریتم dijkstra رو میگم
ولی مثل اینکه نمیشه شروع و پایان node ها رو برای انتخاب کوتاهترین مسیر، مشخص کرد!

نقطه ی شروع رو که باید تعیین کرد
اما نقطه ی پایان معنی نداره . چون از اون نقطه ی شروع به همه ی نقاط مسیر اپتیمال رو میده بهت . خودت از تو ماتریس یا هر چیزی که تو خروجی بده ورمیداری دیگه :rolleyes:
 

scorpion8108

Registered User
تاریخ عضویت
24 می 2005
نوشته‌ها
344
لایک‌ها
0
نقطه ی شروع رو که باید تعیین کرد
اما نقطه ی پایان معنی نداره . چون از اون نقطه ی شروع به همه ی نقاط مسیر اپتیمال رو میده بهت . خودت از تو ماتریس یا هر چیزی که تو خروجی بده ورمیداری دیگه :rolleyes:

مرسی
خودم هم به همین نتیجه رسیدم
 
بالا