דף 1 מתוך 1

פרים ודייקסטרה

נשלח: 15:49 23/07/2009
על ידי YossiCo
מה ההבדל בינהם? הם נראים ממש אותו דבר...
:?:

Re: פרים ודייקסטרה

נשלח: 17:11 23/07/2009
על ידי TA_Gila
המבנה שלהם דומה, אבל הנקודה המרכזית שונה בהחלט-
באלגוריתם של פרים העדכון של המחיר של קדקד שנמצא בערימה נעשה לפי משקל הצלע שנכנסת אליו ושמחברת בינו לבין הקדקד הנוכחי שהוצאנו מהערימה וחיברנו לMST המתהווה.
באלגוריתם דייקסטרה המחיר המעודכן של קדקד יהיה סכום של משקל הצלע הזו והקדקד הנוכחי.

פרים בונה MST ואכפת לנו ממשקלי הצלעות הבודדות. דייקסטרה מחשב מסלולים קצרים ולכן אכפת לנו ממשקל כל הצלעות על המסלול ולא רק ממשקלה של הצלע האחרונה.

Re: פרים ודייקסטרה

נשלח: 21:16 23/07/2009
על ידי halpertc
מה זה דייקסטרה? לא זכור לי שזה הופיע בשיעורים/תרגולים

Re: פרים ודייקסטרה

נשלח: 21:17 23/07/2009
על ידי yosefer
גם אני לא זוכר דייקסטרה
ובכלל אמרו שלא יהיה פרים
אז נראה לי שהדיון הזה מיותר