האלגוריתם:

1. הסר את הקשת $ab$ מהגרף
2. הרץ את אלגוריתם דייקסטרה מ-$s$
3. הרץ את אלגוריתם דייקסטרה מ-$b$
4. לכל צומת $v$ החזר $\min \{d(s,v), d(s,a) + w(ab) + d(b,v)\}$

נכונות:

מכיוון שאין מעגלים שליליים בגרף אז לכל צומת קיים מסלול פשוט קל ביותר. אם לצומת $v$ קיים מסלול קל ביותר שלא עובר בקשת $ab$ אז ערכו הוא $d(s,v)$.

אחרת המסלול הזה מורכב ממסלול קל ביותר מ-$s$ ל-$a$, הקשת $ab$ ומסלול קל ביותר מ-$b$ ל-$v$ ולכן ערכו הוא $d(s,a) + w(ab) + d(b,v)$.