רוטר - |שאלה| בתורת הגרפים... כנסו.

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"|שאלה| בתורת הגרפים... כנסו."

גירסת הדפסה

קבוצות דיון לימודים, מדע ותרבות נושא #10936	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 10936

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

09:27 16.05.11

|שאלה| בתורת הגרפים... כנסו.

נניח שיש לי גרף מכווון ממשוקל ,
וישלי 2 קודקודים s,t
אני רוצה למצוא את המסלול המינימלי בינהם .
יש המון דרכים אבל אני רוצה לעמוד בזמן ריצה מסויים.
השאלה שלי היא כזאת , נניח שאני מוצא עץ פורש מינימלי לגרף.
הוא בהכרח יחזיק את המסלול הקצר בין שני הקודקודים בתוכו?

תודה!

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
אם אני זוכר נכון את ההגדרה של עץ מכוון, אז לא	D-KinG	16.05.11 20:17	1
העפ''מ שלך פה הוא	Yariv-H	17.05.11 08:40	2
צודק, מה עם זה?	D-KinG	17.05.11 12:14	3
אחלה תודה =]	Yariv-H	17.05.11 20:34	4
חפש בגוגל אלגוריתים דיקסטרה או בילמן פורד	waseem	17.05.11 23:26	5
האלגוריתמים האלו לא עונים על מה שביקשתי.	Yariv-H	17.05.11 23:48	6
וזה לא טוב כי...?	Zippo	18.05.11 02:25	7
אמ...	Yariv-H	18.05.11 16:47	8
למה פרים?!?!?	Zippo	18.05.11 21:20	9
אולי לא הייתי ברור בשאלה שלי...	Yariv-H	18.05.11 21:21	10
ברור שלא!	Zippo	18.05.11 23:05	11
תודה =]	Yariv-H	19.05.11 07:47	12
לא כועס. מתלהב. אלגוריתמים ומבני נתונים היו הקורסים שהכי אהבתי :)	Zippo	20.05.11 09:49	13
=] +1	Yariv-H	20.05.11 19:53	14

D-KinG
חבר מתאריך 8.6.02
3490 הודעות, דרג אמינות חבר זה

20:17 16.05.11

1. אם אני זוכר נכון את ההגדרה של עץ מכוון, אז לא
בתגובה להודעה מספר 0

למשל פה:
http://rotter.name/User_files/nor/graphics/4dd15bd675f1a1af.jpg

עפ"מ זה הקשתות ממשקל 4 ו-2, והוא לא מכיל את הקשת ממשקל 1

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

08:40 17.05.11

2. העפ''מ שלך פה הוא
בתגובה להודעה מספר 1

s->a->t
ולא
s->a & s->t

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

D-KinG
חבר מתאריך 8.6.02
3490 הודעות, דרג אמינות חבר זה

12:14 17.05.11

3. צודק, מה עם זה?
בתגובה להודעה מספר 2

http://imageshack.us/photo/my-images/593/imageode.jpg#

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

20:34 17.05.11

4. אחלה תודה =]
בתגובה להודעה מספר 3

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

waseem
חבר מתאריך 1.7.02
1045 הודעות, דרג אמינות חבר זה

23:26 17.05.11

5. חפש בגוגל אלגוריתים דיקסטרה או בילמן פורד
בתגובה להודעה מספר 0

כבר לא נהג חדש

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

23:48 17.05.11

6. האלגוריתמים האלו לא עונים על מה שביקשתי.
בתגובה להודעה מספר 5

הם מוצאים את המסלולים הקצרים והזולים ביותר בגרף.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Zippo
חבר מתאריך 26.5.02
7921 הודעות, דרג אמינות חבר זה

02:25 18.05.11

7. וזה לא טוב כי...?
בתגובה להודעה מספר 6

אתה מחפש מסלול מינימלי בין 2 קודקודים s,t
אם כל המשקלים חיוביים, תשתמש בדייקסטרה עם קודקוד התחלה s
אחרת, תריץ בלמן-פורד. (ואם אתה ממש רוצה להשקיע, תממש את ג'ונסון...)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

16:47 18.05.11

8. אמ...
בתגובה להודעה מספר 7

אתה מתכוון להריץ נניח פרים , ואז דייקסטרה?
ולראות האם המסלול בין S T שנותן דייקטסרה נמצא בעץ של פרים?
זה גם רעיון..

אבל השאלה שלי לא הייתה לגבי מימוש , אלה תאורתית יותר , האם בכלל קיים גרף כזה...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Zippo
חבר מתאריך 26.5.02
7921 הודעות, דרג אמינות חבר זה

21:20 18.05.11

9. למה פרים?!?!?
בתגובה להודעה מספר 8

אתה רוצה מסלול מינימלי! לא עפ"מ! שכח מפרים, שכח מקרוסקאל, שכח מיאו, שכח מסולין, או כל אלגוריתם אחר למציאת עץ פורש מינימלי.
אתה לא צריך עץ פורש מינימלי, רק מסלול מינימלי בין 2 קודקודים בגרף.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

21:21 18.05.11

10. אולי לא הייתי ברור בשאלה שלי...
בתגובה להודעה מספר 9

השאלה שלי הייתה , האם מסלול הכי קצר בין שני קודקודים בהכרח יהיה בתוך העפ"מ

והתשובה היא לא.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Zippo
חבר מתאריך 26.5.02
7921 הודעות, דרג אמינות חבר זה

23:05 18.05.11

11. ברור שלא!
בתגובה להודעה מספר 10

תחשוב על מעגל בו כל הקשתות מלבד קשת אחת שוקלות 1, ואילו הקשת הסוגרת שוקלת כמו סכום כל שאר הקשתות פחות אפסילון כלשהוא...
היא הקשת הכי כבדה במעגל, וע"פ משפט המעגלים הקלים לא מוכלת באף עפ"מ, מצד שני, היא המסלול הקצר ביותר המחבר בין שני קודקודיה (קצר באפסילון)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

07:47 19.05.11

12. תודה =]
בתגובה להודעה מספר 11

ולא צריך לכעוס =]

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Zippo
חבר מתאריך 26.5.02
7921 הודעות, דרג אמינות חבר זה

09:49 20.05.11

13. לא כועס. מתלהב. אלגוריתמים ומבני נתונים היו הקורסים שהכי אהבתי :)
בתגובה להודעה מספר 12

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Yariv-H

חבר מתאריך 24.3.02
5856 הודעות, 1 פידבק, 2 נקודות

19:53 20.05.11

14. =] +1
בתגובה להודעה מספר 13

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד