---
title: "Tüm-Çiftler En Kısa Yollar (Johnson)"
subtitle: "Her düğüme süpernode'dan en kısa mesafeyi potansiyel atayıp kenarları w′ = w + h(u) − h(v) ile yeniden ağırlıklandırırsak (üçgen eşitsizliği bunu negatif-olmayan yapar, telescoping en kısa yolları korur), negatif ağırlıklı tüm-çiftler en kısa yolu V×Dijkstra hızında O(V² log V + V·E) çözeriz — Johnson yeni bir algoritma değil, Bellman-Ford ile Dijkstra'yı birleştiren akıllı bir indirgemedir; çizge ünitesinin son dersi"
---
::: {.callout-note title="Bölüm bilgisi"}
- **Ku'nun videosu:** [YouTube — Lecture 14: APSP and Johnson](https://www.youtube.com/watch?v=EmSmaW-ud6A) (~57 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 14: APSP and Johnson](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-14-apsp-and-johnson/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 21 (L14)
- **Hoca:** Jason Ku (tüm-çiftler en kısa yollar; çizge ünitesinin **SON dersi**)
- **Okuma süresi:** ~27 dk
> Bu, **çizge ünitesinin son dersidir**. Tek kaynak yerine *tüm* düğüm çiftleri arasında en kısa yol: **APSP (all-pairs shortest paths)**. Naif yol — her düğümden Bellman-Ford — $O(V^2 \cdot E)$ (yoğun çizgede $V^4$'e yakın). **Johnson**, negatif ağırlıklı bir çizgeyi akıllıca **yeniden ağırlıklandırıp** Dijkstra'yı $V$ kez çalıştırmayı mümkün kılar → $O(V^2 \log V + V \cdot E)$, neredeyse doğrusal.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d21}
Bu, çizge ünitesinin son dersi (Jason Ku). Tek kaynak yerine **tüm düğüm çiftleri** arasında en kısa yol: **APSP**. Naif yol — her düğümden Bellman-Ford — $O(V^2 \cdot E)$ (yoğun çizgede $V^4$'e yakın). **Johnson algoritması** ise, negatif ağırlıklı bir çizgeyi akıllıca **yeniden ağırlıklandırıp** Dijkstra'yı $V$ kez çalıştırmayı mümkün kılar → $O(V^2 \log V + V \cdot E)$, neredeyse doğrusal.
> *"make edge weights non-negative while preserving shortest paths."* — Ku, 14:35
Üç ana fikir:
1. **APSP çıktısı $\Theta(V^2)$** — her çift için bir sayı; doğrusaldan iyisini umut edemeyiz, ama V×Dijkstra'yı negatif ağırlıkta da istiyoruz.
2. **Potansiyel ile yeniden ağırlıklandırma** — her düğüme bir potansiyel $h(v)$ atayıp $w'(u,v) = w(u,v) + h(u) - h(v)$; bu **en kısa yolları korur** (telescoping).
3. **$h = \delta(s, v)$** — süpernode'dan en kısa mesafeyi potansiyel seçince, üçgen eşitsizliği kenarları **negatif-olmayan** yapar; sonra V×Dijkstra.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 21'in (L14) kavram haritası: kök = APSP ve Johnson (Ku) — çizge ünitesinin son dersi; tüm-çiftler en kısa yol. Beş dal — (1) APSP çıktısı Theta(V kare): her (u,v) çifti için bir sayı, doğrusaldan iyisi umulamaz; naif = V kez SSSP. (2) Kötü fikir: her kenara sabit ekle; az-kenarlı yola önyargı, en kısa yolu bozar. (3) Potansiyel dönüşümü w' = w + h(u) - h(v); telescoping ile iç potansiyeller iptal, en kısa yol korunur. (4) Üçgen eşitsizliği: negatif-olmama koşulu h(v) <= h(u) + w(u,v) tam olarak üçgen eşitsizliği; h = delta(s,v) seçimi w' >= 0 garanti eder. (5) Süpernode: s* her düğüme sıfır ağırlık, gelen kenarı yok; Bellman-Ford ile h, sonra V kez Dijkstra. Sonuç: Johnson yeni algoritma değil, Bellman-Ford ile Dijkstra'yı birleştiren akıllı tutkal; O(V kare log V artı V çarpı E)."
flowchart TD
A["Ders 21 (L14): APSP ve Johnson"] --> O["APSP çıktısı Theta(V kare)"]
O --> Oa["her (u,v) için bir sayı, doğrusaldan<br/>iyisi umulamaz; naif = V kez SSSP"]
A --> B["Kötü fikir: sabit ekle"]
B --> Ba["az-kenarlı yola önyargı,<br/>en kısa yolu BOZAR"]
A --> P["Potansiyel dönüşümü"]
P --> Pa["w-prime = w arti h(u) eksi h(v); telescoping<br/>iç potansiyeller iptal, en kısa yol KORUNUR"]
A --> T["Üçgen eşitsizliği = h = delta(s,v)"]
T --> Ta["h(v) en çok h(u) arti w(u,v), w-prime negatif-olmayan GARANTİ<br/>negatif-olmama = üçgen eşitsizliği"]
A --> S["Süpernode + Bellman-Ford"]
S --> Sa["s-yıldız her düğüme sıfır; gelen kenarı yok<br/>h = delta(s-yıldız), sonra V kez Dijkstra"]
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
class A root
class O,B,P,T,S branch
class Oa,Ba,Pa,Ta,Sa leaf
```
::: {.callout-tip title="Builder Notu — Johnson = Akıllı Tutkal"}
APSP'nin çıktısı zaten $\Theta(V^2)$ — her çift için bir mesafe. Naif yol her düğümden Bellman-Ford'dur ($O(V^2 \cdot E)$, yoğun çizgede $V^4$'e yakın). Johnson, negatif ağırlığı bir potansiyelle ortadan kaldırıp Dijkstra'yı $V$ kez çalıştırarak bunu $O(V^2 \log V + V \cdot E)$'ye indirir. Yeni bir kanıt yoktur — ağır iş Bellman-Ford (bir kez) ve Dijkstra (V kez) kara kutularındadır.
- **İleriye → mesafe matrisi:** APSP, yol ağında "tüm-çiftler süre matrisi" önbelleği (rota servisleri, lojistik optimizasyon) demektir.
- **İleriye → fark kısıtları:** potansiyel/yeniden-ağırlıklandırma, fark-kısıt sistemleri (difference constraints) ve doğrusal programlama dualitesiyle akrabadır.
- **İleriye → reduction ustalığı:** Johnson yeni bir algoritma değil — "imzalı problemi negatif-olmayan probleme indirgeyen tutkal"; OMSCS CS 6515 ana refleksi.
- **Geriye → Bellman-Ford + Dijkstra:** Johnson ikisini kara kutu olarak birleştirir.
Tek cümle: *Her düğüme süpernode'dan en kısa mesafeyi potansiyel atayıp kenarları $w' = w + h(u) - h(v)$ ile yeniden ağırlıklandırırsak (üçgen eşitsizliği bunu negatif-olmayan yapar, telescoping en kısa yolları korur), negatif ağırlıklı APSP'yi V×Dijkstra hızında $O(V^2 \log V + V \cdot E)$ çözeriz.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 21 (L14) APSP ve Johnson motoru (_engine.py D21 bölümü:
# add_supernode → reweight → johnson → brute_apsp → build_johnson_example) +
# D18 bellman_ford_classic (potansiyel h + İPTAL tanığı) + D19 dijkstra /
# ChangeablePQ (V×Dijkstra kara kutusu) + D16 relax_edge/INF + D11 path_weight +
# D18 build_bf_example (negatif çevrim İPTAL örneği) + Slate+Amber viz
# (_viz.py COL_* + apply_style). Bu hücre gizlidir (#| echo: false).
#
# Aşağıdaki TÜM figür hücreleri burada tanımlanan johnson / brute_apsp /
# build_johnson_example / add_supernode / reweight / bellman_ford_classic /
# dijkstra / ChangeablePQ / path_weight / build_bf_example / COL_*'ı IMPORT
# ETMEDEN kullanır.
#
# Notion'daki öğretim içeriği (görünür ```python blokları) bu motorun tarif
# seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir).
# ============================================================================
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, FancyBboxPatch, FancyArrowPatch, Arc
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir)
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
INF = float("inf")
# ---------------------------------------------------------------------------
# _engine.py D11 (L11) — path_weight + relax_edge (gevşetme)
# ---------------------------------------------------------------------------
def path_weight(weight, path):
"""Yolun ağırlığı (L11 §3): kenar ağırlıkları toplamı."""
return sum(weight[(path[i], path[i + 1])] for i in range(len(path) - 1))
def relax_edge(d, weight, u, v):
"""Kenar gevşetme (L11 §8): üçgen eşitsizliği ihlali varsa tahmini düşür."""
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
return True
return False
def _reachable_from(adj, start):
"""start kümesinden erişilebilen düğümler (negatif çevrim → −∞ yayma)."""
seen = set(start)
stack = list(start)
while stack:
u = stack.pop()
for v in adj[u]:
if v not in seen:
seen.add(v)
stack.append(v)
return seen
# ---------------------------------------------------------------------------
# _engine.py D18 (L12) — bellman_ford_classic — Ku; potansiyel h + İPTAL tanığı
# ---------------------------------------------------------------------------
def bellman_ford_classic(adj, weight, s):
"""Klasik Bellman-Ford (D18): V−1 tur kenar gevşetme; V. turda hâlâ
gevşeyen düğümler TANIK → erişilenlere −∞ yay. Johnson'da süpernode'dan
h = δ(s,·) potansiyelini hesaplar; −∞ → negatif çevrim → İPTAL."""
d = {v: INF for v in adj}
d[s] = 0
n = len(adj)
for _ in range(n - 1):
for u in adj:
if d[u] == INF:
continue
for v in adj[u]:
relax_edge(d, weight, u, v)
witnesses = set()
for u in adj:
if d[u] == INF:
continue
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
witnesses.add(v)
for v in _reachable_from(adj, witnesses):
d[v] = -INF
return d
def build_bf_example():
"""L12 §8 Notion örneği: a,b,c,d; çevrim b→c→d→b = (−4)+3+(−1) = −2
(negatif); a→b(−5) girişi. δ(a,·): a=0, b=c=d=−∞ (çevrimden erişilir).
Johnson burada None döner (negatif çevrim → İPTAL)."""
adj = {"a": ["b"], "b": ["c"], "c": ["d"], "d": ["b"]}
weight = {("a", "b"): -5, ("b", "c"): -4, ("c", "d"): 3, ("d", "b"): -1}
return adj, weight
# ---------------------------------------------------------------------------
# _engine.py D19 (L13) — Dijkstra — Ku; V×Dijkstra KARA KUTUSU (w′ ≥ 0)
# ChangeablePQ = binary min-heap + id→konum CROSS-LINK sözlüğü.
# ---------------------------------------------------------------------------
class ChangeablePQ:
"""Değiştirilebilir min-öncelik kuyruğu (L13 §5): binary min-heap +
id→konum sözlüğü (cross-link). build O(n), delete_min / decrease_key
O(log n). Öğe = (key, id); id benzersiz."""
def __init__(self, items=()):
self.a = [(k, i) for i, k in items] # (key, id)
self.pos = {item[1]: idx for idx, item in enumerate(self.a)}
for j in range(len(self.a) // 2 - 1, -1, -1): # heapify O(n)
self._sift_down(j)
def __len__(self):
return len(self.a)
def _swap(self, i, j):
self.a[i], self.a[j] = self.a[j], self.a[i]
self.pos[self.a[i][1]] = i
self.pos[self.a[j][1]] = j
def _sift_up(self, j):
while j > 0:
p = (j - 1) // 2
if self.a[p][0] <= self.a[j][0]:
break
self._swap(p, j)
j = p
def _sift_down(self, j):
n = len(self.a)
while True:
l, r, small = 2 * j + 1, 2 * j + 2, j
if l < n and self.a[l][0] < self.a[small][0]:
small = l
if r < n and self.a[r][0] < self.a[small][0]:
small = r
if small == j:
return
self._swap(j, small)
j = small
def delete_min(self):
"""En küçük anahtarlı id'yi çıkar. O(log n)."""
top_key, top_id = self.a[0]
last = self.a.pop()
del self.pos[top_id]
if self.a:
self.a[0] = last
self.pos[last[1]] = 0
self._sift_down(0)
return top_id, top_key
def decrease_key(self, vid, new_key):
"""id'li öğenin anahtarını DÜŞÜR (cross-link ile konumu O(1) bul)."""
j = self.pos[vid]
assert new_key <= self.a[j][0], "decrease_key yalnız düşürür"
self.a[j] = (new_key, vid)
self._sift_up(j)
def is_valid_heap(self):
for j in range(len(self.a)):
for c in (2 * j + 1, 2 * j + 2):
if c < len(self.a) and self.a[j][0] > self.a[c][0]:
return False
return all(self.a[self.pos[i]][1] == i for i in self.pos)
def dijkstra(adj, weight, s):
"""Dijkstra (L13 §6): en yakını çıkar, kenarlarını gevşet, decrease_key
ile güncelle. Ağırlıklar ≥ 0 ŞART (Johnson reweight bunu garanti eder)."""
d = {v: INF for v in adj}
d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
while len(Q):
u, _ = Q.delete_min()
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
Q.decrease_key(v, d[v])
return d
# ---------------------------------------------------------------------------
# _engine.py D21 (L14) — APSP ve Johnson — Ku; çizge ünitesi FİNALİ
# Johnson = indirgeme TUTKALI: süpernode'dan Bellman-Ford ile h(v)=δ(s,v)
# potansiyeli → w′=w+h(u)−h(v) reweight (telescoping en kısa yolları KORUR;
# üçgen eşitsizliği w′≥0 GARANTİ) → V×Dijkstra → geri-çevir. O(V²logV + V·E).
# ---------------------------------------------------------------------------
def add_supernode(adj, weight):
"""Süpernode (L14 §8): s* → her düğüme 0-ağırlık; GELEN kenarı yok
(yeni negatif çevrim yaratamaz)."""
s = ("super", "*")
adj2 = {s: list(adj.keys())}
for u in adj:
adj2[u] = list(adj[u])
w2 = dict(weight)
for v in adj:
w2[(s, v)] = 0
return adj2, w2, s
def reweight(adj, weight, h):
"""Potansiyel dönüşümü (L14 §6): w′(u,v) = w(u,v) + h(u) − h(v)."""
return {(u, v): weight[(u, v)] + h[u] - h[v] for u in adj for v in adj[u]}
def johnson(adj, weight):
"""Johnson APSP (L14 §9, Notion pseudocode birebir 5 adım).
Döndürür: {u: {v: δ(u,v)}} ya da None (negatif çevrim → iptal)."""
adj_s, w_s, s = add_supernode(adj, weight) # 1. süpernode
h = bellman_ford_classic(adj_s, w_s, s) # 2. h = δ(s,·)
if any(h[v] == -INF for v in adj):
return None # negatif çevrim
w_prime = reweight(adj, weight, h) # 3. w′ ≥ 0
delta = {}
for u in adj: # 4. V × Dijkstra
dp = dijkstra(adj, w_prime, u)
# 5. geri çevir: δ(u,v) = δ′(u,v) − h(u) + h(v)
delta[u] = {v: (dp[v] - h[u] + h[v]) if dp[v] != INF else INF
for v in adj}
return delta
def brute_apsp(adj, weight):
"""Bağımsız tanık: her düğümden bellman_ford_classic (V×BF — yavaş ama
Johnson'dan FARKLI yol; negatif çevrimsiz çizgede sonlu/INF birebir)."""
return {u: bellman_ford_classic(adj, weight, u) for u in adj}
def build_johnson_example():
"""L14 figürleri için deterministik negatif-kenarlı (çevrimsiz-negatif)
çizge: a→b(−2), b→c(3), a→c(4), c→d(−1), b→d(2).
h = δ(s*,·) = {a:0, b:−2, c:0, d:−1}; w′ = {ab:0, ac:4, bc:1, bd:1, cd:0}."""
adj = {"a": ["b", "c"], "b": ["c", "d"], "c": ["d"], "d": []}
weight = {("a", "b"): -2, ("b", "c"): 3, ("a", "c"): 4,
("c", "d"): -1, ("b", "d"): 2}
return adj, weight
```
## 1. APSP Problemi ve $\Theta(V^2)$ Çıktısı {#sec-1-apsp-problemi}
**APSP:** ağırlıklı bir çizgede *her* $(u, v)$ çifti için $\delta(u, v)$ döndür. (Negatif ağırlıklı çevrim varsa **iptal et** — bu derste yok varsayıyoruz, ama negatif kenarlar olabilir.)
> *"the shortest path distance from u to v for every u and v."* — Ku, 1:42
Çıktı boyutu **$\Theta(V^2)$** (her çift için bir sayı); dolayısıyla doğrusaldan (çizge boyutu) iyisini umut edemeyiz — en az karesel.
## 2. Naif Çözüm: V × SSSP {#sec-2-naif-cozum}
En basit yol: her düğümden bir SSSP algoritması. Seçeneğe göre:
- **V × Bellman-Ford:** $O(V^2 \cdot E)$ — genel ama yavaş (yoğun çizgede $V^4$'e yakın).
- **V × Dijkstra** (ağırlık $\geq 0$): $O(V^2 \log V + V \cdot E)$ — seyrek çizgede neredeyse doğrusal.
Seyrek çizgede fark: V×Bellman-Ford $\sim V^3$, V×Dijkstra $\sim V^2 \log V$ — tıpkı insertion sort ($n^2$) ile merge sort ($n \log n$) arasındaki ayrım. **Hedef:** negatif ağırlıklı çizgede de V×Dijkstra hızını elde etmek.
@fig-apsp-naive bu manzarayı tek panelde toplar: solda örnek çizge ve $4 \times 4$ $\delta$ matrisi (motorun Johnson çıktısı; çıktı boyutu $\Theta(V^2) = 16$ hücre), sağda iki naif yöntem — V×Bellman-Ford ($O(V^2 \cdot E)$, yavaş) ile V×Dijkstra (hızlı, ama "$w \geq 0$ şart" kilidiyle). Hedef, en altta: negatif ağırlıkta da V×Dijkstra hızını yakalamak → Johnson.
```{python}
#| label: fig-apsp-naive
#| fig-cap: "APSP problemi + naif çözümler (Ku L14 §1-2): çıktı Θ(V²); naif = V × SSSP. SOL ÜST: örnek çizge (build_johnson_example) sabit yerleşim; düğüm = daire, kenar = yönlü ok + ağırlık rozeti; negatif kenarlar a→b(−2), c→d(−1) amber vurgulu. SOL ALT: 4×4 δ matrisi (motor johnson çıktısı; satır=kaynak, sütun=hedef; +∞ erişilmez; köşegen 0) + sağında \"çıktı boyutu Θ(V²) = 16 hücre, doğrusaldan iyisi umulamaz\" rozeti. SAĞ: iki naif yöntem — (1) V × Bellman-Ford O(V²·E) slate \"yoğun graf ~V⁴ YAVAŞ\"; (2) V × Dijkstra O(V² log V + V·E) amber \"HIZLI\" ama kilit ikonu \"ağırlık ≥ 0 ŞART\". ALT NOT: hedef = negatif ağırlıkta da V × Dijkstra hızı → Johnson (make non-negative while preserving, Ku 14:35). Veri MOTORDAN: johnson == brute_apsp (V×BF bağımsız tanık BİREBİR); 4×4 = 16 hücre; δ[a]={a:0,b:−2,c:1,d:0}; δ[d]={a,b,c:+∞,d:0}."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-apsp-naive (L14 §1-2): örnek çizge + δ matrisi (Θ(V²)) + iki naif yöntem.
# Veri MOTORDAN (build_johnson_example / johnson / brute_apsp). networkx YOK.
_AN_POS = {"a": (0.0, 1.0), "b": (1.0, 1.6), "c": (1.0, 0.4), "d": (2.0, 1.0)}
_AN_EDGES = [
("a", "b", -2, True), ("b", "c", 3, False), ("a", "c", 4, False),
("c", "d", -1, True), ("b", "d", 2, False),
]
_AN_R = 0.20
_AN_NODES = ["a", "b", "c", "d"]
def _an_draw_graph(ax, ox, oy):
def P(v):
x, y = _AN_POS[v]
return (ox + x, oy + y)
for u, v, wt, neg in _AN_EDGES:
ux, uy = P(u)
vx, vy = P(v)
ecol = COL_ACCENT if neg else COL_PRIMARY
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=13,
color=ecol, linewidth=2.4 if neg else 1.9,
shrinkA=_AN_R * 86, shrinkB=_AN_R * 86, zorder=2))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
if (u, v) == ("a", "c"):
my -= 0.18
bg = COL_AMBER_100 if neg else COL_WHITE
ec = COL_ACCENT if neg else COL_SLATE_400
tcol = COL_AMBER_700 if neg else COL_TEXT
ax.add_patch(FancyBboxPatch(
(mx - 0.135, my - 0.115), 0.27, 0.23,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=bg, ec=ec, linewidth=1.6 if neg else 1.0, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center",
fontsize=8.5 if neg else 8, color=tcol, weight="bold", zorder=7)
for v in _AN_NODES:
px, py = P(v)
ax.add_patch(Circle((px, py), _AN_R, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=1.9, zorder=5))
ax.text(px, py, v, ha="center", va="center", fontsize=11,
color=COL_TEXT, weight="bold", zorder=6)
ax.text(ox + 1.0, oy - 0.10,
"negatif kenarlar: a→b (−2), c→d (−1)", ha="center", va="center",
fontsize=7.5, color=COL_AMBER_700, style="italic", zorder=6)
ax.text(ox + 1.0, oy + 2.05, "Örnek çizge (w: E → ℤ)", ha="center",
va="center", fontsize=10.5, color=COL_PRIMARY, weight="bold", zorder=6)
def _an_fmt(val):
return "+∞" if val == INF else str(val)
def _an_draw_matrix(ax, ox, oy, delta):
cw, ch = 0.62, 0.52
gx, gy = ox, oy
ax.text(gx - cw * 0.5, gy + ch * 0.5, "u\\v", ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, weight="bold", zorder=5)
for c, v in enumerate(_AN_NODES):
x = gx + c * cw + cw * 0.5
ax.text(x, gy + ch * 0.5, v, ha="center", va="center",
fontsize=10, color=COL_PRIMARY, weight="bold", zorder=5)
for r, u in enumerate(_AN_NODES):
y = gy - (r + 1) * ch
ax.text(gx - cw * 0.5, y + ch * 0.5, u, ha="center", va="center",
fontsize=10, color=COL_PRIMARY, weight="bold", zorder=5)
for c, v in enumerate(_AN_NODES):
x = gx + c * cw
val = delta[u][v]
is_diag = (u == v)
is_inf = (val == INF)
if is_diag:
fc, ec, tcol, lw = COL_BG, COL_PRIMARY, COL_SLATE_500, 1.5
elif is_inf:
fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_SLATE_400, 1.0
else:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 1.6
ax.add_patch(FancyBboxPatch(
(x, y), cw * 0.94, ch * 0.92, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=3))
ax.text(x + cw * 0.47, y + ch * 0.46, _an_fmt(val),
ha="center", va="center",
fontsize=9 if not is_inf else 8.5,
color=tcol, weight="bold", zorder=4)
ax.text(gx + 2 * cw, gy + ch * 1.45,
"δ(u, v) matrisi — APSP çıktısı", ha="center", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5)
bx = gx + 4 * cw + 0.28
bcy = (gy + (gy - 4 * ch)) * 0.5
bw, bh = 1.95, 1.05
ax.add_patch(FancyBboxPatch(
(bx, bcy - bh * 0.5), bw, bh, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=4))
ax.text(bx + bw * 0.5, bcy + 0.28, "çıktı boyutu", ha="center", va="center",
fontsize=8, color=COL_AMBER_700, zorder=5)
ax.text(bx + bw * 0.5, bcy + 0.04, "Θ(V²) = 16 hücre", ha="center",
va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=5)
ax.text(bx + bw * 0.5, bcy - 0.30, "doğrusaldan iyisi\numulamaz",
ha="center", va="center", fontsize=7.5, color=COL_AMBER_700,
style="italic", zorder=5)
def _an_draw_naive_box(ax, x, y, w, h, title, cost, sub, accent, lock=False,
lock_text=""):
fc = COL_AMBER_100 if accent else COL_BG
ec = COL_ACCENT if accent else COL_SLATE_400
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=fc, ec=ec, linewidth=2.4 if accent else 1.7, zorder=3))
tcol = COL_AMBER_700 if accent else COL_PRIMARY
ax.text(x + 0.22, y + h - 0.30, title, ha="left", va="center",
fontsize=11, color=tcol, weight="bold", zorder=5)
ccol = COL_AMBER_700 if accent else COL_SLATE_500
ax.text(x + w - 0.22, y + h - 0.30, cost, ha="right", va="center",
fontsize=10.5, color=ccol, weight="bold", family="monospace", zorder=5)
ax.text(x + 0.22, y + 0.62, sub, ha="left", va="center",
fontsize=8.4, color=COL_SLATE_500, zorder=5)
if accent:
ax.text(x + 0.22, y + 0.26, "✔ HIZLI", ha="left", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
else:
ax.text(x + 0.22, y + 0.26, "✘ YAVAŞ", ha="left", va="center",
fontsize=8.5, color=COL_SLATE_500, weight="bold", zorder=5)
if lock:
lx = x + w - 2.15
ly = y + 0.26
bw_, bh_ = 0.22, 0.15
cx_ = lx + bw_ * 0.5
body_top = ly - bh_ * 0.5
shackle = Arc((cx_, body_top + bh_ * 0.5), bw_ * 0.66, bw_ * 0.78,
theta1=0.0, theta2=180.0,
color=COL_AMBER_700, linewidth=2.0, zorder=6)
ax.add_patch(shackle)
ax.add_patch(FancyBboxPatch(
(lx, body_top), bw_, bh_,
boxstyle="round,pad=0.004,rounding_size=0.025",
fc=COL_AMBER_600, ec=COL_AMBER_700, linewidth=1.3, zorder=7))
ax.text(lx + bw_ + 0.13, ly, lock_text, ha="left", va="center",
fontsize=8.2, color=COL_AMBER_700, weight="bold", zorder=7)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_an_adj, _an_w = build_johnson_example()
_an_delta = johnson(_an_adj, _an_w)
assert _an_delta is not None, "negatif çevrim beklenmiyordu"
_an_cells = [(u, v) for u in _an_adj for v in _an_adj]
assert len(_an_cells) == 16, len(_an_cells) # Θ(V²) çıktı
_an_bf = brute_apsp(_an_adj, _an_w)
assert all(_an_delta[u][v] == _an_bf[u][v] for u in _an_adj for v in _an_adj)
assert _an_delta["a"] == {"a": 0, "b": -2, "c": 1, "d": 0}, _an_delta["a"]
assert _an_delta["d"] == {"a": INF, "b": INF, "c": INF, "d": 0}, _an_delta["d"]
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
_an_draw_graph(ax, ox=0.10, oy=4.55)
_an_draw_matrix(ax, ox=0.95, oy=3.55, delta=_an_delta)
_an_right_x = 5.95
_an_box_w, _an_box_h = 4.55, 1.65
_an_gap = 0.55
_an_top_y = 4.30
ax.text(_an_right_x + _an_box_w * 0.5, _an_top_y + _an_box_h + 0.40,
"Naif çözüm: her düğümden SSSP çalıştır (V kez)",
ha="center", va="center", fontsize=10, color=COL_TEXT,
weight="bold", zorder=5)
_an_draw_naive_box(
ax, _an_right_x, _an_top_y, _an_box_w, _an_box_h,
"V × Bellman-Ford", "O(V² · E)",
"her düğümden D18 SSSP · negatif kenarı KALDIRIR ama yoğun grafta ~V⁴",
accent=False)
_an_y2 = _an_top_y - (_an_box_h + _an_gap)
_an_draw_naive_box(
ax, _an_right_x, _an_y2, _an_box_w, _an_box_h,
"V × Dijkstra", "O(V² log V + V·E)",
"her düğümden D19 SSSP · çok daha hızlı, AMA bir kısıt var",
accent=True, lock=True, lock_text="ağırlık ≥ 0 ŞART")
_an_note_y = _an_y2 - 0.62
ax.text(_an_right_x, _an_note_y,
"Hedef: negatif ağırlıkta DA V × Dijkstra hızı → JOHNSON",
ha="left", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(_an_right_x, _an_note_y - 0.32,
"ağırlıkları, en kısa yolları KORUYARAK negatif-olmayana dönüştür "
"(potansiyel) (Ku 14:35)",
ha="left", va="center", fontsize=8.4, color=COL_SLATE_500,
style="italic", zorder=5)
fig.suptitle(
"APSP: tüm (u,v) çiftleri için δ — çıktı Θ(V²); naif = V × SSSP "
"(Dijkstra hızlı ama w ≥ 0 ister)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
ax.text(0.95, 1.02,
"All-Pairs Shortest Paths · çizge ünitesi finali · Ku L14 §1-2",
ha="left", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.35, 10.85)
ax.set_ylim(_an_note_y - 0.70, 5.75)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 3. Fikir: Yeniden Ağırlıklandırma {#sec-3-fikir-yeniden-agirliklandirma}
Anahtar fikir: kenar ağırlıklarını **negatif-olmayan** yapacak şekilde değiştir — ama **en kısa yolları koruyarak**.
> *"make edge weights non-negative while preserving shortest paths."* — Ku, 14:35
Başarırsak, yeni çizge $G'$ üzerinde V×Dijkstra çalıştırıp, mesafeleri orijinal $G$'ye geri çeviririz. (Mümkün değildir eğer $G$ negatif ağırlıklı çevrim içeriyorsa — o zaman en kısa yol basit değildir, oysa negatif-olmayan çizgede en kısa yollar basittir → çelişki.)
## 4. Kötü Fikir: Her Kenara Sabit Ekle {#sec-4-kotu-fikir-sabit}
Akla gelen ilk şey: en küçük (negatif) ağırlığın tersini her kenara ekle → hepsi negatif-olmayan. **Ama en kısa yolları bozar.**
> *"Makes weights non-negative, but does not preserve shortest paths."* — Ku, 23:45
Neden? Her kenara aynı sabit eklemek, **az kenarlı** yollara önyargı (bias) yaratır: 3-kenarlı bir yol $+3c$, 1-kenarlı yol $+c$ artar. Kenar sayısı farklı yollar farklı değişir → en kısa yol değişebilir.
@fig-constant-bias bunu birebir bir karşı-örnekle gösterir: solda orijinal çizge ($s \to t$ doğrudan = 3; $s \to m \to t$ = 2; en kısa = 2-kenarlı yol), sağda her kenara $+2$ eklenmiş hâli (doğrudan = 5; iki-kenarlı = 6; en kısa **değişti** → doğrudan kenar). Sebep: 2-kenarlı yol $+2c$ kayar, 1-kenarlı yol $+c$ kayar — farklı kayma sıralamayı bozar. Doğru dönüşüm (potansiyel) her yolu *aynı* sabitle kaydırmalıdır.
```{python}
#| label: fig-constant-bias
#| fig-cap: "KÖTÜ FİKİR (Ku L14 §4): her kenara sabit ekle — kenar sayısına bağlı kayma en kısa yolu DEĞİŞTİRİR. İki panel, aynı üçgen çizge (s, m, t; doğrudan s→t alt kenar). SOL — ORİJİNAL: s→t (1 kenar) = 3, s→m→t (2 kenar) = 2; KAZANAN iki-kenarlı yol amber (2 < 3). SAĞ — HER KENARA +2: s→t = 5, s→m→t = 6; KAZANAN DEĞİŞTİ → doğrudan kenar amber + \"✗ en kısa yol DEĞİŞTİ\" uyarı rozeti (2-kenarlı +2c=+4 ≠ 1-kenarlı +c=+2). ORTA kutu: k-kenarlı yol +k·c kayar; farklı kenar sayısı → farklı kayma → sıralama bozulur (Ku 23:45). ALT NOT: doğru dönüşüm her yolu AYNI sabitle kaydırmalı → potansiyel h: w′ = w + h(u) − h(v) telescoping; sağlama (motor) build_johnson_example reweight w′ = {ab:0, ac:4, bc:1, bd:1, cd:0} HEPSİ ≥ 0. Veri MOTORDAN (path_weight): orijinal 3 vs 2, +c sonrası 5 vs 6; kayma 1-kenarlı +2, 2-kenarlı +4; kazanan yer değiştirdi."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-constant-bias (L14 §4): 1-kenarlı vs 2-kenarlı yol → sabit-ekle bozar.
# Veri MOTORDAN (path_weight + build_johnson_example reweight). networkx YOK.
_CB_POS = {"s": (0.0, 0.55), "m": (1.0, 1.35), "t": (2.0, 0.55)}
_CB_R = 0.24
_CB_W_ORIG = {("s", "t"): 3, ("s", "m"): 1, ("m", "t"): 1}
_CB_C = 2
def _cb_draw_counterexample(ax, ox, oy, weight, win_path, badge=None,
badge_warn=False):
def P(v):
x, y = _CB_POS[v]
return (ox + x, oy + y)
win_edges = {(win_path[i], win_path[i + 1]) for i in range(len(win_path) - 1)}
win_nodes = set(win_path)
for (u, v), wt in weight.items():
ux, uy = P(u)
vx, vy = P(v)
on_win = (u, v) in win_edges
ecol = COL_ACCENT if on_win else COL_PRIMARY
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=13,
color=ecol, linewidth=2.6 if on_win else 1.7,
shrinkA=_CB_R * 64, shrinkB=_CB_R * 64, zorder=3 if on_win else 2))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
if (u, v) == ("s", "t"):
my -= 0.17
ax.add_patch(FancyBboxPatch(
(mx - 0.135, my - 0.115), 0.27, 0.23,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100 if on_win else COL_WHITE,
ec=COL_ACCENT if on_win else COL_SLATE_400,
linewidth=1.7 if on_win else 1.0, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center", fontsize=9,
color=COL_AMBER_700 if on_win else COL_TEXT,
weight="bold", zorder=7)
for v, (x, y) in _CB_POS.items():
on_win = v in win_nodes
if on_win:
fc, ec, tc, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.6
else:
fc, ec, tc, lw = COL_BG, COL_PRIMARY, COL_TEXT, 1.9
px, py = P(v)
ax.add_patch(Circle((px, py), _CB_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(px, py, v, ha="center", va="center", fontsize=12,
color=tc, weight="bold", zorder=6)
if v == "s":
ax.text(px - _CB_R - 0.06, py - 0.02, "kaynak", ha="right",
va="center", fontsize=7.5, color=COL_SLATE_500,
weight="bold", zorder=6)
elif v == "t":
ax.text(px + _CB_R + 0.06, py - 0.02, "hedef", ha="left",
va="center", fontsize=7.5, color=COL_SLATE_500,
weight="bold", zorder=6)
w_direct = path_weight(weight, ["s", "t"])
w_via = path_weight(weight, ["s", "m", "t"])
yb = oy - 0.30
direct_win = (("s", "t") in win_edges)
ax.text(ox + 1.0, yb, f"s→t (1 kenar): {w_direct}",
ha="center", va="center", fontsize=9.5,
color=COL_AMBER_700 if direct_win else COL_SLATE_500,
weight="bold" if direct_win else "normal", zorder=6)
ax.text(ox + 1.0, yb - 0.34, f"s→m→t (2 kenar): {w_via}",
ha="center", va="center", fontsize=9.5,
color=COL_AMBER_700 if not direct_win else COL_SLATE_500,
weight="bold" if not direct_win else "normal", zorder=6)
win_label = "doğrudan kenar" if direct_win else "iki kenarlı yol"
lo, hi = (w_direct, w_via) if direct_win else (w_via, w_direct)
ax.text(ox + 1.0, yb - 0.72, f"en kısa = {win_label} ({lo} < {hi})",
ha="center", va="center", fontsize=9,
color=COL_AMBER_700, style="italic", weight="bold", zorder=6)
if badge is not None:
bw, bh = 2.55, 0.46
bx = ox + 1.0 - bw * 0.5
by = oy + 1.95
bfc = COL_AMBER_100 if badge_warn else COL_BG
bec = COL_ACCENT if badge_warn else COL_PRIMARY
ax.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=bfc, ec=bec, linewidth=2.4 if badge_warn else 1.8, zorder=4))
ax.text(ox + 1.0, by + bh * 0.5, badge, ha="center", va="center",
fontsize=10, color=COL_AMBER_700 if badge_warn else COL_TEXT,
weight="bold", zorder=5)
def _cb_draw_warning_badge(ax, cx, cy):
w, h = 3.05, 0.82
ax.add_patch(FancyBboxPatch(
(cx - w * 0.5, cy - h * 0.5), w, h,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=6))
ax.text(cx, cy + 0.16, "✗ en kısa yol DEĞİŞTİ", ha="center", va="center",
fontsize=10, color=COL_AMBER_700, weight="bold", zorder=7)
ax.text(cx, cy - 0.17, "2-kenarlı +2c=+4 ≠ 1-kenarlı +c=+2",
ha="center", va="center", fontsize=8.5, color=COL_AMBER_700,
family="monospace", zorder=7)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_cb_w_orig = dict(_CB_W_ORIG)
_cb_c = _CB_C
_cb_w_shift = {e: wt + _cb_c for e, wt in _cb_w_orig.items()}
_cb_d_orig = path_weight(_cb_w_orig, ["s", "t"])
_cb_v_orig = path_weight(_cb_w_orig, ["s", "m", "t"])
assert _cb_d_orig == 3 and _cb_v_orig == 2 and _cb_v_orig < _cb_d_orig
_cb_d_shift = path_weight(_cb_w_shift, ["s", "t"])
_cb_v_shift = path_weight(_cb_w_shift, ["s", "m", "t"])
assert _cb_d_shift == 5 and _cb_v_shift == 6 and _cb_d_shift < _cb_v_shift
assert (_cb_d_shift - _cb_d_orig) == 1 * _cb_c
assert (_cb_v_shift - _cb_v_orig) == 2 * _cb_c
_cb_win_orig = ["s", "m", "t"] if _cb_v_orig < _cb_d_orig else ["s", "t"]
_cb_win_shift = ["s", "t"] if _cb_d_shift < _cb_v_shift else ["s", "m", "t"]
assert _cb_win_orig != _cb_win_shift
# Johnson DOĞRU dönüşüm sağlaması (alt not atfı): reweight w′ HEPSİ ≥ 0
_cb_ja, _cb_jw = build_johnson_example()
_cb_jas, _cb_jws, _cb_js = add_supernode(_cb_ja, _cb_jw)
_cb_jh = bellman_ford_classic(_cb_jas, _cb_jws, _cb_js)
_cb_jwp = reweight(_cb_ja, _cb_jw, _cb_jh)
assert {k: _cb_jh[k] for k in _cb_ja} == {"a": 0, "b": -2, "c": 0, "d": -1}
assert all(v >= 0 for v in _cb_jwp.values()), _cb_jwp
assert _cb_jwp == {("a", "b"): 0, ("a", "c"): 4, ("b", "c"): 1,
("b", "d"): 1, ("c", "d"): 0}, _cb_jwp
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
_cb_left_ox, _cb_left_oy = 0.0, 1.7
_cb_draw_counterexample(ax, _cb_left_ox, _cb_left_oy, _cb_w_orig, _cb_win_orig,
badge="ORİJİNAL ağırlıklar", badge_warn=False)
_cb_right_ox, _cb_right_oy = 5.0, 1.7
_cb_draw_counterexample(ax, _cb_right_ox, _cb_right_oy, _cb_w_shift, _cb_win_shift,
badge="HER KENARA +2 (kötü fikir)", badge_warn=True)
_cb_draw_warning_badge(ax, _cb_right_ox + 1.0, _cb_right_oy - 1.62)
_cb_arr_y = _cb_left_oy + 0.85
ax.add_patch(FancyArrowPatch(
(_cb_left_ox + 2.55, _cb_arr_y), (_cb_right_ox + 0.30, _cb_arr_y),
arrowstyle="-|>", mutation_scale=18, color=COL_AMBER_700,
linewidth=2.4, zorder=2, connectionstyle="arc3,rad=-0.18"))
ax.text((_cb_left_ox + 2.55 + _cb_right_ox + 0.30) * 0.5, _cb_arr_y + 0.62,
"her kenara\nsabit c = +2", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
_cb_box_x, _cb_box_y, _cb_box_w, _cb_box_h = 0.55, -2.05, 9.7, 1.18
ax.add_patch(FancyBboxPatch(
(_cb_box_x, _cb_box_y), _cb_box_w, _cb_box_h,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=3))
ax.text(_cb_box_x + 0.30, _cb_box_y + _cb_box_h - 0.30,
"Neden YANLIŞ — az kenarlı yola önyargı:", ha="left", va="center",
fontsize=10, color=COL_TEXT, weight="bold", zorder=5)
ax.text(_cb_box_x + 0.30, _cb_box_y + _cb_box_h - 0.66,
"k kenarlı bir yola toplam +k·c eklenir. Farklı kenar sayılı yollar "
"FARKLI kayar → en kısa yol sıralaması bozulur.",
ha="left", va="center", fontsize=9, color=COL_SLATE_500, zorder=5)
ax.text(_cb_box_x + 0.30, _cb_box_y + 0.24,
"Burada: 2-kenarlı yol +4, 1-kenarlı yol +2 kaydı; 2 < 3 iken 6 > 5 oldu "
"(Ku 23:45).", ha="left", va="center", fontsize=9,
color=COL_AMBER_700, style="italic", weight="bold", zorder=5)
_cb_note_y = _cb_box_y - 0.55
ax.text(_cb_box_x, _cb_note_y,
"Doğru dönüşüm her yolu AYNI sabitle kaydırmalı → potansiyel h: "
"w′(u,v) = w(u,v) + h(u) − h(v) (telescoping)",
ha="left", va="center", fontsize=9, color=COL_TEXT, weight="bold", zorder=5)
ax.text(_cb_box_x, _cb_note_y - 0.34,
"yol toplamına yalnız h(s)−h(t) eklenir — kenar sayısından BAĞIMSIZ; "
"üçgen eşitsizliği w′ ≥ 0 GARANTİ (Johnson §6).",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500,
style="italic", zorder=5)
ax.text(_cb_box_x, _cb_note_y - 0.66,
"Sağlama (motor): build_johnson_example reweight → "
"w′ = {ab:0, ac:4, bc:1, bd:1, cd:0} HEPSİ ≥ 0.",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700,
weight="bold", zorder=5)
fig.suptitle(
"KÖTÜ FİKİR: her kenara sabit ekle — kenar sayısına bağlı kayma en kısa "
"yolu DEĞİŞTİRİR",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(5.05, _cb_left_oy + 2.62,
"negatif kenarı yok etmek için sabit eklemek Dijkstra'yı kurtarmaz · Ku L14 §4",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.5, 10.7)
ax.set_ylim(_cb_note_y - 1.05, _cb_left_oy + 2.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 5. İyi Fikir: Potansiyel Dönüşümü {#sec-5-iyi-fikir-potansiyel}
Daha akıllı dönüşüm: bir düğüm $v$ için, **tüm çıkış kenarlarına $h$ ekle, tüm giriş kenarlarından $h$ çıkar**.
> *"If I add a number to all outgoing edges from a vertex, and I subtract that same number from the weights of all of the incoming edges... preserves shortest paths."* — Ku, 25:20
**Çalışılan Örnek — neden korur.** Bir yolu düşün: $v$'den **geçen** her yol, $v$'ye bir giriş kenarı ($-h$) ve bir çıkış kenarı ($+h$) kullanır → değişim iptal olur (net 0). $v$'ye **hiç değmeyen** yol etkilenmez. Yalnızca $v$'nin **başlangıç** (yol $+h$) veya **bitiş** (yol $-h$) olduğu durumda değişir — ama o zaman $v$'den çıkan/giren *tüm* yollar aynı miktarda değişir → en kısa yol yine en kısa kalır.
## 6. Potansiyel Fonksiyon ve Telescoping {#sec-6-potansiyel-telescoping}
Bunu her düğüme bağımsız uygula: bir **potansiyel fonksiyonu** $h: V \to \mathbb{Z}$. Yeni çizge $G'$: her kenar $w'(u, v) = w(u, v) + h(u) - h(v)$.
> *"define a potential function h that maps vertices to integers."* — Ku, 31:39
**Çalışılan Örnek — telescoping kanıtı.** $v_0 \to v_1 \to \ldots \to v_k$ yolunun yeni ağırlığı: $\sum [w(v_{i-1}, v_i) + h(v_{i-1}) - h(v_i)]$. Ara terimler **teleskoplanır** (her iç düğümün $+h$ ve $-h$'si iptal) → $w'(v_0 \to v_k) = w(v_0 \to v_k) + h(v_0) - h(v_k)$. Yani $v_0$'dan $v_k$'ya *her* yol aynı sabit ($h(v_0) - h(v_k)$) kadar değişir → en kısa yol değişmez.
@fig-potential-telescoping Johnson'ın imza fikrini gösterir: üstte $a \to b \to c$ yolu, her kenarın üstünde dönüşüm açılımı ($w'(a,b) = -2 + 0 - (-2) = 0$, $w'(b,c) = 3 + (-2) - 0 = 1$); ortada telescoping — iki açılım alt alta, iç terimler $-h(b)$ ve $+h(b)$ amber çift-çizgiyle iptal, geriye $w(a \to c) + h(a) - h(c)$ kalır; sağda geçiş düğümü sezgisi ($-h(v) + h(v) = 0$); altta sonuç — her yol aynı sabitle kayar, en kısa yol korunur, üstelik $h = \delta(s^*, v)$ seçimiyle $w' \geq 0$.
```{python}
#| label: fig-potential-telescoping
#| fig-cap: "Potansiyel dönüşümü + telescoping (Ku L14 §5-6 İMZA): w′(yol) = w(yol) + h(başlangıç) − h(bitiş). ÜST: yol a → b → c, her kenar üstünde dönüşüm açılımı w′(a,b)=w(a,b)+h(a)−h(b) (= −2+0−(−2) = 0) ve w′(b,c)=w(b,c)+h(b)−h(c) (= 3+(−2)−0 = 1). ORTA TELESCOPING: iki açılım alt alta; iç terimler −h(b) (satır 1) ve +h(b) (satır 2) AMBER çift-çizgiyle iptal (−h(b)+h(b)=0); kalan w(yol)+h(a)−h(c) kutuda (= 1+0−0 = 1). SAĞ mini panel: v'den GEÇEN yol için ara düğüm gelen kenar … −h(v), giden kenar +h(v) … → net 0 (Ku 25:20). ALT şerit SONUÇ: aynı (u,v) çifti arasındaki HER yol AYNI sabitle h(u)−h(v) kayar → SIRALAMA değişmez, en kısa yol KORUNUR; ayrıca h(v)=δ(s*,v) seçimiyle w′ ≥ 0 (üçgen eşitsizliği) → Dijkstra. Veri MOTORDAN: h = {a:0, b:−2, c:0, d:−1}; w′ = {ab:0, ac:4, bc:1, bd:1, cd:0} HEPSİ ≥ 0; path_weight(wp,[a,b,c]) == path_weight(w,[a,b,c]) + h[a] − h[c] (1 == 1+0−0); johnson == brute_apsp (telescoping en kısa yolu korur)."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-potential-telescoping (L14 §5-6 İMZA): potansiyel açılımı + telescoping.
# Veri MOTORDAN (build_johnson_example + add_supernode + bellman_ford_classic +
# reweight + path_weight + johnson + brute_apsp). networkx YOK.
def _pt_fmt(val):
if val < 0:
return f"−{abs(val)}"
return str(val)
def _pt_draw_path_node(ax, x, y, label, r=0.30, src=False):
fc = COL_AMBER_100 if src else COL_BG
ec = COL_ACCENT if src else COL_PRIMARY
tc = COL_AMBER_700 if src else COL_TEXT
ax.add_patch(Circle((x, y), r, facecolor=fc, edgecolor=ec,
linewidth=2.4 if src else 2.0, zorder=5))
ax.text(x, y, label, ha="center", va="center", fontsize=13,
color=tc, weight="bold", zorder=6)
def _pt_draw_path_edge(ax, x0, x1, y, r=0.30):
ax.add_patch(FancyArrowPatch(
(x0 + r, y), (x1 - r, y), arrowstyle="-|>", mutation_scale=16,
color=COL_PRIMARY, linewidth=2.2, zorder=3))
# ---- motor verisi + ASSERT (figür yalnız motor sayılarını çizer) ----
_pt_adj, _pt_w = build_johnson_example()
_pt_as, _pt_ws, _pt_s = add_supernode(_pt_adj, _pt_w)
_pt_h_full = bellman_ford_classic(_pt_as, _pt_ws, _pt_s)
_pt_h = {v: _pt_h_full[v] for v in _pt_adj} # süpernode'u at
assert _pt_h == {"a": 0, "b": -2, "c": 0, "d": -1}, _pt_h # potansiyel
_pt_wp = reweight(_pt_adj, _pt_w, _pt_h)
assert _pt_wp[("a", "b")] == 0 and _pt_wp[("a", "c")] == 4, _pt_wp
assert _pt_wp[("b", "c")] == 1 and _pt_wp[("b", "d")] == 1, _pt_wp
assert _pt_wp[("c", "d")] == 0, _pt_wp
assert all(val >= 0 for val in _pt_wp.values()), _pt_wp # w′ ≥ 0 GARANTİ
_pt_yol = ["a", "b", "c"]
_pt_lhs = path_weight(_pt_wp, _pt_yol)
_pt_rhs = path_weight(_pt_w, _pt_yol) + _pt_h["a"] - _pt_h["c"]
assert _pt_lhs == _pt_rhs, (_pt_lhs, _pt_rhs) # 1 == 1 + 0 − 0
assert _pt_lhs == 1 and path_weight(_pt_w, _pt_yol) == 1
assert johnson(_pt_adj, _pt_w) == brute_apsp(_pt_adj, _pt_w)
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
# ÜST: yol a → b → c + her kenar üstünde dönüşüm açılımı
_pt_px = {"a": 1.2, "b": 4.0, "c": 6.8}
_pt_py = 6.4
_pt_R = 0.30
_pt_draw_path_node(ax, _pt_px["a"], _pt_py, "a", _pt_R, src=True)
_pt_draw_path_node(ax, _pt_px["b"], _pt_py, "b", _pt_R)
_pt_draw_path_node(ax, _pt_px["c"], _pt_py, "c", _pt_R)
_pt_draw_path_edge(ax, _pt_px["a"], _pt_px["b"], _pt_py, _pt_R)
_pt_draw_path_edge(ax, _pt_px["b"], _pt_px["c"], _pt_py, _pt_R)
ax.text((_pt_px["a"] + _pt_px["c"]) * 0.5, _pt_py + 0.78,
"Yol a → b → c (potansiyel dönüşümü altında)", ha="center",
va="center", fontsize=11.5, color=COL_PRIMARY, weight="bold", zorder=6)
_pt_mab = (_pt_px["a"] + _pt_px["b"]) * 0.5
ax.text(_pt_mab, _pt_py + 0.40, r"$w'(a,b) = w(a,b) + h(a) - h(b)$",
ha="center", va="center", fontsize=10.5, color=COL_TEXT, zorder=6)
ax.text(_pt_mab, _pt_py - 0.46,
f"= {_pt_w[('a','b')]} + {_pt_fmt(_pt_h['a'])} − ({_pt_fmt(_pt_h['b'])}) "
f"= {_pt_wp[('a','b')]}",
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=6)
_pt_mbc = (_pt_px["b"] + _pt_px["c"]) * 0.5
ax.text(_pt_mbc, _pt_py + 0.40, r"$w'(b,c) = w(b,c) + h(b) - h(c)$",
ha="center", va="center", fontsize=10.5, color=COL_TEXT, zorder=6)
ax.text(_pt_mbc, _pt_py - 0.46,
f"= {_pt_w[('b','c')]} + ({_pt_fmt(_pt_h['b'])}) − {_pt_fmt(_pt_h['c'])} "
f"= {_pt_wp[('b','c')]}",
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=6)
# ORTA: TELESCOPING — iki satır, iç terimler iptal
_pt_tel_y0 = 4.55
_pt_line_gap = 0.62
_pt_lx0 = 0.55
_pt_tx0 = 2.55
ax.add_patch(FancyBboxPatch(
(0.30, _pt_tel_y0 - 2 * _pt_line_gap - 0.30), 8.55, 2 * _pt_line_gap + 0.95,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.4, zorder=1))
ax.text(_pt_lx0, _pt_tel_y0 + 0.62, "TELESCOPING (iç potansiyeller iptal olur)",
ha="left", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", zorder=4)
_pt_cx_w = _pt_tx0 + 0.55
_pt_cx_plus = _pt_tx0 + 2.05
_pt_cx_minus = _pt_tx0 + 3.65
_pt_y1 = _pt_tel_y0
ax.text(_pt_lx0, _pt_y1, r"$w'(a,b)\,=$", ha="left", va="center", fontsize=11,
color=COL_TEXT, zorder=4)
ax.text(_pt_cx_w, _pt_y1, r"$w(a,b)$", ha="center", va="center", fontsize=11,
color=COL_PRIMARY, weight="bold", zorder=4)
ax.text(_pt_cx_plus, _pt_y1, r"$+\,h(a)$", ha="center", va="center", fontsize=11,
color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(_pt_cx_minus, _pt_y1, r"$-\,h(b)$", ha="center", va="center", fontsize=11,
color=COL_SLATE_500, weight="bold", zorder=4)
_pt_y2 = _pt_tel_y0 - _pt_line_gap
ax.text(_pt_lx0, _pt_y2, r"$w'(b,c)\,=$", ha="left", va="center", fontsize=11,
color=COL_TEXT, zorder=4)
ax.text(_pt_cx_w, _pt_y2, r"$w(b,c)$", ha="center", va="center", fontsize=11,
color=COL_PRIMARY, weight="bold", zorder=4)
ax.text(_pt_cx_plus, _pt_y2, r"$+\,h(b)$", ha="center", va="center", fontsize=11,
color=COL_SLATE_500, weight="bold", zorder=4)
ax.text(_pt_cx_minus, _pt_y2, r"$-\,h(c)$", ha="center", va="center", fontsize=11,
color=COL_AMBER_700, weight="bold", zorder=4)
def _pt_strike(cx, cy, hw=0.52, hh=0.20):
ax.plot([cx - hw, cx + hw], [cy - hh, cy + hh],
color=COL_ACCENT, linewidth=2.6, zorder=7)
ax.plot([cx - hw, cx + hw], [cy + hh, cy - hh],
color=COL_ACCENT, linewidth=2.6, zorder=7)
_pt_strike(_pt_cx_minus, _pt_y1) # −h(b) (satır 1)
_pt_strike(_pt_cx_plus, _pt_y2) # +h(b) (satır 2)
ax.add_patch(FancyArrowPatch(
(_pt_cx_minus, _pt_y1 - 0.20), (_pt_cx_plus, _pt_y2 + 0.20),
arrowstyle="-", color=COL_ACCENT, linewidth=2.0,
linestyle=(0, (4, 2)), zorder=6, connectionstyle="arc3,rad=0.0"))
ax.text((_pt_cx_minus + _pt_cx_plus) * 0.5 + 0.55, (_pt_y1 + _pt_y2) * 0.5,
"−h(b) + h(b) = 0", ha="left", va="center", fontsize=8.5,
color=COL_AMBER_700, style="italic", weight="bold", zorder=8)
_pt_res_y = _pt_tel_y0 - 2 * _pt_line_gap - 0.02
ax.add_patch(FancyBboxPatch(
(_pt_lx0 - 0.10, _pt_res_y - 0.30), 6.30, 0.62,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=5))
ax.text(_pt_lx0 + 0.05, _pt_res_y,
r"$w'(\mathrm{yol}) \;=\; w(\mathrm{yol}) + h(a) - h(c)$",
ha="left", va="center", fontsize=12, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(_pt_lx0 + 4.55, _pt_res_y,
f"= {path_weight(_pt_w, _pt_yol)} + {_pt_fmt(_pt_h['a'])} − "
f"{_pt_fmt(_pt_h['c'])} = {path_weight(_pt_wp, _pt_yol)}",
ha="left", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", zorder=6)
# SAĞ mini panel: v'den GEÇEN yol → ara potansiyel −h(v)+h(v) = 0
_pt_rx = 9.35
ax.add_patch(FancyBboxPatch(
(_pt_rx - 0.30, 3.45), 2.55, 2.65,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE, ec=COL_PRIMARY, linewidth=1.6, zorder=2))
ax.text(_pt_rx + 0.97, 5.86, "GEÇİŞ DÜĞÜMÜ", ha="center", va="center",
fontsize=9.5, color=COL_PRIMARY, weight="bold", zorder=4)
ax.text(_pt_rx + 0.97, 5.56, "v'den geçen yol", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, style="italic", zorder=4)
_pt_vy = 4.75
_pt_ux, _pt_vx, _pt_wx = _pt_rx + 0.10, _pt_rx + 0.97, _pt_rx + 1.84
ax.add_patch(Circle((_pt_ux, _pt_vy), 0.16, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=1.6, zorder=5))
ax.add_patch(Circle((_pt_vx, _pt_vy), 0.20, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=2.2, zorder=5))
ax.add_patch(Circle((_pt_wx, _pt_vy), 0.16, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=1.6, zorder=5))
ax.text(_pt_ux, _pt_vy, "u", ha="center", va="center", fontsize=9,
color=COL_TEXT, weight="bold", zorder=6)
ax.text(_pt_vx, _pt_vy, "v", ha="center", va="center", fontsize=10,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(_pt_wx, _pt_vy, "w", ha="center", va="center", fontsize=9,
color=COL_TEXT, weight="bold", zorder=6)
ax.add_patch(FancyArrowPatch(
(_pt_ux + 0.16, _pt_vy), (_pt_vx - 0.20, _pt_vy), arrowstyle="-|>",
mutation_scale=11, color=COL_PRIMARY, linewidth=1.8, zorder=3))
ax.add_patch(FancyArrowPatch(
(_pt_vx + 0.20, _pt_vy), (_pt_wx - 0.16, _pt_vy), arrowstyle="-|>",
mutation_scale=11, color=COL_PRIMARY, linewidth=1.8, zorder=3))
ax.text((_pt_ux + _pt_vx) * 0.5, _pt_vy + 0.30, "… −h(v)", ha="center",
va="center", fontsize=8.5, color=COL_SLATE_500, weight="bold", zorder=6)
ax.text((_pt_vx + _pt_wx) * 0.5, _pt_vy + 0.30, "+h(v) …", ha="center",
va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(_pt_rx + 0.97, _pt_vy - 0.55, "−h(v) + h(v) = 0", ha="center",
va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(_pt_rx + 0.97, _pt_vy - 0.92, "ara düğüm net\ndeğişim YOK",
ha="center", va="center", fontsize=8, color=COL_SLATE_500,
style="italic", zorder=6)
ax.text(_pt_rx + 0.97, 3.66, "(Ku 25:20)", ha="center", va="center",
fontsize=7.5, color=COL_SLATE_400, style="italic", zorder=4)
# ALT şerit: SONUÇ
_pt_sonuc_y = 2.05
ax.add_patch(FancyBboxPatch(
(0.30, _pt_sonuc_y - 0.78), 11.55, 1.30,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=1))
ax.text(0.60, _pt_sonuc_y + 0.22,
"SONUÇ: aynı (u, v) çifti arasındaki HER yol AYNI sabitle "
"h(u) − h(v) kayar",
ha="left", va="center", fontsize=11, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(0.60, _pt_sonuc_y - 0.20,
"→ ağırlıklar kayar ama SIRALAMA değişmez · en kısa yol KORUNUR · "
"ayrıca h(v)=δ(s*,v) seçimiyle w′ ≥ 0 (üçgen eşitsizliği) → Dijkstra",
ha="left", va="center", fontsize=9, color=COL_TEXT, zorder=4)
ax.text(0.60, _pt_sonuc_y - 0.55,
"Motor teyidi: w′ tüm kenarlarda ≥ 0 · Johnson(δ) == brute_apsp(δ) "
"(telescoping en kısa yolu korur — birebir)",
ha="left", va="center", fontsize=8.5, color=COL_AMBER_700,
style="italic", weight="bold", zorder=4)
fig.suptitle(
"Potansiyel dönüşümü + telescoping: w′(yol) = w(yol) + h(başlangıç) − h(bitiş)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text((_pt_px["a"] + _pt_px["c"]) * 0.5, _pt_py + 1.18,
"Johnson'ın tutkalı — iç potansiyeller telescoping ile iptal, "
"en kısa yol korunur · Ku L14 §5-6",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.1, 12.1)
ax.set_ylim(1.05, 7.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 7. Negatif-Olmama Koşulu = Üçgen Eşitsizliği {#sec-7-negatif-olmama-ucgen}
Hangi $h$ kenarları negatif-olmayan yapar? $w'(u, v) = w(u, v) + h(u) - h(v) \geq 0$ koşulunu düzenle:
$$h(v) \leq h(u) + w(u, v)$$
> *"That looks like almost exactly the definition of the triangle inequality."* — Ku, 40:16
Bu, **üçgen eşitsizliğinin** ta kendisi! Demek ki $h(v) = \delta(s, v)$ (bir kaynaktan en kısa mesafe) seçersek — ve bu mesafeler sonluysa — koşul kendiliğinden sağlanır. Reweight sonrası tüm kenarlar negatif-olmayan olur.
@fig-triangle-nonneg bu denkliği üç bölgede gösterir: solda cebirsel türetme ($w'(u,v) \geq 0 \Leftrightarrow w(u,v) + h(u) - h(v) \geq 0 \Leftrightarrow h(v) \leq h(u) + w(u,v)$ = üçgen eşitsizliği), ortada üçgen şeması ($s^*$ tepe, $u$ ve $v$ alt; $h(v) \leq h(u) + w$), sağda 5-kenarlı reweight tablosu (her satırda $w / h(u) / h(v) / w'$; hepsi $\geq 0$). Altta: $h = \delta(s^*, \cdot)$ seçersek üçgen eşitsizliği otomatik sağlanır.
```{python}
#| label: fig-triangle-nonneg
#| fig-cap: "Negatif-olmama koşulu w′(u,v) ≥ 0 = üçgen eşitsizliği h(v) ≤ h(u) + w(u,v) (Ku L14 §7, 40:16 \"almost exactly the definition\"). SOL: cebir kutusu adım adım — w′(u,v) ≥ 0 İSTE ⇕ w(u,v)+h(u)−h(v) ≥ 0 ⇕ h(v) ≤ h(u)+w(u,v); son satır amber \"BU ÜÇGEN EŞİTSİZLİĞİ\". ORTA: üçgen şeması s* (süpernode/kaynak, tepe) → u (mesafe h(u)) + s* → v (mesafe h(v)) + kenar u→v (ağırlık w, amber kapanış); sonuç rozeti h(v) ≤ h(u) + w(u,v); \"s*'tan v'ye en kısa yol u üzerinden gitmekten kötü olamaz\". SAĞ: 5 kenar tablosu (a→b, a→c, b→c, b→d, c→d), her satırda w / h(u) / h(v) / w′ = w+h(u)−h(v) ve ✓ (hepsi ≥ 0); altta \"TÜM w′ ≥ 0 — negatif-olmama SAĞLANDI\". ALT NOT: h = δ(s*,·) en kısa mesafe SEÇERSEK üçgen eşitsizliği OTOMATİK → tüm w′ ≥ 0 GARANTİ; süpernode s* her düğüme erişir + gelen kenarı yok → yeni negatif çevrim yaratmaz. Veri MOTORDAN: h = {a:0, b:−2, c:0, d:−1}; w′ = {ab:0, ac:4, bc:1, bd:1, cd:0} HEPSİ ≥ 0; johnson == brute_apsp (V×BF bağımsız tanık BİREBİR)."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-triangle-nonneg (L14 §7): negatif-olmama = üçgen eşitsizliği.
# Veri MOTORDAN (build_johnson_example + add_supernode + bellman_ford_classic +
# reweight + johnson + brute_apsp). networkx YOK.
def _tn_draw_algebra(ax, x0, y0):
box_w, box_h = 4.1, 0.74
gap = 0.30
# mathtext: $...$ içinde Türkçe YASAK — yalnız sembol/formül
steps = [
(r"$w'(u,v) \geq 0$", "negatif-olmama İSTE"),
(r"$w(u,v) + h(u) - h(v) \geq 0$", r"$w' = w + h(u) - h(v)$ yerine koy"),
(r"$h(v) \leq h(u) + w(u,v)$", r"$h(v)$ yalnız bırak"),
]
for i, (formula, note) in enumerate(steps):
y = y0 - i * (box_h + gap)
ax.add_patch(FancyBboxPatch(
(x0, y), box_w, box_h, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.7, zorder=3))
ax.text(x0 + 0.22, y + box_h * 0.62, formula, ha="left", va="center",
fontsize=13, color=COL_TEXT, zorder=5)
ax.text(x0 + 0.22, y + box_h * 0.22, note, ha="left", va="center",
fontsize=7.8, color=COL_SLATE_500, style="italic", zorder=5)
if i < len(steps) - 1:
mx = x0 + box_w * 0.5
ax.text(mx, y - gap * 0.5, "⇕", ha="center", va="center",
fontsize=12, color=COL_AMBER_700, weight="bold", zorder=5)
yr = y0 - len(steps) * (box_h + gap)
ax.add_patch(FancyArrowPatch(
(x0 + box_w * 0.5, yr + box_h + gap), (x0 + box_w * 0.5, yr + box_h + 0.04),
arrowstyle="-|>", mutation_scale=15, color=COL_AMBER_700,
linewidth=2.2, zorder=2))
ax.add_patch(FancyBboxPatch(
(x0, yr), box_w, box_h + 0.10, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=3))
ax.text(x0 + box_w * 0.5, yr + (box_h + 0.10) * 0.66,
"BU ÜÇGEN EŞİTSİZLİĞİ", ha="center", va="center",
fontsize=12.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(x0 + box_w * 0.5, yr + (box_h + 0.10) * 0.24,
"(Ku 40:16 'almost exactly the definition')", ha="center",
va="center", fontsize=7.5, color=COL_AMBER_700, style="italic", zorder=5)
def _tn_draw_triangle(ax, cx, cy):
R = 0.30
Ps = (cx, cy + 1.35)
Pu = (cx - 1.45, cy - 0.95)
Pv = (cx + 1.45, cy - 0.95)
def edge(a, b, col, lw):
ax.add_patch(FancyArrowPatch(
a, b, arrowstyle="-|>", mutation_scale=14, color=col,
linewidth=lw, shrinkA=R * 78, shrinkB=R * 78,
connectionstyle="arc3,rad=0.0", zorder=2))
edge(Ps, Pu, COL_PRIMARY, 2.0)
edge(Ps, Pv, COL_PRIMARY, 2.0)
edge(Pu, Pv, COL_ACCENT, 2.6)
ax.text((Ps[0] + Pu[0]) * 0.5 - 0.30, (Ps[1] + Pu[1]) * 0.5 + 0.08,
r"$h(u)$", ha="center", va="center", fontsize=11,
color=COL_PRIMARY, weight="bold", zorder=6)
ax.text((Ps[0] + Pv[0]) * 0.5 + 0.30, (Ps[1] + Pv[1]) * 0.5 + 0.08,
r"$h(v)$", ha="center", va="center", fontsize=11,
color=COL_PRIMARY, weight="bold", zorder=6)
ax.text((Pu[0] + Pv[0]) * 0.5, Pu[1] - 0.30,
r"$w(u,v)$", ha="center", va="center", fontsize=11,
color=COL_AMBER_700, weight="bold", zorder=6)
for (px, py), lab, src in [(Ps, r"$s^{*}$", True), (Pu, r"$u$", False),
(Pv, r"$v$", False)]:
fc = COL_AMBER_100 if src else COL_BG
ec = COL_ACCENT if src else COL_PRIMARY
lw = 2.8 if src else 2.0
ax.add_patch(Circle((px, py), R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(px, py, lab, ha="center", va="center", fontsize=12.5,
color=COL_AMBER_700 if src else COL_TEXT, weight="bold", zorder=6)
ax.text(Ps[0], Ps[1] + R + 0.20, "süpernode (kaynak)", ha="center",
va="center", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6)
ax.add_patch(FancyBboxPatch(
(cx - 1.75, cy - 2.18), 3.5, 0.58,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=4))
ax.text(cx, cy - 1.89, r"$h(v) \;\leq\; h(u) + w(u,v)$",
ha="center", va="center", fontsize=12.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(cx, cy + 2.28,
"Üçgen: s*'tan v'ye en kısa yol,\nu üzerinden gitmekten kötü olamaz",
ha="center", va="center", fontsize=8, color=COL_SLATE_500,
style="italic", zorder=6)
def _tn_draw_table(ax, x0, y0, rows):
headers = ["kenar", "w", "h(u)", "h(v)", "w′ = w+h(u)−h(v)", "≥ 0 ?"]
col_w = [0.95, 0.62, 0.78, 0.78, 2.30, 0.78]
row_h = 0.66
x_edges = [x0]
for cw in col_w:
x_edges.append(x_edges[-1] + cw)
total_w = x_edges[-1] - x0
yh = y0
ax.add_patch(FancyBboxPatch(
(x0, yh), total_w, row_h, boxstyle="round,pad=0.01,rounding_size=0.04",
fc=COL_PRIMARY, ec=COL_PRIMARY, linewidth=1.5, zorder=3))
for c, head in enumerate(headers):
xc = (x_edges[c] + x_edges[c + 1]) * 0.5
ax.text(xc, yh + row_h * 0.5, head, ha="center", va="center",
fontsize=7.6, color=COL_WHITE, weight="bold", zorder=5)
for r, row in enumerate(rows):
y = y0 - (r + 1) * row_h
edge_lab, w, hu, hv, wp = row
cells = [edge_lab, str(w), str(hu), str(hv),
f"{w}+({hu})−({hv}) = {wp}", "✓"]
for c, txt in enumerate(cells):
xc = (x_edges[c] + x_edges[c + 1]) * 0.5
is_wp = (c >= 4)
fc = COL_AMBER_100 if is_wp else (COL_BG if r % 2 == 0 else COL_WHITE)
ec = COL_ACCENT if is_wp else COL_SLATE_400
ax.add_patch(FancyBboxPatch(
(x_edges[c] + 0.02, y + 0.02), col_w[c] - 0.04, row_h - 0.04,
boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=1.6 if is_wp else 0.9, zorder=2))
tcol = COL_AMBER_700 if is_wp else COL_TEXT
wt = "bold" if (c == 0 or is_wp) else "normal"
fs = 8.0 if c == 4 else (9.5 if c == 5 else 8.6)
ax.text(xc, y + row_h * 0.5, txt, ha="center", va="center",
fontsize=fs, color=tcol, weight=wt, zorder=5)
yb = y0 - (len(rows) + 1) * row_h - 0.10
ax.text(x0 + total_w * 0.5, yb,
"TÜM w′ ≥ 0 — negatif-olmama SAĞLANDI", ha="center",
va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=5)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_tn_adj, _tn_w = build_johnson_example()
_tn_as, _tn_ws, _tn_s = add_supernode(_tn_adj, _tn_w)
_tn_h = bellman_ford_classic(_tn_as, _tn_ws, _tn_s)
_tn_h_nodes = {v: _tn_h[v] for v in _tn_adj}
assert _tn_h_nodes == {"a": 0, "b": -2, "c": 0, "d": -1}, _tn_h_nodes
_tn_wp = reweight(_tn_adj, _tn_w, _tn_h)
_tn_wp_named = {u + v: _tn_wp[(u, v)] for u in _tn_adj for v in _tn_adj[u]}
assert _tn_wp_named == {"ab": 0, "ac": 4, "bc": 1, "bd": 1, "cd": 0}, _tn_wp_named
assert all(v >= 0 for v in _tn_wp.values()), _tn_wp # üçgen eşitsizliği
assert johnson(_tn_adj, _tn_w) == brute_apsp(_tn_adj, _tn_w)
_tn_edge_order = [("a", "b"), ("a", "c"), ("b", "c"), ("b", "d"), ("c", "d")]
_tn_rows = []
for (u, v) in _tn_edge_order:
_wuv = _tn_w[(u, v)]
_wp = _tn_wp[(u, v)]
assert _wp == _wuv + _tn_h[u] - _tn_h[v], (u, v, _wp)
assert _wp >= 0
_tn_rows.append((f"{u}→{v}", _wuv, _tn_h[u], _tn_h[v], _wp))
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
_tn_alg_x = 0.0
_tn_alg_top = 4.55
_tn_draw_algebra(ax, _tn_alg_x, _tn_alg_top)
_tn_draw_triangle(ax, 6.55, 2.95)
_tn_draw_table(ax, 9.05, 4.95, _tn_rows)
_tn_note_x = _tn_alg_x + 0.05
_tn_note_y = -0.95
ax.text(_tn_note_x, _tn_note_y,
"h = δ(s*, ·) en kısa mesafeleri SEÇERSEK, üçgen eşitsizliği OTOMATİK "
"sağlanır → tüm w′ ≥ 0 GARANTİ.",
ha="left", va="center", fontsize=9.2, color=COL_TEXT, weight="bold", zorder=5)
ax.text(_tn_note_x, _tn_note_y - 0.40,
"Süpernode s* her düğüme erişir + gelen kenarı yok → yeni negatif "
"çevrim yaratmaz; potansiyel dönüşümü en kısa yolları KORUR.",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, zorder=5)
ax.text(_tn_note_x, _tn_note_y - 0.78,
"Motor: johnson(adj, w) == brute_apsp(adj, w) (V×Bellman-Ford bağımsız "
"tanık — BİREBİR, sıfır uyuşmazlık).",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700,
style="italic", weight="bold", zorder=5)
fig.suptitle(
"Negatif-olmama koşulu w′(u,v) ≥ 0 = üçgen eşitsizliği h(v) ≤ h(u) + w(u,v)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(5.9, _tn_alg_top + 1.18,
"Johnson reweight (L14 §7): w′ = w + h(u) − h(v), h = δ(s*, ·) · Ku L14 — çizge ünitesi FİNALİ",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.4, 14.4)
ax.set_ylim(_tn_note_y - 1.25, _tn_alg_top + 1.35)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 8. Süpernode ile Potansiyeli Hesapla {#sec-8-supernode-potansiyel}
Sorun: tüm düğümlere erişebilen bir kaynak olmayabilir (çizge bağlı olmayabilir). Çözüm: **süpernode**.
> *"Add new vertex s with 0-weight edge to every vertex."* — Ku, 42:00
Yeni süpernode $s$'ten her düğüme 0-ağırlıklı kenar ekle ($G_s$). $s$'ten Bellman-Ford ile $\delta(s, v)$ hesapla (negatif ağırlık olabileceğinden Dijkstra değil). İki durum: $\delta(s, v) = $ eksi sonsuz ise **negatif çevrim** vardır ($s$'in gelen kenarı yok → çevrim $s$'ten geçemez → orijinal $G$'de) → **iptal et**. Aksi halde tüm $\delta(s, v)$ sonlu → $h(v) = \delta(s, v)$ geçerli potansiyel.
@fig-supernode-h bu adımı gösterir: solda örnek çizge + üstte süpernode $s^*$, ondan her düğüme 0-ağırlıklı kesikli kenarlar, "$s^*$'e gelen kenar yok → yeni çevrim yaratmaz" rozeti, her düğümün altında Bellman-Ford'la hesaplanan $h(v)$ ($a{:}0$, $b{:}{-2}$, $c{:}0$, $d{:}{-1}$); sağda İPTAL durumu — D18'in negatif-çevrimli örneği ($b \to c \to d \to b = -2$), `johnson()` `None` döner ($\delta = $ eksi sonsuz tespit).
```{python}
#| label: fig-supernode-h
#| fig-cap: "Johnson §8 (Ku L14, 42:00): süpernode s* + Bellman-Ford → potansiyel h(v) = δ(s*, v) → reweight w′ ≥ 0. SOL: örnek çizge (build_johnson_example) + ÜSTTE süpernode s* (büyük amber); s*'den her düğüme 0-ağırlıklı KESİKLİ kenar (\"0\" rozetli); \"s*'e GELEN kenar YOK → yeni çevrim yaratmaz\" amber rozeti; her düğüm altında h = δ(s*, v) rozeti (a:0, b:−2, c:0, d:−1); orijinal negatif kenarlar a→b(−2), c→d(−1) amber; \"h Bellman-Ford ile — negatif kenar var → Dijkstra OLMAZ\" notu. SAĞ mini panel — İPTAL durumu: D18 örnek çizgesi (çevrim b→c→d→b = −2); s* eklenip Bellman-Ford koşunca çevrimden erişilen b,c,d → δ = −∞ → johnson() = None → \"NEGATİF ÇEVRİM → İPTAL\" kutusu. ALT NOT: Ku 42:00 \"add new vertex with 0-weight edges\"; s*'e gelen kenar yok → çevrim yaratmaz; h sonsuz değilse w′ = w + h(u) − h(v) ≥ 0 GARANTİ (üçgen eşitsizliği) → V × Dijkstra mümkün. Veri MOTORDAN: h = {a:0, b:−2, c:0, d:−1}; w′ = {ab:0, ac:4, bc:1, bd:1, cd:0} HEPSİ ≥ 0; johnson == brute_apsp; johnson(build_bf_example()) is None (İPTAL); çevrim b→c→d→b ağırlığı = −2."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-supernode-h (L14 §8 İMZA): süpernode + Bellman-Ford → h → İPTAL.
# Veri MOTORDAN (build_johnson_example + add_supernode + bellman_ford_classic +
# reweight + johnson + brute_apsp + build_bf_example). networkx YOK.
_SH_POS = {"a": (0.0, 1.0), "b": (1.3, 1.85), "c": (1.3, 0.15), "d": (2.6, 1.0)}
_SH_S_POS = (1.3, 3.15)
_SH_H_OFFSET = {"a": (-0.05, -0.58), "b": (-0.78, 0.0),
"c": (0.0, -0.58), "d": (0.78, 0.0)}
_SH_J_EDGES = [
("a", "b", -2, True), ("b", "c", 3, False), ("a", "c", 4, False),
("c", "d", -1, True), ("b", "d", 2, False),
]
_SH_R = 0.22
_SH_RS = 0.34
def _sh_draw_johnson_graph(ax, h):
sx, sy = _SH_S_POS
for v, (vx, vy) in _SH_POS.items():
ax.add_patch(FancyArrowPatch(
(sx, sy), (vx, vy), arrowstyle="-|>", mutation_scale=11,
color=COL_SLATE_400, linewidth=1.4, linestyle=(0, (4, 3)),
shrinkA=_SH_RS * 70, shrinkB=_SH_R * 78, zorder=1))
mx, my = sx + (vx - sx) * 0.40, sy + (vy - sy) * 0.40
ax.add_patch(Circle((mx, my), 0.115, facecolor=COL_WHITE,
edgecolor=COL_SLATE_400, linewidth=1.0, zorder=4))
ax.text(mx, my, "0", ha="center", va="center", fontsize=7.5,
color=COL_SLATE_500, weight="bold", zorder=5)
for u, v, wt, neg in _SH_J_EDGES:
ux, uy = _SH_POS[u]
vx, vy = _SH_POS[v]
ecol = COL_ACCENT if neg else COL_PRIMARY
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=13,
color=ecol, linewidth=2.4 if neg else 1.9,
shrinkA=_SH_R * 78, shrinkB=_SH_R * 78, zorder=2))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
if (u, v) == ("a", "c"):
mx, my = mx - 0.06, my - 0.06
elif (u, v) == ("b", "d"):
mx, my = mx + 0.06, my + 0.06
tcol = COL_AMBER_700 if neg else COL_TEXT
ax.add_patch(FancyBboxPatch(
(mx - 0.135, my - 0.115), 0.27, 0.23,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100 if neg else COL_WHITE,
ec=COL_ACCENT if neg else COL_SLATE_400,
linewidth=1.6 if neg else 1.0, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center", fontsize=8.5,
color=tcol, weight="bold", zorder=7)
ax.add_patch(Circle((sx, sy), _SH_RS, facecolor=COL_AMBER_300,
edgecolor=COL_AMBER_700, linewidth=2.8, zorder=5))
ax.text(sx, sy, "s*", ha="center", va="center", fontsize=13,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(sx, sy + _SH_RS + 0.18, "süpernode", ha="center", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6)
bx, by = sx - 2.30, sy + 0.10
ax.add_patch(FancyBboxPatch(
(bx, by - 0.40), 2.05, 0.80, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=4))
ax.text(bx + 1.025, by + 0.13, "s*'e GELEN kenar YOK", ha="center",
va="center", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(bx + 1.025, by - 0.16, "→ yeni çevrim yaratmaz", ha="center",
va="center", fontsize=7.5, color=COL_AMBER_700, style="italic", zorder=5)
ax.add_patch(FancyArrowPatch(
(bx + 2.05, by), (sx - _SH_RS - 0.04, sy + 0.02),
arrowstyle="-|>", mutation_scale=10, color=COL_ACCENT,
linewidth=1.3, zorder=4, connectionstyle="arc3,rad=-0.18"))
for v, (x, y) in _SH_POS.items():
ax.add_patch(Circle((x, y), _SH_R, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=1.9, zorder=5))
ax.text(x, y, v, ha="center", va="center", fontsize=11,
color=COL_TEXT, weight="bold", zorder=6)
odx, ody = _SH_H_OFFSET[v]
hx, hy = x + odx, y + ody
ax.add_patch(FancyBboxPatch(
(hx - 0.42, hy - 0.155), 0.84, 0.31,
boxstyle="round,pad=0.01,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.6, zorder=5))
hstr = f"h={h[v]}".replace("-", "−")
ax.text(hx, hy, hstr, ha="center", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(1.3, -0.78,
"h(v) = δ(s*, v) — Bellman-Ford ile (negatif kenar var → Dijkstra OLMAZ)",
ha="center", va="center", fontsize=8.2, color=COL_SLATE_500,
style="italic", zorder=6)
ax.text(1.3, 3.85, "Süpernode s* ekle → Bellman-Ford → h(v)",
ha="center", va="center", fontsize=11, color=COL_PRIMARY,
weight="bold", zorder=6)
def _sh_draw_cancel_panel(ax, ox, oy):
pos = {"a": (0.0, 1.0), "b": (0.9, 1.0), "c": (1.8, 1.5), "d": (1.8, 0.5)}
edges = [("a", "b", -5, False), ("b", "c", -4, True),
("c", "d", 3, True), ("d", "b", -1, True)]
r = 0.18
def P(v):
px, py = pos[v]
return (ox + px, oy + py)
ax.add_patch(FancyBboxPatch(
(ox - 0.55, oy - 1.15), 3.25, 3.30,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.6, zorder=1))
for u, v, wt, cyc in edges:
ux, uy = P(u)
vx, vy = P(v)
ecol = COL_ACCENT if cyc else COL_PRIMARY
cstyle = "arc3,rad=-0.30" if (u, v) == ("d", "b") else "arc3,rad=0.0"
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=10,
color=ecol, linewidth=2.0 if cyc else 1.5,
shrinkA=r * 78, shrinkB=r * 78, connectionstyle=cstyle, zorder=3))
if (u, v) == ("d", "b"):
mx, my = (ux + vx) * 0.5 - 0.34, (uy + vy) * 0.5
else:
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
tcol = COL_AMBER_700 if cyc else COL_TEXT
ax.add_patch(FancyBboxPatch(
(mx - 0.115, my - 0.10), 0.23, 0.20,
boxstyle="round,pad=0.01,rounding_size=0.04",
fc=COL_AMBER_100 if cyc else COL_WHITE,
ec=COL_ACCENT if cyc else COL_SLATE_400,
linewidth=1.3 if cyc else 0.9, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center", fontsize=7,
color=tcol, weight="bold", zorder=7)
neg_nodes = {"b", "c", "d"}
for v, (x, y) in pos.items():
is_neg = (v in neg_nodes)
px, py = P(v)
fc = COL_AMBER_100 if is_neg else COL_BG
ec = COL_ACCENT if is_neg else COL_PRIMARY
tc = COL_AMBER_700 if is_neg else COL_TEXT
ax.add_patch(Circle((px, py), r, facecolor=fc, edgecolor=ec,
linewidth=2.2 if is_neg else 1.6, zorder=5))
ax.text(px, py, v, ha="center", va="center", fontsize=9,
color=tc, weight="bold", zorder=6)
ax.text(ox + 1.0, oy + 2.0, "D18 örneği — çevrim b→c→d→b = −2",
ha="center", va="center", fontsize=8, color=COL_AMBER_700,
style="italic", weight="bold", zorder=6)
ax.text(ox + 1.0, oy - 0.05, "çevrimden erişilen b, c, d → δ = −∞",
ha="center", va="center", fontsize=7.5, color=COL_AMBER_700,
style="italic", zorder=6)
cbx, cby = ox - 0.40, oy - 1.02
ax.add_patch(FancyBboxPatch(
(cbx, cby), 2.95, 0.62, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=4))
ax.text(cbx + 1.475, cby + 0.41, "NEGATİF ÇEVRİM → İPTAL",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(cbx + 1.475, cby + 0.15, "johnson() = None (δ = −∞ tespit)",
ha="center", va="center", fontsize=7.5, color=COL_AMBER_700,
family="monospace", zorder=5)
ax.text(ox + 1.0, oy + 2.42, "İPTAL durumu", ha="center", va="center",
fontsize=10, color=COL_PRIMARY, weight="bold", zorder=6)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_sh_adj, _sh_w = build_johnson_example()
_sh_as, _sh_ws, _sh_s = add_supernode(_sh_adj, _sh_w)
_sh_h = bellman_ford_classic(_sh_as, _sh_ws, _sh_s)
_sh_h_nodes = {v: _sh_h[v] for v in _sh_adj}
assert _sh_h_nodes == {"a": 0, "b": -2, "c": 0, "d": -1}, _sh_h_nodes
_sh_wp = reweight(_sh_adj, _sh_w, _sh_h)
assert _sh_wp == {("a", "b"): 0, ("a", "c"): 4, ("b", "c"): 1,
("b", "d"): 1, ("c", "d"): 0}, _sh_wp
assert all(wp >= 0 for wp in _sh_wp.values()), _sh_wp # HEPSİ ≥ 0
assert johnson(_sh_adj, _sh_w) == brute_apsp(_sh_adj, _sh_w)
assert johnson(*build_bf_example()) is None # İPTAL
assert path_weight(build_bf_example()[1], ["b", "c", "d", "b"]) == -2
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
_sh_draw_johnson_graph(ax, _sh_h_nodes)
_sh_draw_cancel_panel(ax, ox=4.25, oy=0.40)
ax.text(0.0, -1.30,
"Ku 42:00 — \"add new vertex with 0-weight edges\": s*'e gelen kenar "
"yok → çevrim yaratmaz; h sonsuz değilse",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold", zorder=6)
ax.text(0.0, -1.62,
"sonraki adım w′(u,v) = w(u,v) + h(u) − h(v) ≥ 0 GARANTİ (üçgen "
"eşitsizliği) → V × Dijkstra mümkün olur.",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, zorder=6)
ax.text(0.0, -1.94,
"Motor tanığı: h = {a:0, b:−2, c:0, d:−1} · w′ = {ab:0, ac:4, bc:1, "
"bd:1, cd:0} HEPSİ ≥ 0 · johnson == brute_apsp.",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700,
style="italic", weight="bold", zorder=6)
fig.suptitle(
"Johnson §8: süpernode s* + Bellman-Ford → potansiyel h(v) = δ(s*, v) "
"→ reweight w′ ≥ 0",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.set_xlim(-1.6, 7.6)
ax.set_ylim(-2.15, 4.15)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 9. Johnson Algoritması ve Çalışma Süresi {#sec-9-johnson-calisma-suresi}
Johnson, bir **indirgeme** algoritmasıdır: imzalı (signed) APSP → negatif-olmayan APSP.
> *"It's really a reduction problem or a reduction algorithm."* — Ku, 47:08
```python
def johnson(graph):
# 1. Supernode s ekle: s'ten her dugume 0-agirlikli kenar
Gs = add_supernode(graph)
# 2. Bellman-Ford ile h(v) = delta(s, v)
h = bellman_ford(Gs, source=s) # O(V*E)
if any(h[v] == float('-inf') for v in graph):
return "NEGATIF CEVRIM" # iptal
# 3. Yeniden agirliklandir: w'(u,v) = w(u,v) + h(u) - h(v) >= 0
G_prime = reweight(graph, h) # O(E)
# 4. Her dugumden Dijkstra (G' negatif-olmayan)
delta_prime = {u: dijkstra(G_prime, u) for u in graph} # V * Dijkstra
# 5. G mesafelerini geri cevir: delta(u,v) = delta'(u,v) - h(u) + h(v)
return recover_original_distances(delta_prime, h) # O(V*(V+E))
```
**Çalışma süresi.** (1) $O(V+E)$, (2) Bellman-Ford $O(V \cdot E)$, (3) $O(E)$, (4) V×Dijkstra **$O(V^2 \log V + V \cdot E)$**, (5) $O(V \cdot (V+E))$. Baskın terim (4) → **$O(V^2 \log V + V \cdot E)$**.
> *"Johnson's is really just glue to transform a graph in a clever way."* — Ku, 56:24
Yeni bir tümevarım/kanıt yok; ağır iş Bellman-Ford (bir kez) + Dijkstra (V kez) kara kutularında. Johnson yalnızca "akıllı tutkal". Negatif ağırlıklı APSP'yi, V×Bellman-Ford'un $V^3$'ünden çok daha hızlı, seyrek çizgede neredeyse doğrusal çözer.
@fig-johnson-pipeline beş adımı dikey bir akışta toplar: (1) süpernode ekle $O(V+E)$, (2) Bellman-Ford $O(V \cdot E)$ — Ders 18 kara kutusu, eksi sonsuz çıkarsa İPTAL, (3) reweight $O(E)$, (4) V×Dijkstra $O(V^2 \log V + V \cdot E)$ — Ders 19 kara kutusu, BASKIN terim, (5) geri çevir $O(V(V+E))$; toplam $O(V^2 \log V + V \cdot E)$. Sağda örnek çizge ($w \to w'$ rozetleriyle) ve "Johnson = yeni algoritma değil, akıllı tutkal/indirgeme" yan notu.
```{python}
#| label: fig-johnson-pipeline
#| fig-cap: "Johnson APSP boru hattı (Ku L14 §9 İMZA): süpernode + Bellman-Ford potansiyeli + V×Dijkstra → O(V² log V + V·E). 5 adım dikey akış: (1) SÜPERNODE EKLE — s* → her düğüme 0 ağırlık, GELEN kenarı yok, O(V+E); (2) BELLMAN-FORD — h = δ(s*,·) potansiyeli (Ders 18 KARA KUTU), −∞ çıkarsa NEGATİF ÇEVRİM → İPTAL, O(V·E); (3) REWEIGHT — w′ = w + h(u) − h(v) ≥ 0 (üçgen garanti, en kısa yolları KORUR), O(E); (4) V × DIJKSTRA — her düğümden Dijkstra (Ders 19 KARA KUTU, w′ ≥ 0 geçerli), BASKIN terim, O(V²logV + V·E); (5) GERİ ÇEVİR — δ(u,v) = δ′(u,v) − h(u) + h(v), O(V(V+E)). TOPLAM O(V²logV + V·E). Sağ panel: örnek çizge, kenar rozeti w → w′ (a→b −2→0, a→c 4→4, b→c 3→1, b→d 2→1, c→d −1→0), düğüm potansiyeli h = {a:0, b:−2, c:0, d:−1}. Yan not: Johnson = YENİ algoritma DEĞİL, akıllı TUTKAL/indirgeme; iki büyük kara kutuyu (Ders 18 + Ders 19) birleştirir; çizge ünitesinin KAPANIŞ dersi (Ku 47:08 + 56:24 \"just glue\"). Veri MOTORDAN: h ve w′ EXACT; johnson == brute_apsp (V×BF BAĞIMSIZ tanık); δ(a,d) = 0 = path_weight(w,[a,b,d])."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-johnson-pipeline (L14 §9 İMZA): 5 adım dikey akış + örnek çizge.
# Veri MOTORDAN (build_johnson_example + add_supernode + bellman_ford_classic +
# reweight + johnson + brute_apsp). networkx YOK. V×BF bağımsız tanık.
_JP_POS = {"a": (0.0, 1.0), "b": (1.3, 1.9), "c": (1.3, 0.1), "d": (2.6, 1.0)}
_JP_EDGES = [
("a", "b", -2, 0), ("a", "c", 4, 4), ("b", "c", 3, 1),
("b", "d", 2, 1), ("c", "d", -1, 0),
]
_JP_R = 0.20
def _jp_draw_example_graph(ax, ox, oy, h):
def P(v):
x, y = _JP_POS[v]
return (ox + x, oy + y)
for u, v, wt, wp in _JP_EDGES:
ux, uy = P(u)
vx, vy = P(v)
neg = (wt < 0)
ecol = COL_ACCENT if neg else COL_PRIMARY
cstyle = "arc3,rad=0.16" if (u, v) == ("a", "c") else "arc3,rad=0.0"
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=12,
color=ecol, linewidth=2.2 if neg else 1.8,
shrinkA=_JP_R * 78, shrinkB=_JP_R * 78,
connectionstyle=cstyle, zorder=2))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
if (u, v) == ("a", "c"):
my -= 0.22
ax.add_patch(FancyBboxPatch(
(mx - 0.30, my - 0.135), 0.60, 0.27,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100 if neg else COL_WHITE,
ec=COL_ACCENT if neg else COL_SLATE_400,
linewidth=1.5 if neg else 1.0, zorder=6))
ax.text(mx, my, f"{wt} → {wp}", ha="center", va="center", fontsize=7.5,
color=COL_AMBER_700 if neg else COL_TEXT, weight="bold", zorder=7)
_h_off = {"a": (-0.46, 0.0), "b": (0.0, 0.46), "c": (0.0, -0.46),
"d": (0.46, 0.0)}
for v, (x, y) in _JP_POS.items():
px, py = P(v)
ax.add_patch(Circle((px, py), _JP_R, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=1.8, zorder=5))
ax.text(px, py, v, ha="center", va="center", fontsize=10,
color=COL_TEXT, weight="bold", zorder=6)
dx, dy = _h_off[v]
bxc, byc = px + dx, py + dy
ax.add_patch(FancyBboxPatch(
(bxc - 0.27, byc - 0.12), 0.54, 0.24,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.4, zorder=6))
ax.text(bxc, byc, f"h={h[v]}", ha="center", va="center",
fontsize=7.5, color=COL_AMBER_700, weight="bold", zorder=7)
ax.text(ox + 1.3, oy + 3.00, "Örnek çizge · kenar rozeti = w → w′",
ha="center", va="center", fontsize=8.2, color=COL_PRIMARY,
weight="bold", zorder=6)
ax.text(ox + 1.3, oy + 2.70, "h = δ(s*, ·) potansiyeli → her w′ ≥ 0",
ha="center", va="center", fontsize=7.3, color=COL_AMBER_700,
style="italic", zorder=6)
def _jp_draw_blackbox_badge(ax, ox, oy, title, sub):
w, h = 1.9, 0.78
ax.add_patch(FancyBboxPatch(
(ox, oy - h * 0.5), w, h, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=4))
ax.text(ox + w * 0.5, oy + 0.15, title, ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(ox + w * 0.5, oy - 0.16, sub, ha="center", va="center",
fontsize=7, color=COL_AMBER_700, style="italic", zorder=5)
def _jp_draw_step_box(ax, x, y, w, h, num, title, body, badge, accent=False):
fc = COL_AMBER_100 if accent else COL_BG
ec = COL_ACCENT if accent else COL_PRIMARY
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=fc, ec=ec, linewidth=2.4 if accent else 1.8, zorder=3))
ncx, ncy = x + 0.42, y + h * 0.5
ax.add_patch(Circle((ncx, ncy), 0.27, facecolor=COL_ACCENT,
edgecolor=COL_AMBER_700, linewidth=1.8, zorder=5))
ax.text(ncx, ncy, str(num), ha="center", va="center", fontsize=13,
color=COL_WHITE, weight="bold", zorder=6)
bw, bh = 2.32, 0.40
bx = x + w - bw - 0.18
bcy = y + h - 0.32
ax.add_patch(FancyBboxPatch(
(bx, bcy - bh * 0.5), bw, bh, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_WHITE, ec=COL_PRIMARY, linewidth=1.6, zorder=5))
ax.text(bx + bw * 0.5, bcy, badge, ha="center", va="center",
fontsize=8.8, color=COL_PRIMARY, weight="bold",
family="monospace", zorder=6)
tx = x + 0.86
ax.text(tx, y + h - 0.32, title, ha="left", va="center",
fontsize=10.2, color=COL_TEXT, weight="bold", zorder=5)
ax.text(tx, y + 0.30, body, ha="left", va="center",
fontsize=8.0, color=COL_SLATE_500, zorder=5)
# ---- motor verisi + V×BF bağımsız tanık (figür yalnız bunu çizer) ----
_jp_adj, _jp_w = build_johnson_example()
_jp_as, _jp_ws, _jp_s = add_supernode(_jp_adj, _jp_w)
_jp_h_full = bellman_ford_classic(_jp_as, _jp_ws, _jp_s)
_jp_h = {v: _jp_h_full[v] for v in _jp_adj}
assert _jp_h == {"a": 0, "b": -2, "c": 0, "d": -1}, _jp_h # POTANSİYEL EXACT
_jp_wp = reweight(_jp_adj, _jp_w, _jp_h)
assert _jp_wp == {("a", "b"): 0, ("a", "c"): 4, ("b", "c"): 1,
("b", "d"): 1, ("c", "d"): 0}, _jp_wp
assert all(v >= 0 for v in _jp_wp.values()), _jp_wp # HEPSİ ≥ 0
_jp_J = johnson(_jp_adj, _jp_w)
_jp_B = brute_apsp(_jp_adj, _jp_w)
assert _jp_J == _jp_B, (_jp_J, _jp_B) # V×BF tanık
assert _jp_J["a"]["d"] == 0 == path_weight(_jp_w, ["a", "b", "d"])
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
_jp_bx0 = 0.0
_jp_box_w, _jp_box_h = 6.6, 0.98
_jp_v_gap = 0.46
_jp_top_y = 5.2
_jp_steps = [
(1, "SÜPERNODE EKLE — s*",
"s* → her düğüme 0 ağırlık · GELEN kenarı yok (yeni çevrim yok)",
"O(V+E)", False),
(2, "BELLMAN-FORD",
"h = δ(s*, ·) potansiyel; −∞ çıkarsa NEGATİF ÇEVRİM → İPTAL",
"O(V·E)", True),
(3, "REWEIGHT",
"w′ = w + h(u) − h(v) ≥ 0 (üçgen garanti) · en kısa yolları KORUR",
"O(E)", False),
(4, "V × DIJKSTRA",
"her düğümden Dijkstra (w′ ≥ 0 geçerli) · BASKIN terim",
"O(V²logV + V·E)", True),
(5, "GERİ ÇEVİR",
"δ(u,v) = δ′(u,v) − h(u) + h(v) · potansiyeli geri al → gerçek δ",
"O(V(V+E))", False),
]
for _idx, (_num, _title, _body, _badge, _accent) in enumerate(_jp_steps):
_y = _jp_top_y - _idx * (_jp_box_h + _jp_v_gap)
_jp_draw_step_box(ax, _jp_bx0, _y, _jp_box_w, _jp_box_h, _num, _title,
_body, _badge, accent=_accent)
_jp_arrow_x = _jp_bx0 + 0.42
for _idx in range(len(_jp_steps) - 1):
_y_bot = _jp_top_y - _idx * (_jp_box_h + _jp_v_gap)
_y_next_top = _jp_top_y - (_idx + 1) * (_jp_box_h + _jp_v_gap) + _jp_box_h
ax.add_patch(FancyArrowPatch(
(_jp_arrow_x, _y_bot), (_jp_arrow_x, _y_next_top),
arrowstyle="-|>", mutation_scale=15, color=COL_AMBER_700,
linewidth=2.2, zorder=2))
_jp_tot_y = _jp_top_y - len(_jp_steps) * (_jp_box_h + _jp_v_gap)
ax.add_patch(FancyArrowPatch(
(_jp_arrow_x, _jp_tot_y + _jp_box_h + _jp_v_gap), (_jp_arrow_x, _jp_tot_y + 0.50),
arrowstyle="-|>", mutation_scale=15, color=COL_AMBER_700,
linewidth=2.2, zorder=2))
ax.add_patch(FancyBboxPatch(
(_jp_bx0, _jp_tot_y), _jp_box_w, 0.62, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=3))
ax.text(_jp_bx0 + 0.30, _jp_tot_y + 0.31, "TOPLAM", ha="left", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(_jp_bx0 + _jp_box_w - 0.30, _jp_tot_y + 0.31, "O(V²logV + V·E)", ha="right",
va="center", fontsize=12.5, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=5)
_jp_right_x = _jp_bx0 + _jp_box_w + 0.55
_jp_y2 = _jp_top_y - 1 * (_jp_box_h + _jp_v_gap) + _jp_box_h * 0.5
_jp_draw_blackbox_badge(ax, _jp_right_x, _jp_y2, "Ders 18 · KARA KUTU",
"Bellman-Ford")
ax.add_patch(FancyArrowPatch(
(_jp_right_x + 1.9, _jp_y2 - 0.30), (_jp_right_x + 2.55, _jp_y2 - 0.78),
arrowstyle="-|>", mutation_scale=13, color=COL_AMBER_700,
linewidth=2.0, zorder=4, connectionstyle="arc3,rad=-0.2"))
ax.text(_jp_right_x + 2.62, _jp_y2 - 0.96, "−∞ → İPTAL", ha="left", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(_jp_right_x + 2.62, _jp_y2 - 1.24, "(negatif çevrim)", ha="left",
va="center", fontsize=6.8, color=COL_SLATE_500, style="italic", zorder=5)
_jp_y4 = _jp_top_y - 3 * (_jp_box_h + _jp_v_gap) + _jp_box_h * 0.5
_jp_draw_blackbox_badge(ax, _jp_right_x, _jp_y4, "Ders 19 · KARA KUTU", "Dijkstra")
ax.text(_jp_right_x + 0.95, _jp_y4 - 0.50, "↑ BASKIN", ha="center", va="center",
fontsize=7.5, color=COL_AMBER_700, weight="bold", zorder=5)
_jp_graph_ox = _jp_right_x + 1.40
_jp_graph_oy = _jp_tot_y - 0.30
_jp_draw_example_graph(ax, _jp_graph_ox, _jp_graph_oy, _jp_h)
_jp_note_x = _jp_bx0
_jp_note_y = _jp_tot_y - 0.60
ax.text(_jp_note_x, _jp_note_y,
"Yan not: Johnson = YENİ algoritma DEĞİL — akıllı",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold", zorder=5)
ax.text(_jp_note_x, _jp_note_y - 0.32,
"TUTKAL/indirgeme. İki büyük KARA KUTUyu birleştirir:",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold", zorder=5)
ax.text(_jp_note_x, _jp_note_y - 0.64,
"Ders 18 Bellman-Ford (potansiyel) + Ders 19 Dijkstra (V×).",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, zorder=5)
ax.text(_jp_note_x, _jp_note_y - 0.96,
"Çizge ünitesinin KAPANIŞ dersi (Ku 47:08 + 56:24 \"just glue\").",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, zorder=5)
ax.text(_jp_note_x, _jp_note_y - 1.30,
"Motor tanığı: johnson(G) == brute_apsp(G) (V×BF, BAĞIMSIZ "
"mekanizma) — örnek + 60 rastgele ± çizgede BİREBİR.",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700,
style="italic", weight="bold", zorder=5)
fig.suptitle(
"Johnson APSP: süpernode + Bellman-Ford potansiyeli + V×Dijkstra → "
"O(V² log V + V·E)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(_jp_bx0 + _jp_box_w * 0.5, _jp_top_y + _jp_box_h + 0.26,
"negatif kenarlı APSP — iki kara kutuyu birleştiren akıllı indirgeme · "
"Ku L14 §9 (çizge ünitesi finali)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.4, _jp_right_x + 4.4)
ax.set_ylim(_jp_note_y - 1.62, _jp_top_y + _jp_box_h + 0.62)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d21}
1. **APSP**: tüm çift $\delta(u, v)$; çıktı **$\Theta(V^2)$**; negatif çevrim → iptal.
2. **Naif**: V×Bellman-Ford $O(V^2 \cdot E)$ / V×Dijkstra $O(V^2 \log V + V \cdot E)$.
3. **Yeniden ağırlıklandırma**: kenarları negatif-olmayan yap ama en kısa yolları koru → $G'$'de V×Dijkstra.
4. **Kötü fikir**: sabit ekle → az-kenarlı yollara bias, bozar.
5. **Potansiyel $h$**: $w' = w + h(u) - h(v)$; telescoping ile en kısa yol korunur.
6. **$h(v) = \delta(s, v)$**: negatif-olmama koşulu = üçgen eşitsizliği.
7. **Süpernode + Bellman-Ford**: $h$'yi hesapla, negatif çevrimi yakala; sonra V×Dijkstra → **$O(V^2 \log V + V \cdot E)$**.
::: {.callout-important title="Tek Bir Cümle"}
Johnson, süpernode'dan Bellman-Ford ile bulduğu $\delta(s,v)$'yi potansiyel yapıp kenarları $w' = w + h(u) - h(v)$ ile negatif-olmayana çevirir (üçgen eşitsizliği garanti eder, telescoping en kısa yolları korur), sonra V×Dijkstra çağırarak imzalı APSP'yi $O(V^2 \log V + V \cdot E)$'de çözer.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d21}
::: {.callout-note collapse="true" title="Soru 1: \"Her kenara aynı sabit ekle\" neden en kısa yolları bozar, ama potansiyel dönüşümü neden bozmaz?"}
**Cevap:**
Her kenara aynı $c$ eklemek, bir yolun ağırlığını (kenar sayısı)×$c$ kadar artırır — yani farklı kenar sayılı yollar farklı değişir, az-kenarlı yola önyargı doğar; eskiden en kısa olan çok-kenarlı yol artık en kısa olmayabilir. Potansiyel dönüşümünde $w' = w + h(u) - h(v)$; bir yol boyunca ara düğümlerin $+h(u)$ ve $-h(v)$ terimleri **teleskoplanır**, yalnızca $h(v_0) - h(v_k)$ kalır. Yani aynı $(v_0, v_k)$ çifti arasındaki *her* yol aynı sabit kadar değişir — göreli sıralama korunur, en kısa yol yine en kısa kalır.
:::
::: {.callout-note collapse="true" title="Soru 2: Potansiyeli neden h(v) = δ(s, v) seçiyoruz? Bu neyi garanti eder?"}
**Cevap:**
Reweight sonrası kenarların negatif-olmaması için $w(u, v) + h(u) - h(v) \geq 0$, yani **$h(v) \leq h(u) + w(u, v)$** gerekir — bu tam olarak üçgen eşitsizliğidir. En kısa yol mesafeleri $\delta(s, \cdot)$ üçgen eşitsizliğini **her zaman** sağlar ($\delta(s, v) \leq \delta(s, u) + w(u, v)$). Dolayısıyla $h(v) = \delta(s, v)$ seçilirse, tüm yeni kenar ağırlıkları otomatik olarak negatif-olmayan olur — başka bir koşul aramaya gerek kalmaz.
:::
::: {.callout-note collapse="true" title="Soru 3: Süpernode neden gerekli, ve neden onu eklemek yeni bir negatif çevrim yaratmaz?"}
**Cevap:**
$h(v) = \delta(s, v)$'yi hesaplamak için *tüm* düğümlere sonlu mesafede ulaşan bir kaynak gerekir; ama orijinal çizge bağlı olmayabilir, hiçbir düğüm hepsine ulaşamayabilir (ulaşılamayan için $\delta = $ artı sonsuz, işe yaramaz). Süpernode $s$, her düğüme 0-ağırlıklı kenarla bağlanır → her düğüme sonlu ($\leq 0$) mesafe. Yeni negatif çevrim yaratmaz çünkü $s$'in **hiç gelen kenarı yoktur** — hiçbir çevrim $s$'ten geçemez. Dolayısıyla Bellman-Ford bir eksi sonsuz bulursa, o çevrim zaten orijinal $G$'de vardı → güvenle iptal edilir.
:::
::: {.callout-note collapse="true" title="Soru 4: Johnson neden \"yeni bir algoritma değil, tutkal\" olarak tanımlanıyor?"}
**Cevap:**
Johnson kendi başına yeni bir tümevarım/kanıt veya çekirdek hesaplama içermez; ağır işi zaten bildiğimiz iki kara kutu yapar: **Bellman-Ford** (potansiyeli bulmak için bir kez) ve **Dijkstra** (negatif-olmayan $G'$ üzerinde V kez). Johnson'ın katkısı, imzalı (negatif ağırlıklı) problemi, Dijkstra'nın çalışabileceği negatif-olmayan bir probleme **indirgeyen** akıllı yeniden-ağırlıklandırmadır. Yani bir *reduction*: zor bağlamı, hızlı çözebildiğimiz kolay bağlama çeviren tutkal.
:::
## Egzersizler {#sec-egzersizler-d21}
**Egzersiz 1.** Küçük bir negatif-kenarlı (çevrimsiz) çizgede süpernode ekle, Bellman-Ford ile $h(v) = \delta(s, v)$ hesapla, kenarları $w'$ ile yeniden ağırlıklandır; tüm $w' \geq 0$ olduğunu doğrula.
**Egzersiz 2.** Telescoping kanıtını bir yol üzerinde adım adım yaz: ara terimlerin iptal olup $w(v_0 \to v_k) + h(v_0) - h(v_k)$ kaldığını göster.
**Egzersiz 3.** "Her kenara sabit ekle" fikrinin bir karşı-örneğini kur: iki düğüm arasında farklı kenar sayılı iki yolla, sabit eklemenin en kısayı değiştirdiğini göster.
**Egzersiz 4.** Johnson'ı Python'da yaz (Bellman-Ford + reweight + V×Dijkstra); çalışma süresinin $O(V^2 \log V + V \cdot E)$ olduğunu argümanla göster.
**Egzersiz 5.** Süpernode'un gelen kenarı olmamasının neden kritik olduğunu, gelen kenarı olsaydı hangi yanlış sonucun doğabileceğini açıkla.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d21}
::: {.callout-warning title="Sonraki: Ders 23 (L15) — Dinamik Programlama 1 (Erik Demaine)"}
**Ders 23 (L15): Dinamik Programlama — 1** (Erik Demaine). Araya **Ders 22 (Quiz 2 Gözden Geçirme)** girer; çizge ünitesinin son dersi olan bu Johnson dersini ve önceki ağırlıklı en kısa yol derslerini quizden önce gözden geçirme fırsatıdır.
Yeni bir üniteye geçiyoruz: artık size hazır bir algoritma sunmak yerine, **kendi algoritmanızı tasarlamayı** öğreteceğiz — **dinamik programlama (DP)**. En kısa yolların "optimal alt yapı" ve "örtüşen alt problemler" sezgileri, DP'nin temelini oluşturur.
**Ders 23 Öncesi Yapılacak:**
- Bu dersin egzersizlerini, özellikle Egzersiz 1 (reweight) ve 2 (telescoping) çöz.
- Johnson'ın 5 adımını ve her adımın süresini ezberden anlat.
- Ana cümleyi tekrar oku: *"Süpernode'dan δ(s,v)'yi potansiyel yap, reweight et, V×Dijkstra çalıştır."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d21}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **APSP** | Tüm çift $\delta(u,v)$; çıktı $\Theta(V^2)$; negatif çevrim → iptal | Böl. 1 |
| **Naif çözüm** | V×Bellman-Ford $O(V^2 \cdot E)$ / V×Dijkstra $O(V^2 \log V + V \cdot E)$ | Böl. 2 |
| **Yeniden ağırlıklandırma** | Kenarları $\geq 0$ yap, en kısa yolları koru | Böl. 3 |
| **Sabit ekleme (kötü)** | Az-kenarlı yola bias → bozar | Böl. 4 |
| **Potansiyel $h$** | $w' = w + h(u) - h(v)$; telescoping korur | Böl. 5-6 |
| **$h = \delta(s,v)$** | Negatif-olmama = üçgen eşitsizliği | Böl. 7 |
| **Süpernode** | $s \to$ her düğüm 0-ağırlık; Bellman-Ford; eksi sonsuz → iptal | Böl. 8 |
| **Johnson süresi** | $O(V^2 \log V + V \cdot E)$ (V×Dijkstra baskın) | Böl. 9 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d21}
::: {.callout-tip title="6 köprü"}
Bu ders, APSP çıktısının zorunlu $\Theta(V^2)$ alt sınırından başlayıp Johnson'ın akıllı indirgemesiyle negatif ağırlıklı tüm-çiftler en kısa yolu neredeyse doğrusala indirir — köprülerin özeti:
1. **APSP** → yol ağı mesafe matrisi (rota servisi önbelleği), lojistik, ağ gecikme matrisi.
2. **Potansiyel / yeniden ağırlıklandırma** → fark-kısıt sistemleri (difference constraints), doğrusal programlama dualitesi.
3. **Üçgen eşitsizliği = negatif-olmama** → metrik gömme, geçerli sezgisel (admissible heuristic) tasarımı.
4. **Süpernode** → çok-kaynak/çok-hedef indirgemesi (akış, kümeleme).
5. **Johnson = reduction** → "zor bağlamı kolay kara kutuya çevir"; OMSCS CS 6515 indirgeme refleksi.
6. **Negatif çevrim tespiti (tek Bellman-Ford)** → erken durma ile büyük iş tasarrufu; arbitraj/tutarsızlık kontrolü.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
Johnson, negatif ağırlıklı tüm-çiftler en kısa yolu, V×Bellman-Ford'un yavaşlığına katlanmadan çözer. Sırrı bir **potansiyel fonksiyonudur**: süpernode'dan Bellman-Ford ile bulunan $\delta(s,v)$'yi her düğüme atayıp kenarları $w' = w + h(u) - h(v)$ ile yeniden ağırlıklandırır. Üçgen eşitsizliği bunu negatif-olmayan yapar, telescoping en kısa yolları korur — böylece hızlı Dijkstra'yı V kez çalıştırabiliriz. Johnson yeni bir algoritma değil; zor problemi kolay kara kutuya çeviren akıllı bir indirgemedir. Bununla **çizge ünitesi kapanır**; sırada algoritma *tasarlamayı* öğreten dinamik programlama var.
:::
