מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
נבנה גרף חדש כך.
ראשית, נקח את צמתי הגרף
, ונשכפל אותם 3 פעמים, בקבוצות
,
, ו
. לכל צומת
בקבוצה
, יש צומת
ב
, וצומת
ב
. התרשים
הבא מראה זאת.
שכפול הצמתים.
כעת נוסיף גם קשתות:
- כל קשת אדומה בין
ל
(בגרף המקורי) - נמתח אותה בגרף החדש בין
ב
לבין הצומת המתאים ל
ב
.
- כל קשת שחורה בין
ל
(בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל
ב
לבין הצומת המתאים ל
ב
.
התרשים הבא מראה זאת.
הוספת הקשתות.
בנוסף נמתח עוד שני סוגי קשתות:
- לכל צומת
ב
, נמתח קשת במחיר 1 בין
ב
לבין
ב
.
- לכל צומת
ב
, נמתח קשת במחיר 1 בין
ב
לבין
ב
.(לא נצייר קשתות אלו מטעמי נוחות.)
נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא
.
המשפט הבא מסביר את חשיבות הגרף החדש.
הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ
ל
ב
בגרף החדש, מורכב משני חלקים:
- מסלול זהה לחלוטין למסלול קביל מ
ל
בגרף המקורי
- מסלול בעלות 1 ל
ב![{\displaystyle \displaystyle C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f93c2f86128fa35ce9fc9541ea009814df31c36)
לכן, כל שנותר הוא להריץ את אלגוריתם Dijkstra.
קל לראות שהסיבוכיות הכוללת היא זו של אלגוריתם Dijkstra.