|
|
עמוד:236
אפשר לתאר את האלגוריתם כך : . 1 קבע את צומת המקור לצומת הפעיל ; . 2 בחן את כל השכנים של הצומת הפעיל , אם אחד מהם הוא צומת היעד - סיים ; ? . 3 בחר את השכן הקרוב ביותר והפוך אותו לצומת פעיל . 4 חזור . 2-ל אלגוריתם כזה ( שנקרא אלגוריתם חמדן ) הוא פשוט ביותר , אך לרוע המזל הוא אינו נכון . כדי להמחיש זאת , נסה להריץ אותו על הגרף שלהלן , שבו צומת A הוא צומת המקור וצומת E הוא צומת היעד . נפנה עתה לסקירת אלגוריתם נכון למציאת המסלול הקצר ביותר בגרף . אלגוריתם זה נקרא , על שם החוקר שהמציא אותו , האלגוריתם של דייקסטרה ( Dijkstra ) והוא נלמד בדרך-כלל במסגרת תורת הגרפים . האלגוריתם משתמש בפריטים האלה ! לכל צומת בגרף > שתהית שהיא מספר המייצג את המרחק של הצומת מצומת המקור , S דרך המסלול הקצר ביותר הידוע עד אותו רגע . בתחילת האלגוריתם , התווית של S היא , 0 והתוויות של כל הצמתים האחרים הן . 00 תווית של צומת יכולה להיות ז מנית או קבועה . בתחילת האלגוריתם , התוויות של כל הצמתים הן זמניות , והן הופכות לקבועות במהלך פעולת האלגוריתם . בכל שלב של האלגוריתם יש צומתפ >> 1 / . אחד ( בשלב הראשון , צומת S הוא הפעיל . ( איור 4 . 20 גרף לבדיקת פעולתו של אלגוריתם חמדן
|
|