בגרף מכוון ממושקל ללא מעגלים,
ע"י הקלת הקשתות לפי הסדר המוחזר ממיון
טופולוגי על הגרף, ניתן לחשב מסלולים קצרים ביותר ממקור
יחיד בזמן לינארי.
האלגוריתם מתחיל במיון טופולוגי של הגרף כדי לסדר את הקודקודים
בסדר לינארי. תזכורת : אם קיים מסלול מ u אל v אז קודקוד
u יבוא לפני קודקוד v בסדר הטופולוגי.
באלגוריתם, אנו מבצעים מעבר אחד בלבד על הקודקודים לפי הסדר
שנקבע במיון הטופולוגי, שבמהלך המעבר על הקודקוד, מתבצעת
הקלה על שכניו.
מסלולים קצרים ביותר תמיד מוגדרים בגרף מכוון ללא מעגלים,
כי כמובן לא ייתכן בו מעגל שלילי.
פסאודו קוד
1. sort the
vertices of G by topologically sort
2. INITIALIZE-ESTIMATES
(G,s)
3. for each vertex u taken in the topologically order
4. ___for each v neighbor
of u
5. ______Improve
(u,v)
הסבר :
מיון טופולוגי (שורה 1), איתחול הגרף (שורה 2) ואז מעבר
על הקודקודים לפי הסדר הטופולוגי שלהם (שורה 3) שבמהלכו,
הקלה על כל הקשתות השכנות (שורות 4-5).
