انتخاب کوتاهترین مسیر

[pegah1371]

سلام، کسی چیزی درباره ی انتخاب کوتاهترین مسیر بین ۲ نقطه به کمک الگوریتم DFS می دونه؟

[pegah1371]

دوستاااااااااااااان!!!!!!
کمک می خوام ها
یعنی هیچکی نیس به داد من برسه؟!؟!

[godfather]

از DFS منظورت Depth first search?
منظورتون چیه از کوتاهترین فاصله؟ توی گراف؟ یا ؟
یکم واضحتر میگین!

[Hooman kh]

منظورتون کوتاه ترین مسیر بین دو نقطه در صفحه دوبعدی یا در فضا هست؟

[godfather]

فکر نکنم منظورش اون باشه!
آخه DFS یه متودِ تو گراف و علوم کامپیوتر!

[javad123javad]

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

ترتیب کاوش:A, B, D, F, E, C, G(از چپ به راست)

کد: انتخاب همه

FS (V, E)

1.     for each vertex u in V[G]
2.        do color[u] ← WHITE
3.                π[u] ← NIL
4.     time ← 0
5.     for each vertex u in V[G]
6.        do if color[u] ← WHITE
7.                then DFS-Visit(u)              ▷ build a new DFS-tree from u

 

DFS-Visit(u)

1.     color[u] ← GRAY                         ▷ discover u
2.     time ← time + 1
3.     d[u] ← time
4.     for each vertex v adjacent to u     ▷ explore (u, v)
5.        do if color[v] ← WHITE
6.                then π[v] ← u
7.                        DFS-Visit(v)
8.     color[u] ← BLACK
9.     time ← time + 1
10.   f[u] ← time                                 ▷ we are done with u

مثالی دیگر:

[metra70]

با اجازه منم یه توضیح مختصری میدم

dfs.gif

یال هایی که شمارش ميشوند، داراي دو عدد هستند كه اولي زمان ملاقات آنها و دومي زمان برگشت به آنها است. يال هاي درختي همان يالهاي پيمايش شده در dfs هستند. يالهاي back(بازگشتي) يالهايي هستند كه نود ابتداي يال، فرزند نود انتهاي يال باشد. يالهاي forwardهم يالهايي هستند كه ابتداي آنها جد نود انتهايي است ولي در پيمايش dfs پيمايش نميشوند.
ديگر يالها را صليبي Cross گوييم. اين يال هاي ممكن است از دو درخت جدا بوده و دو درخت را به هم وصل كنند. که همانطور که در شکل بالا میبینی دو تا یال Cross داریم. که سه تا درخت رو به همدیگه وصل میکنه و در هر درخت بررسی ازسمت چپ شروع میشه و...