---
title: "Bellman-Ford"
subtitle: "DAG kısıtını kaldırırız: herhangi bir ağırlıklı çizgede (çevrim ve negatif ağırlık dahil) tek-kaynak en kısa yol; sonlu en kısa yol V−1 kenardan uzun olamaz (basittir), çizgeyi V+1 seviyeye çoğaltıp DAG yaparak DAG relaxation çağırırız, V kenarda hâlâ kısalan tanıkları bulup onlardan eksi sonsuz yayarız — hepsi O(V·E)"
---
::: {.callout-note title="Bölüm bilgisi"}
- **Ku'nun videosu:** [YouTube — Lecture 12: Bellman-Ford](https://www.youtube.com/watch?v=f9cVS_URPc0) (~57 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 12: Bellman-Ford](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-12-bellman-ford/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 18 (L12)
- **Hoca:** Jason Ku (ağırlıklı en kısa yollar ünitesinin en genel algoritması)
- **Okuma süresi:** ~27 dk
> Bir önceki ünite dersinde (Ders 16) DAG relaxation, ağırlıklı SSSP'yi yalnızca **çevrimsiz** çizgelerde $O(V+E)$'de çözdü. Bu ders DAG kısıtını kaldırır: Bellman-Ford *herhangi* bir çizgede çalışır, negatif ağırlıklı çevrimleri tespit eder ve onlardan erişilen düğümlere $-\infty$ atar.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d18}
DAG relaxation (Ders 16) yalnızca çevrimsiz çizgelerde çalışıyordu. Bu ders (Jason Ku), **en genel** tek-kaynak en kısa yol algoritmasını verir: **Bellman-Ford**. *Herhangi* bir ağırlıklı çizgede — çevrimler ve negatif ağırlıklar dahil — çalışır; negatif ağırlıklı çevrimleri tespit eder ve onlardan erişilen düğümlere $-\infty$ atar.
> *"if a negative weight cycle is reachable from our source, then the vertices in that cycle and anything reachable from that cycle will potentially have an unbounded number of edges."* — Ku, 2:22
Üç ana fikir:
1. **En kısa yollar basittir** — $\delta$ sonluysa düğüm tekrarsız (simple) bir en kısa yol vardır; bu da en fazla **$V-1$ kenar** demektir.
2. **k-kenar mesafesi + tanık** — "en fazla $k$ kenarlı" mesafeyi izleyerek, $V$ kenarda hâlâ kısalan düğüm bir **tanıktır** (witness) → negatif çevrim kanıtı.
3. **Graf çoğaltma** — çizgeyi $V+1$ seviyeye kopyalayıp DAG'a çevir; DAG relaxation'ı çağır → $O(V \cdot E)$.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 18'in (L12) kavram haritası: kök = Bellman-Ford (Ku) — herhangi ağırlıklı çizgede en genel SSSP. Dört dal — (1) en kısa yollar basittir: delta sonlu ise düğüm tekrarsız yol var → en fazla V−1 kenar; bu, sonsuz yol kümesini sonlandırır. (2) k-kenar mesafesi delta_k = en fazla k kenarlı en kısa mesafe; V kenarda hâlâ kısalan düğüm bir tanıktır → negatif çevrim kanıtı; delta = eksi sonsuz ise düğüm bir tanıktan erişilir. (3) graf çoğaltma: çizgeyi V+1 seviyeye kopyala, kenarlar yalnız bir üst seviyeye gider + 0 ağırlıklı kalma kenarı → seviye-içi kenar yok → DAG; şimdi DAG relaxation kara kutusu çağrılır. (4) algoritma dört adım: G' kur → DAG relaxation → sonlu mesafeleri ata → tanıktan eksi sonsuz yay; toplam O(V·E). Sonuç: çevrimli/negatif problemi, çözmeyi bildiğimiz çevrimsiz bir probleme indirger; bedeli yalnız bir V çarpanı."
flowchart TD
A["Ders 18 (L12): Bellman-Ford"] --> S["en kısa yollar basittir"]
S --> S1["delta sonlu → tekrarsız yol<br/>en fazla V−1 kenar"]
A --> K["k-kenar mesafesi + tanık"]
K --> K1["delta_k = en fazla k kenarlı en kısa<br/>V kenarda kısalan = tanık → negatif çevrim"]
A --> D["graf çoğaltma"]
D --> D1["V+1 seviye + 0 kalma kenarı<br/>seviye-içi kenar yok → DAG → relaxation"]
A --> G["algoritma — dört adım"]
G --> G1["G' kur → DAG relaxation → sonlu ata<br/>tanıktan eksi sonsuz yay → O(V·E)"]
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 S,K,D,G branch
class S1,K1,D1,G1 leaf
```
::: {.callout-tip title="Builder Notu — DAG Kısıtı Kalkınca"}
DAG relaxation (Ders 16) topolojik sıraya dayanıyordu, çevrim olduğunda topolojik sıra yoktur. Bellman-Ford aynı "relax" tekniğini korur ama çevrime ve negatif ağırlığa izin verir; karşılığında bir $V$ çarpanı öder. Püf noktası tek bir gözlemdir: sonlu bir en kısa yol $V-1$ kenardan uzun olamaz.
- **İleriye → yönlendirme:** Bellman-Ford, distance-vector yönlendirme protokollerinin (RIP) temelidir — her router komşularından mesafe alıp gevşetir.
- **İleriye → arbitraj:** negatif ağırlıklı çevrim tespiti, döviz çevrim grafında **kâr döngüsü** (arbitraj) bulmaktır.
- **İleriye → graf çoğaltma:** "düğümü duruma göre çoğalt" tekniği, durum-augmentasyonlu birçok problemde (zaman, yakıt, mod) tekrar eder.
- **Geriye → DAG relaxation (Ders 16):** Bellman-Ford, problemi bir DAG'a indirgeyip o algoritmayı kara kutu olarak kullanır.
Tek cümle: *En kısa yol sonluysa $V-1$ kenardan uzun olamaz; çizgeyi $V+1$ seviyeye çoğaltıp DAG yaparak DAG relaxation çağırırız, $V$ kenarda hâlâ kısalan düğümleri tanık olarak işaretleyip $-\infty$ yayarız — hepsi $O(V \cdot E)$.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 18 (L12) Bellman-Ford motoru (_engine.py D18 bölümü:
# k_edge_distances → brute_simple_path_sssp) + D16 INF/relax_edge/dag_relaxation
# + D15 topological_order/finishing_order (dag_sssp için) + 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 build_bf_example /
# k_edge_distances / bellman_ford_classic / bellman_ford_via_dag /
# build_duplicated_dag / _reachable_from / brute_simple_path_sssp /
# build_weighted_dag_example / dag_sssp / dag_relaxation / path_weight +
# 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). Standalone testte savefig
# kullanılır; Quarto render'da jupyter inline backend'i ayarlar.
# ============================================================================
import math
from collections import deque
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, FancyBboxPatch, FancyArrowPatch
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir) + apply_style
# ---------------------------------------------------------------------------
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"
COL_OK = "#3f7d5e"
COL_OK_BG = "#cfe8da"
# −∞ düğümler için koyu dolgu (slate türevi)
COL_NEGINF = "#374151"
COL_NEGINF_DARK = "#1f2937"
def apply_style(ax):
"""Bir eksene tutarlı Slate+Amber görünümü uygular (curve figürleri için)."""
ax.set_facecolor(COL_WHITE)
ax.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8)
for spine in ax.spines.values():
spine.set_color(COL_SLATE_400)
ax.tick_params(colors=COL_TEXT)
ax.title.set_color(COL_TEXT)
ax.xaxis.label.set_color(COL_TEXT)
ax.yaxis.label.set_color(COL_TEXT)
return ax
# ---------------------------------------------------------------------------
# _engine.py D15 (L10) — finishing_order / topological_order (dag_sssp için)
# ---------------------------------------------------------------------------
def finishing_order(adj):
"""Bitiş sırası (L10 §9): full DFS; visit TAMAMLANINCA ekle."""
parent, order = {}, []
def visit(u):
for v in adj[u]:
if v not in parent:
parent[v] = u
visit(v)
order.append(u)
for s in adj:
if s not in parent:
parent[s] = None
visit(s)
return order
def topological_order(adj):
"""Topolojik sıra (L10 §9): TERS bitiş sırası (DAG'da geçerli)."""
return list(reversed(finishing_order(adj)))
# ---------------------------------------------------------------------------
# _engine.py D16 (L11) — relax_edge / dag_relaxation / dag_sssp / path_weight
# (Bellman-Ford bu D16 kara kutusunu çoğaltılmış DAG üzerinde çağırır).
# ---------------------------------------------------------------------------
INF = float("inf")
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 dag_relaxation(adj, weight, s, topo_order):
"""DAG relaxation (L11 §10): d=∞, d[s]=0; topolojik sırada gevşet. O(V+E)."""
d = {v: INF for v in adj}
d[s] = 0
for u in topo_order:
for v in adj[u]:
relax_edge(d, weight, u, v)
return d
def dag_sssp(adj, weight, s):
"""topolojik sıra (D15) + DAG relaxation — tek çağrı."""
return dag_relaxation(adj, weight, s, topological_order(adj))
def build_weighted_dag_example():
"""L11 §10 örneği (D16 DAG): kaynak e; δ(e,·)= e0 f3 g5 h6 d3 c8, a/b=∞."""
adj = {"a": ["b"], "b": [], "e": ["f"], "f": ["h", "g"],
"g": ["h", "d"], "h": [], "d": ["c"], "c": []}
weight = {("a", "b"): 1, ("e", "f"): 3, ("f", "h"): 8, ("f", "g"): 2,
("g", "h"): 1, ("g", "d"): -2, ("d", "c"): 5}
topo = ["a", "b", "e", "f", "g", "h", "d", "c"]
return adj, weight, topo
# ---------------------------------------------------------------------------
# _engine.py D18 (L12) — Bellman-Ford — Ku; genel SSSP (çevrim + negatif dahil)
# Ku L12: en kısa yollar BASİTTİR (δ sonlu → ≤ V−1 kenar); k-kenar mesafesi δₖ;
# TANIK = δ_V(v) < δ_{V−1}(v) (negatif çevrim kanıtı); δ=−∞ ⟺ tanıktan erişilir;
# GRAF ÇOĞALTMA: V+1 seviye + 0-kalma kenarları → DAG → D16 dag_relaxation kara
# kutusu → O(V·E). Klasik V-tur sürümü de (Egzersiz 4).
# ---------------------------------------------------------------------------
def k_edge_distances(adj, weight, s, kmax):
"""δₖ(s,v) tablosu (L12 §4): k = 0..kmax için en fazla k kenarlı en kısa
mesafeler. Figür/Egzersiz-1 tanığı. Döndürür: liste[k][v]."""
d0 = {v: INF for v in adj}
d0[s] = 0
table = [d0]
for _ in range(kmax):
prev = table[-1]
cur = dict(prev) # "kalma" kenarı: δₖ ≤ δₖ₋₁
for u in adj:
if prev[u] == INF:
continue
for v in adj[u]:
if prev[u] + weight[(u, v)] < cur[v]:
cur[v] = prev[u] + weight[(u, v)]
table.append(cur)
return table
def _reachable_from(adj, start):
"""start kümesinden erişilebilen düğümler (tanık → −∞ 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
def bellman_ford_classic(adj, weight, s):
"""Klasik Bellman-Ford (L12 not + Egzersiz 4): V−1 tur kenar gevşetme;
V. turda hâlâ gevşeyen düğümler TANIK → erişilenlere −∞ yay. O(V·E)."""
d = {v: INF for v in adj}
d[s] = 0
n = len(adj)
for _ in range(n - 1): # V−1 tur (δ_{V−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: # V. tur: tanık tespiti
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_duplicated_dag(adj, weight):
"""Graf çoğaltma (L12 §7-8): V+1 seviye; (u,k)→(v,k+1) orijinal kenarlar +
(v,k)→(v,k+1) 0-ağırlıklı KALMA kenarları. Seviye-içi kenar YOK → DAG."""
n = len(adj)
adj2, weight2 = {}, {}
for k in range(n + 1):
for v in adj:
adj2[(v, k)] = []
for k in range(n):
for u in adj:
adj2[(u, k)].append((u, k + 1)) # kalma
weight2[((u, k), (u, k + 1))] = 0
for v in adj[u]:
adj2[(u, k)].append((v, k + 1)) # seviye-atlamalı
weight2[((u, k), (v, k + 1))] = weight[(u, v)]
return adj2, weight2
def bellman_ford_via_dag(adj, weight, s):
"""Ders algoritması (L12 §9): çoğaltılmış DAG + D16 dag_relaxation kara
kutusu; d(v) = δ(s₀, v_{V−1}); tanık = δ(v_V) < δ(v_{V−1}) → −∞ yay."""
n = len(adj)
adj2, weight2 = build_duplicated_dag(adj, weight)
topo = [(v, k) for k in range(n + 1) for v in adj] # seviye sırası = topo
delta = dag_relaxation(adj2, weight2, (s, 0), topo)
d = {v: delta[(v, n - 1)] for v in adj}
witnesses = {v for v in adj if delta[(v, n)] < delta[(v, n - 1)]}
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)."""
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
def brute_simple_path_sssp(adj, weight, s):
"""Bağımsız tanık (küçük çizge): TÜM BASİT yolları DFS ile gez, min ağırlık
(≤ V−1 kenar — Claim 1). −∞'ları AYIRMAZ (sonlu kıyas için)."""
best = {v: INF for v in adj}
best[s] = 0
def rec(u, total, seen):
for v in adj[u]:
if v in seen:
continue
t2 = total + weight[(u, v)]
if t2 < best[v]:
best[v] = t2
rec(v, t2, seen | {v})
rec(s, 0, {s})
return best
```
## 1. Bellman-Ford'un Hedefi {#sec-1-bellman-ford-hedefi}
Çizge çevrim ve negatif ağırlık içerebilir. Hedef: her düğüm için $\delta(s, v)$ hesapla — erişilemez ise $+\infty$, **negatif ağırlıklı çevrimden** erişilen ise $-\infty$, diğerleri sonlu. Ek olarak, varsa bir negatif çevrim döndür. Çalışma süresi hedefi $O(V \cdot E)$.
## 2. Isınma: Yönsüz Çevrim ve İndirgeme {#sec-2-isinma-yonsuz-cevrim-indirgeme}
İki kısa alıştırma:
- **Yönsüz çizgede negatif çevrim $\Leftrightarrow$ negatif kenar.** Yönsüz bir negatif kenar üzerinde ileri-geri gidersek (uzunluk-2 çevrim) negatif çevrim olur. Yani yönsüz hâl ilginç değil; bu ders **yönlü** çizgelere odaklanır.
- **$O(V \cdot (V+E)) \to O(V \cdot E)$ indirgemesi.** Bir algoritma SSSP'yi $O(V \cdot (V+E))$'de çözüyorsa: önce BFS/DFS ile $s$'den **erişilebilenleri** bul, gerisini at. Kalan çizgede $V = O(E)$ (bağlı bileşen en fazla $E+1$ düğüm), dolayısıyla $V+E = O(E)$ → toplam $O(V \cdot E)$. (Bu yüzden $V \cdot (V+E)$ hedefiyle $V \cdot E$ aynı.)
## 3. En Kısa Yollar Basittir {#sec-3-en-kisa-yollar-basittir}
**Çalışılan Örnek — Claim 1.** $\delta(s, v)$ **sonlu** ise, $s$'den $v$'ye **basit** (simple, düğüm tekrarsız) bir en kısa yol vardır.
> *"if my shortest path distance from S to some vertex is finite... there exists a shortest S to V path that is simple."* — Ku, 11:06
Kanıt: bir en kısa yol bir çevrim $C$ içerse, $\delta$ sonlu olduğundan $w(C)$ negatif **olamaz** (negatif olsaydı tekrar tekrar dolaşıp $-\infty$ yapardık). $w(C) \geq 0$ ise çevrimi atıp daha kısa (veya eşit) bir yol elde ederiz; tekrar tekrar atarak basit bir yola ineriz.
Sonuç (kutula): basit yol en fazla $V$ düğüm → en fazla **$V-1$ kenar** kullanır.
> *"simple paths have at most V minus 1 edges."* — Ku, 14:06
Yani $\delta$ sonluysa, yalnızca **en fazla $V-1$ kenarlı** yolları kontrol etmek yeter (sonsuz değil, sonlu bir küme).
@fig-simple-paths bu gözlemi iki panelde gösterir: solda pozitif/sıfır ağırlıklı çevrimi atınca basit yolun daha kısa/eşit olduğu mini örnek (çevrimli yol 11 vs basit yol 7), sağda zincir akışı ($\delta$ sonlu → basit yol → en fazla $V-1$ kenar) ve sonlu arama uzayı.
```{python}
#| label: fig-simple-paths
#| fig-cap: "En kısa yollar BASİTTİR: δ sonlu → çevrim at → en fazla V−1 kenar (Bellman-Ford'u SONLANDIRIR) (L12 §3 İMZA). SOL panel pozitif/sıfır çevrim durumu: mini çizge s→a→b→t + b→a geri kenarı (çevrim a→b→a, w(C) = 3+1 = 4 ≥ 0). Çevrimli yol s→a→b→a→b→t (çevrim parçası soluk + makas ✂) ağırlık 11 üstü çizili vs çevrimi ATILMIŞ BASİT yol s→a→b→t (amber kalın) ağırlık 7 — w(C) ≥ 0 ise çevrimi at → daha kısa/eşit. Dipnot: çevrim NEGATİF olursa (build_bf_example w(C) = −2 < 0) δ = −∞, en kısa yol YOK. SAĞ panel kural kutusu: δ(s,v) SONLU → BASİT en kısa yol VAR → en fazla V düğüm → en fazla V−1 kenar (Ku 14:06); altında 0..V−1 sonlu sayı doğrusu (sonsuz yol uzayı yerine sonlu arama). Veri MOTORDAN: path_weight basit = 7 ≤ çevrimli = 11 (w(C)=4≥0); build_bf_example çevrim = −2 (Ku 11:06, 14:06)."
#| fig-width: 11.0
#| fig-height: 6.2
# fig-simple-paths (L12 §3 İMZA): δ sonlu → çevrim at → BASİT yol → V−1 kenar.
# Veri MOTORDAN (build_bf_example / path_weight). networkx YOK — elle koordinat.
_MINI_W = {("s", "a"): 2, ("a", "b"): 3, ("b", "a"): 1, ("b", "t"): 2}
_MINI_POS = {"s": (0.0, 0.0), "a": (1.55, 0.0), "b": (3.10, 0.0), "t": (4.65, 0.0)}
_SP_R = 0.30
def _sp_node(ax, name, hot=False, dim=False):
x, y = _MINI_POS[name]
if hot:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.6
elif dim:
fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_SLATE_400, 1.4
else:
fc, ec, tcol, lw = COL_BG, COL_PRIMARY, COL_TEXT, 2.0
ax.add_patch(Circle((x, y), _SP_R, facecolor=fc, edgecolor=ec,
linewidth=lw, alpha=0.55 if dim else 1.0, zorder=5))
ax.text(x, y, name, ha="center", va="center", fontsize=13,
color=tcol, weight="bold", alpha=0.6 if dim else 1.0, zorder=6)
def _sp_straight(ax, u, v, wt, color, lw, alpha=1.0, wbg=COL_WHITE,
wec=COL_SLATE_400, wtcol=COL_TEXT, zbase=2):
ux, uy = _MINI_POS[u]
vx, vy = _MINI_POS[v]
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=15,
color=color, linewidth=lw, shrinkA=_SP_R * 72, shrinkB=_SP_R * 72,
alpha=alpha, zorder=zbase))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
ax.add_patch(FancyBboxPatch(
(mx - 0.15, my - 0.15), 0.30, 0.30,
boxstyle="round,pad=0.01,rounding_size=0.06",
fc=wbg, ec=wec, linewidth=1.4, alpha=alpha, zorder=zbase + 4))
ax.text(mx, my, str(wt), ha="center", va="center", fontsize=9,
color=wtcol, weight="bold", alpha=alpha, zorder=zbase + 5)
def _sp_draw_left(ax):
sw = path_weight(_MINI_W, ["s", "a", "b", "t"])
cw = path_weight(_MINI_W, ["s", "a", "b", "a", "b", "t"])
cyc_w = path_weight(_MINI_W, ["a", "b", "a"])
ax.text(2.32, 2.55, "w(C) ≥ 0 ise çevrimi AT", ha="center", va="center",
fontsize=12, color=COL_PRIMARY, weight="bold", zorder=7)
bx, by = _MINI_POS["b"]
axx, ayy = _MINI_POS["a"]
ax.add_patch(FancyArrowPatch(
(bx, by), (axx, ayy), arrowstyle="-|>", mutation_scale=13,
color=COL_SLATE_400, linewidth=2.0, shrinkA=_SP_R * 72, shrinkB=_SP_R * 72,
connectionstyle="arc3,rad=-0.55", alpha=0.75, zorder=2))
midx, midy = (bx + axx) * 0.5, 0.95
ax.add_patch(FancyBboxPatch(
(midx - 0.15, midy - 0.15), 0.30, 0.30,
boxstyle="round,pad=0.01,rounding_size=0.06",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.3, alpha=0.85, zorder=6))
ax.text(midx, midy, "1", ha="center", va="center", fontsize=8.5,
color=COL_SLATE_500, weight="bold", alpha=0.9, zorder=7)
ax.text(midx, midy + 0.42, "✂ çevrim a→b→a", ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=7)
ax.text(midx, midy - 0.43, f"w(C) = 3+1 = {cyc_w} (≥ 0)", ha="center",
va="center", fontsize=8, color=COL_SLATE_500, zorder=7)
_sp_straight(ax, "s", "a", _MINI_W[("s", "a")], COL_ACCENT, 2.6,
wbg=COL_AMBER_100, wec=COL_ACCENT, wtcol=COL_AMBER_700, zbase=3)
_sp_straight(ax, "a", "b", _MINI_W[("a", "b")], COL_ACCENT, 2.6,
wbg=COL_AMBER_100, wec=COL_ACCENT, wtcol=COL_AMBER_700, zbase=3)
_sp_straight(ax, "b", "t", _MINI_W[("b", "t")], COL_ACCENT, 2.6,
wbg=COL_AMBER_100, wec=COL_ACCENT, wtcol=COL_AMBER_700, zbase=3)
for nm in ("s", "a", "b", "t"):
_sp_node(ax, nm, hot=(nm in ("s", "t")))
ax.text(2.32, -0.95, f"çevrimli yol s→a→b→a→b→t = {cw}", ha="center",
va="center", fontsize=9, color=COL_SLATE_500, zorder=7)
ax.plot([0.62, 4.02], [-0.95, -0.95], color=COL_SLATE_400,
linewidth=1.1, alpha=0.55, zorder=6)
ax.text(2.32, -1.42, f"BASİT yol s→a→b→t = {sw} ✓ daha kısa/eşit",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=7)
nadj, nw = build_bf_example()
neg_cyc = path_weight(nw, ["b", "c", "d", "b"])
ax.text(2.32, -2.05,
f"(çevrim NEGATİF olursa, ör. w(C) = {neg_cyc} < 0 → δ = −∞: en kısa yol YOK)",
ha="center", va="center", fontsize=8, color=COL_SLATE_500,
style="italic", zorder=7)
return sw, cw, cyc_w
def _sp_number_line(ax, x0, y0, vmax, label):
span = 4.6
step = span / vmax
ax.add_patch(FancyArrowPatch(
(x0 - 0.15, y0), (x0 + span + 0.30, y0), arrowstyle="-|>",
mutation_scale=12, color=COL_SLATE_500, linewidth=1.5, zorder=4))
for k in range(vmax + 1):
x = x0 + k * step
ax.add_patch(Circle((x, y0), 0.055, facecolor=COL_ACCENT,
edgecolor=COL_AMBER_700, linewidth=1.0, zorder=6))
lbl = str(k) if k < vmax else "V−1"
ax.text(x, y0 - 0.30, lbl, ha="center", va="center", fontsize=8,
color=COL_AMBER_700 if k == vmax else COL_SLATE_500,
weight="bold" if k == vmax else "normal", zorder=6)
ax.text(x0 + span * 0.5, y0 + 0.42, label, ha="center", va="center",
fontsize=8.5, color=COL_TEXT, style="italic", zorder=6)
def _sp_draw_right(ax):
bx, by, bw, bh = 0.0, 0.40, 5.2, 3.65
ax.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.04,rounding_size=0.12",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
cx = bx + bw * 0.5
lines = [
("δ(s, v) SONLU", COL_AMBER_700, 12.5, "bold"),
("↓", COL_SLATE_500, 13, "bold"),
("BASİT en kısa yol VAR (çevrim atılır)", COL_TEXT, 11, "bold"),
("↓", COL_SLATE_500, 13, "bold"),
("yol en fazla V düğüm gezer", COL_TEXT, 11, "bold"),
("↓", COL_SLATE_500, 13, "bold"),
]
yy = by + bh - 0.42
for txt, col, fs, wt in lines:
ax.text(cx, yy, txt, ha="center", va="center", fontsize=fs,
color=col, weight=wt, zorder=5)
yy -= 0.46
ax.add_patch(FancyBboxPatch(
(cx - 1.55, yy - 0.30), 3.10, 0.62,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE, ec=COL_ACCENT, linewidth=2.6, zorder=5))
ax.text(cx, yy, "en fazla V − 1 kenar", ha="center", va="center",
fontsize=13.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(cx, yy - 0.50, "(Ku 14:06)", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, style="italic", zorder=6)
_sp_number_line(ax, bx + 0.30, by - 0.70, 6,
"yol uzunluğu olasılıkları: 0 .. V−1 (SONLU küme)")
ax.text(cx, by - 1.55,
"sonsuz yol uzayı → SONLU arama (her uzunluk en fazla bir kez)",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=6)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_sp_nadj, _sp_nw = build_bf_example()
assert path_weight(_sp_nw, ["b", "c", "d", "b"]) == -2
_sp_sw = path_weight(_MINI_W, ["s", "a", "b", "t"])
_sp_cw = path_weight(_MINI_W, ["s", "a", "b", "a", "b", "t"])
_sp_cyc = path_weight(_MINI_W, ["a", "b", "a"])
assert (_sp_sw, _sp_cw, _sp_cyc) == (7, 11, 4), (_sp_sw, _sp_cw, _sp_cyc)
assert _sp_sw <= _sp_cw and _sp_cyc >= 0
fig, (_sp_axL, _sp_axR) = plt.subplots(1, 2, figsize=(11.0, 6.2),
gridspec_kw={"width_ratios": [1.05, 1.0]})
fig.patch.set_facecolor(COL_WHITE)
_sp_draw_left(_sp_axL)
_sp_axL.set_title("Çevrimli yol vs çevrim atılmış BASİT yol",
color=COL_TEXT, fontsize=11.5, weight="bold", pad=10)
_sp_axL.set_xlim(-0.7, 5.4)
_sp_axL.set_ylim(-2.5, 2.95)
_sp_axL.set_aspect("equal")
_sp_axL.axis("off")
_sp_draw_right(_sp_axR)
_sp_axR.set_title("Sonuç: en kısa yol BASİT → V−1 kenar",
color=COL_TEXT, fontsize=11.5, weight="bold", pad=10)
_sp_axR.set_xlim(-0.4, 5.6)
_sp_axR.set_ylim(-1.9, 4.4)
_sp_axR.set_aspect("equal")
_sp_axR.axis("off")
fig.suptitle(
"En kısa yollar BASİTTİR: δ sonlu → çevrim at → en fazla V−1 kenar "
"(Bellman-Ford'u SONLANDIRIR)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
plt.tight_layout(rect=(0, 0, 1, 0.95))
plt.show()
```
## 4. k-Kenar Mesafesi {#sec-4-k-kenar-mesafesi}
**k-kenar mesafesi** $\delta_k(s, v)$: en fazla $k$ kenar kullanan en kısa $s \to v$ yolunun ağırlığı. Eğer $\delta_k$'yı $k = V-1$ için hesaplarsak ve $\delta(s, v)$ sonluysa, gerçek en kısa yolu bulmuş oluruz (çünkü sonlu en kısa yol $\leq V-1$ kenar).
Bu, problemi sonlandırır: sonsuz sayıda yol yerine, kenar sayısını $V-1$ ile sınırlayıp **adım adım** mesafe hesaplarız.
## 5. Tanık (Witness) ve −∞ {#sec-5-tanik-ve-eksi-sonsuz}
Peki $-\infty$ düğümleri? Anahtar gözlem: eğer **$V$ kenarlı** en kısa mesafe ($\delta$, $k = V$), **$(V-1)$ kenarlı** mesafeden ($\delta$, $k = V-1$) **kesinlikle küçükse**, bu yeni (daha kısa) yol basit olamaz ($V$ kenar $> V-1$ düğüm → tekrar var) → içinde bir negatif çevrim vardır. Böyle bir $v$'ye **tanık (witness)** denir.
> *"I'm going to call V is a witness."* — Ku, 19:53
İddia: $\delta(s, v) = -\infty \Leftrightarrow v$, bir tanıktan **erişilebilir**. Yani tüm tanıkları bulup onlardan erişilen her düğümü $-\infty$ işaretlemek yeter.
@fig-delta-k-table örnek çizgeyi ve $\delta_k$ tablosunu birlikte gösterir: üstte negatif çevrimli çizge (kaynak `a`), altta $k = 0 \ldots 5$ satırları; $k = V = 4$ satırında `b` düğümünün $-5 \to -7$ düşmesi **tanık** vurgusudur (kenar tablosu motordan: `b` sütunu $[\infty, -5, -5, -5, -7, -7]$).
```{python}
#| label: fig-delta-k-table
#| fig-cap: "k-kenar mesafesi δₖ + TANIK: δ_V < δ_{V−1} ise basit yol olamaz → negatif çevrim → −∞ (L12 §4-5 İMZA). ÜST: örnek çizge — a→b(−5) girişi + b/c/d çevrim üçgeni (b→c −4, c→d 3, d→b −1; toplam −2 amber negatif rozet). ALT: δₖ(a, v) tablosu — satırlar k = 0..5, sütunlar a/b/c/d; hücrelerde δ değerleri (∞ glifi). k = V = 4 satırında DÜŞEN b hücresi (−5 → −7) AMBER dolgu + aşağı-ok = TANIK; çevrim her turda −2 kazandırır. Sağ kenar TANIK kutusu (Ku 19:53): δ_V(v) < δ_{V−1}(v) → V-kenarlı yol (V−1)-kenarlıdan kısa → o yol BASİT OLAMAZ → negatif çevrim içerir → δ(a,v) = −∞. ALT NOT: δ(a,v) = −∞ ⟺ v bir tanıktan erişilebilir; burada b,c,d hepsi çevrimden erişilir → −∞, yalnız a = 0 sonlu. Veri MOTORDAN: k_edge_distances b = [∞,−5,−5,−5,−7,−7], c = [∞,∞,−9,−9,−9,−11], d = [∞,∞,∞,−6,−6,−6]; k=V=4'te −5→−7 TANIK düşüşü."
#| fig-width: 10.6
#| fig-height: 7.0
# fig-delta-k-table (L12 §4-5 İMZA): δₖ tablosu + k=V tanık düşüşü.
# Veri MOTORDAN (build_bf_example / k_edge_distances). networkx YOK.
_DK_POS = {"a": (0.0, 1.0), "b": (1.0, 1.0), "c": (2.0, 1.6), "d": (2.0, 0.4)}
_DK_EDGES = [("a", "b", -5, True), ("b", "c", -4, True),
("c", "d", 3, False), ("d", "b", -1, True)]
_DK_R = 0.24
def _dk_draw_mini_graph(ax, x_off, y_off):
def P(v):
x, y = _DK_POS[v]
return (x + x_off, y + y_off)
rad = {("b", "c"): 0.0, ("c", "d"): 0.0, ("d", "b"): 0.30, ("a", "b"): 0.0}
for u, v, wt, neg in _DK_EDGES:
ux, uy = P(u)
vx, vy = P(v)
ecol = COL_ACCENT if neg else COL_PRIMARY
r = rad[(u, v)]
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=14,
color=ecol, linewidth=2.2 if neg else 2.0,
shrinkA=_DK_R * 74, shrinkB=_DK_R * 74,
connectionstyle=f"arc3,rad={r}", zorder=2))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
if r != 0.0:
mx -= 0.36
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.17, my - 0.135), 0.34, 0.27,
boxstyle="round,pad=0.01,rounding_size=0.06",
fc=bg, ec=ec, linewidth=1.6 if neg else 1.1, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center",
fontsize=9, color=tcol, weight="bold", zorder=7)
for v in _DK_POS:
x, y = P(v)
is_src = (v == "a")
fc = COL_AMBER_100 if is_src else COL_BG
ec = COL_ACCENT if is_src else COL_PRIMARY
lw = 2.8 if is_src else 2.0
ax.add_patch(Circle((x, y), _DK_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
tcol = COL_AMBER_700 if is_src else COL_TEXT
ax.text(x, y, v, ha="center", va="center", fontsize=12.5,
color=tcol, weight="bold", zorder=6)
sx, sy = P("a")
ax.text(sx, sy + _DK_R + 0.20, "kaynak", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=6)
cx, cy = P("c")
dx, dy = P("d")
bx, by = P("b")
cyc_x = max(cx, dx) + 1.30
cyc_y = (cy + dy) * 0.5
ax.add_patch(FancyBboxPatch(
(cyc_x - 0.88, cyc_y - 0.30), 1.76, 0.60,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=6))
ax.text(cyc_x, cyc_y + 0.11, "çevrim b→c→d→b", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=7)
ax.text(cyc_x, cyc_y - 0.12, "toplam = −2 (negatif)", ha="center",
va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=7)
ax.text(bx + 0.0, by + 1.05, "Ağırlıklı çizge (kaynak a, negatif çevrim)",
ha="center", va="center", fontsize=10.5, color=COL_PRIMARY,
weight="bold", zorder=6)
def _dk_fmt(val):
if val == INF:
return "∞"
if val == -INF:
return "−∞"
return str(val).replace("-", "−")
def _dk_draw_table(ax, table, cols, x0, y_top, witness_k):
n_k = len(table)
n_c = len(cols)
cell_w, cell_h = 1.05, 0.66
head_h = 0.50
klabel_w = 1.05
witness_x = None
for c, name in enumerate(cols):
cx = x0 + klabel_w + c * cell_w + cell_w * 0.5
ax.text(cx, y_top + head_h * 0.5, name, ha="center", va="center",
fontsize=12, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(x0 + klabel_w * 0.5, y_top + head_h * 0.5, "k ╲ v",
ha="center", va="center", fontsize=9.5, color=COL_SLATE_500,
weight="bold", zorder=6)
for k in range(n_k):
y = y_top - (k + 1) * cell_h
is_witness_row = (k == witness_k)
klab = f"k = {k}"
if k == witness_k:
klab = f"k = V = {k}"
ax.text(x0 + klabel_w - 0.12, y + cell_h * 0.5, klab,
ha="right", va="center",
fontsize=9.5 if k != witness_k else 10,
color=COL_AMBER_700 if k == witness_k else COL_SLATE_500,
weight="bold", zorder=6)
for c, name in enumerate(cols):
x = x0 + klabel_w + c * cell_w
val = table[k][name]
prev = table[k - 1][name] if k > 0 else None
dropped = is_witness_row and (prev is not None) and (val < prev)
if dropped:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 2.6, COL_AMBER_700
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.3, COL_TEXT
ax.add_patch(FancyBboxPatch(
(x, y), cell_w * 0.94, cell_h * 0.92, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=3))
cx, cy = x + cell_w * 0.47, y + cell_h * 0.46
ax.text(cx, cy, _dk_fmt(val), ha="center", va="center",
fontsize=12 if val != INF else 13,
color=tcol, weight="bold", zorder=5)
if dropped:
cx_prev = x + cell_w * 0.47
if witness_x is None:
witness_x = (cx_prev, _dk_fmt(prev), _dk_fmt(val))
ax.add_patch(FancyArrowPatch(
(cx_prev, y + cell_h * 1.30), (cx_prev, y + cell_h * 0.92),
arrowstyle="-|>", mutation_scale=12, color=COL_AMBER_700,
linewidth=2.0, zorder=7))
table_bottom = y_top - n_k * cell_h
table_right = x0 + klabel_w + n_c * cell_w
return table_bottom, table_right, witness_x
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_dk_adj, _dk_w = build_bf_example()
_dk_kmax = 5
_dk_raw = k_edge_distances(_dk_adj, _dk_w, "a", _dk_kmax)
_dk_cols = ["a", "b", "c", "d"]
_dk_table = [dict(row) for row in _dk_raw]
_dk_col_b = [_dk_table[k]["b"] for k in range(_dk_kmax + 1)]
_dk_col_c = [_dk_table[k]["c"] for k in range(_dk_kmax + 1)]
_dk_col_d = [_dk_table[k]["d"] for k in range(_dk_kmax + 1)]
assert _dk_col_b == [INF, -5, -5, -5, -7, -7], _dk_col_b
assert _dk_col_c == [INF, INF, -9, -9, -9, -11], _dk_col_c
assert _dk_col_d == [INF, INF, INF, -6, -6, -6], _dk_col_d
_dk_V = len(_dk_adj)
assert _dk_V == 4
assert _dk_table[_dk_V]["b"] == -7 and _dk_table[_dk_V - 1]["b"] == -5
fig, ax = plt.subplots(figsize=(10.6, 7.0))
fig.patch.set_facecolor(COL_WHITE)
_dk_draw_mini_graph(ax, x_off=0.55, y_off=4.55)
_dk_tbl_x0 = 0.30
_dk_tbl_top = 3.55
ax.text(_dk_tbl_x0, _dk_tbl_top + 0.85,
"δₖ(a, v) = en fazla k kenarlı en kısa mesafe "
"(her satır: bir kenar daha gevşet)",
ha="left", va="center", fontsize=9.5, color=COL_PRIMARY,
weight="bold", zorder=6)
_dk_bottom, _dk_right, _dk_wit = _dk_draw_table(
ax, _dk_table, _dk_cols, _dk_tbl_x0, _dk_tbl_top, witness_k=_dk_V)
if _dk_wit is not None:
_wx, _wprev, _wval = _dk_wit
_wrow_y = _dk_tbl_top - (_dk_V + 0.5) * 0.66
_bx_badge = _dk_right + 1.85 + 0.25
_by_badge = 0.78
ax.add_patch(FancyBboxPatch(
(_bx_badge, _by_badge - 0.27), 4.10, 0.52,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=8))
ax.text(_bx_badge + 0.22, _by_badge,
f"k = V satırında b: {_wprev} → {_wval} DÜŞTÜ = TANIK",
ha="left", va="center", fontsize=8.8, color=COL_AMBER_700,
weight="bold", zorder=9)
ax.add_patch(FancyArrowPatch(
(_wx + 0.55, _wrow_y), (_bx_badge - 0.05, _by_badge),
arrowstyle="-|>", mutation_scale=11, color=COL_AMBER_600,
linewidth=1.6, zorder=7, connectionstyle="arc3,rad=-0.20"))
_dk_box_x = _dk_right + 1.85
_dk_box_top = _dk_tbl_top - 0.10
_dk_box_w, _dk_box_h = 4.35, 2.95
ax.add_patch(FancyBboxPatch(
(_dk_box_x, _dk_box_top - _dk_box_h), _dk_box_w, _dk_box_h,
boxstyle="round,pad=0.04,rounding_size=0.12",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
_dk_bx = _dk_box_x + 0.25
ax.text(_dk_bx, _dk_box_top - 0.40, "TANIK (Ku 19:53)", ha="left", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold", zorder=4)
_dk_lines = [
("δ_V(v) < δ_{V−1}(v)", "mono"),
("→ V-kenarlı yol (V−1)-kenarlıdan KISA", "norm"),
("→ o yol BASİT OLAMAZ (≤ V−1 kenar şartı)", "norm"),
("→ negatif çevrim İÇERİR", "norm"),
("→ δ(a, v) = −∞", "hot"),
]
_dk_ly = _dk_box_top - 0.86
for _text, _kind in _dk_lines:
if _kind == "mono":
ax.text(_dk_bx, _dk_ly, _text, ha="left", va="center", fontsize=10.5,
color=COL_AMBER_700, family="monospace", weight="bold", zorder=4)
elif _kind == "hot":
ax.text(_dk_bx, _dk_ly, _text, ha="left", va="center", fontsize=10.5,
color=COL_AMBER_700, weight="bold", zorder=4)
else:
ax.text(_dk_bx, _dk_ly, _text, ha="left", va="center", fontsize=9.5,
color=COL_TEXT, zorder=4)
_dk_ly -= 0.48
_dk_note_y = _dk_bottom - 0.55
ax.text(_dk_tbl_x0, _dk_note_y,
"δ(a, v) = −∞ ⟺ v bir tanıktan erişilebilir "
"(negatif çevrim her turda ağırlığı düşürür → sınır yok)",
ha="left", va="center", fontsize=9.5, color=COL_TEXT,
weight="bold", zorder=6)
ax.text(_dk_tbl_x0, _dk_note_y - 0.40,
"burada b, c, d hepsi çevrimden erişilir → δ(a, b) = δ(a, c) = "
"δ(a, d) = −∞; yalnız a = 0 sonlu",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500,
style="italic", zorder=6)
fig.suptitle(
"k-kenar mesafesi δₖ + TANIK: δ_V < δ_{V−1} ise basit yol olamaz → negatif çevrim → −∞",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
ax.set_xlim(-0.3, _dk_box_x + _dk_box_w + 0.4)
ax.set_ylim(_dk_note_y - 0.85, 6.35)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 6. Her Negatif Çevrim Bir Tanık İçerir {#sec-6-her-negatif-cevrim-bir-tanik-icerir}
**Çalışılan Örnek — kanıt.** İddiayı kanıtlamak için şunu göstermek yeter:
> *"It suffices to prove that every negative weight cycle contains a witness."* — Ku, 22:43
Bir negatif çevrim $C$ al; her $v$ için üçgen eşitsizliği: $\delta_V(s, v) \leq \delta_{V-1}(s, v') + w(v', v)$ ($v' = v$'nin çevrimdeki öncülü). Bu eşitsizliği **çevrimdeki tüm düğümler üzerinde topla**: sol taraf $\sum \delta_V$, sağ taraf $\sum \delta_{V-1} + w(C)$. $w(C) < 0$ olduğundan, sol toplam sağ toplamdan **kesinlikle küçük** olur. O hâlde çevrimde en az bir düğüm $\delta_V < \delta_{V-1}$ eşitsizliğini sağlamalı — yani bir **tanık** içerir. (Hiçbiri tanık olmasaydı toplam eşitsizliği çökerdi: çelişki.)
@fig-witness-spread bu kanıtı üç panelde toplar: solda örnek çizge (tanık `b` yıldızlı, çevrimden erişilen `b/c/d` koyu $-\infty$), ortada yayılım akışı (tanık → DFS erişilebilirlik → $-\infty$ boyaması), sağda çevrim üzerinde toplama + $w(C) < 0$ çelişki argümanı.
```{python}
#| label: fig-witness-spread
#| fig-cap: "Bellman-Ford: TANIK (V. turda düşer) → DFS erişilebilirlik → −∞ yayılımı · her negatif çevrim bir tanık içerir (L12 §5-6 İMZA). SOL panel örnek çizge (kaynak a): çevrim b→c→d→b (toplam −2 < 0); TANIK olan b amber yıldızlı; çevrimden erişilen b,c,d koyu dolgulu δ = −∞; a = 0 temiz. ORTA panel yayılım akışı (3 aşama dikey): TANIK (δ_V(b) < δ_{V−1}(b), V. turda hâlâ düşer) → ERİŞİLEBİLİRLİK TARAMASI (DFS, tanıktan ulaşılan her düğüm) → −∞ BOYAMASI; erişilen küme { b, c, d }. SAĞ panel kanıt kutusu (Ku 22:43): çevrim C üzerinde her kenar için üçgen eşitsizliği δ_V(v_i) ≤ δ_{V−1}(v_{i−1}) + w(v_{i−1}, v_i); çevrim boyunca TOPLA → Σ δ_V ≤ Σ δ_{V−1} + w(C); w(C) = −2 < 0 → Σ δ_V < Σ δ_{V−1} → en az bir v_i'de düşüş = TANIK (çelişki: tanık yoksa düşüş olmaz ama w(C) < 0 zorlar). Veri MOTORDAN: bellman_ford_classic(a) = {a:0, b:−∞, c:−∞, d:−∞}; V. tur tanık = [b] (δ₄(b)=−7 < δ₃(b)=−5); erişilen = {b,c,d}; çevrim w = −2."
#| fig-width: 11.0
#| fig-height: 5.5
# fig-witness-spread (L12 §5-6 İMZA): tanık → DFS erişilebilirlik → −∞ yayılım.
# Veri MOTORDAN (build_bf_example / bellman_ford_classic / k_edge_distances /
# _reachable_from / path_weight). networkx YOK — elle koordinat.
_WS_POS = {"a": (0.0, 1.0), "b": (1.0, 1.0), "c": (2.0, 1.6), "d": (2.0, 0.4)}
_WS_EDGES = [("a", "b", -5), ("b", "c", -4), ("c", "d", 3), ("d", "b", -1)]
_WS_R = 0.26
def _ws_draw_graph(ax, source, witnesses, neginf_nodes):
cyc_edges = {("b", "c"), ("c", "d"), ("d", "b")}
for u, v, wt in _WS_EDGES:
ux, uy = _WS_POS[u]
vx, vy = _WS_POS[v]
on_cycle = (u, v) in cyc_edges
ecol = COL_ACCENT if on_cycle else COL_PRIMARY
rad = -0.18 if on_cycle else 0.0
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=15,
color=ecol, linewidth=2.4 if on_cycle else 2.0,
shrinkA=_WS_R * 78, shrinkB=_WS_R * 78,
connectionstyle=f"arc3,rad={rad}", zorder=2))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
if on_cycle:
dx, dy = vx - ux, vy - uy
nlen = (dx * dx + dy * dy) ** 0.5 or 1.0
mx += -dy / nlen * 0.22
my += dx / nlen * 0.22
neg = wt < 0
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.16, my - 0.13), 0.32, 0.26,
boxstyle="round,pad=0.01,rounding_size=0.06",
fc=bg, ec=ec, linewidth=1.7 if neg else 1.1, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center",
fontsize=8.5, color=tcol, weight="bold", zorder=7)
for v, (x, y) in _WS_POS.items():
is_src = (v == source)
is_neginf = (v in neginf_nodes)
if is_src:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 3.0, COL_AMBER_700
elif is_neginf:
fc, ec, lw, tcol = COL_NEGINF_DARK, COL_AMBER_600, 2.4, COL_WHITE
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 2.0, COL_TEXT
ax.add_patch(Circle((x, y), _WS_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, v, ha="center", va="center", fontsize=12.5,
color=tcol, weight="bold", zorder=6)
if is_neginf:
ax.text(x, y - _WS_R - 0.16, "δ = −∞", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=6)
elif is_src:
ax.text(x, y - _WS_R - 0.16, "δ = 0", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=6)
for wnode in witnesses:
wx, wy = _WS_POS[wnode]
ax.scatter([wx], [wy + _WS_R + 0.20], marker="*", s=320,
color=COL_ACCENT, edgecolor=COL_AMBER_700, linewidth=1.2,
zorder=8)
ax.text(wx + 0.30, wy + _WS_R + 0.22, "TANIK", ha="left", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=8)
sx, sy = _WS_POS[source]
ax.text(sx, sy + _WS_R + 0.18, "kaynak", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(2.78, 0.55, "çevrim\nb→c→d→b\nağırlığı −2\n(< 0)", ha="left",
va="center", fontsize=8, color=COL_AMBER_700, style="italic", zorder=6)
ax.text(1.0, 2.45, "Bellman-Ford örneği (kaynak a)", ha="center",
va="center", fontsize=11, color=COL_PRIMARY, weight="bold", zorder=6)
ax.set_xlim(-0.55, 3.95)
ax.set_ylim(-0.55, 2.65)
ax.set_aspect("equal")
ax.axis("off")
def _ws_draw_spread(ax, witnesses, reach):
stages = [
("TANIK", "δ_V(b) < δ_{V−1}(b)\n(V. turda hâlâ düşer)", COL_ACCENT, COL_AMBER_100),
("ERİŞİLEBİLİRLİK\nTARAMASI (DFS)", "tanıktan ulaşılan\ntüm düğümleri gez", COL_PRIMARY, COL_BG),
("−∞ BOYAMASI", "ulaşılan her düğüm\nδ = −∞", COL_AMBER_600, COL_NEGINF_DARK),
]
box_w, box_h = 2.05, 0.92
cx = 1.05
ys = [3.0, 1.55, 0.10]
for i, (title, sub, ec, fc) in enumerate(stages):
y = ys[i]
dark = (i == 2)
ax.add_patch(FancyBboxPatch(
(cx - box_w / 2, y), box_w, box_h,
boxstyle="round,pad=0.03,rounding_size=0.10",
fc=fc, ec=ec, linewidth=2.6, zorder=3))
tcol_title = COL_WHITE if dark else COL_AMBER_700 if i == 0 else COL_TEXT
tcol_sub = COL_AMBER_300 if dark else COL_SLATE_500
ax.text(cx, y + box_h * 0.66, title, ha="center", va="center",
fontsize=9.5, color=tcol_title, weight="bold", zorder=5)
ax.text(cx, y + box_h * 0.27, sub, ha="center", va="center",
fontsize=7.6, color=tcol_sub, style="italic", zorder=5)
if i < len(stages) - 1:
ya = y - 0.04
yb = ys[i + 1] + box_h + 0.04
ax.add_patch(FancyArrowPatch(
(cx, ya), (cx, yb), arrowstyle="-|>", mutation_scale=18,
color=COL_AMBER_700, linewidth=2.6, zorder=4))
reach_sorted = sorted(reach)
ax.text(cx, ys[2] - 0.30, "erişilen: { " + ", ".join(reach_sorted) + " }",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(cx, ys[2] - 0.62, "(b → c → d, çevrim boyunca)", ha="center",
va="center", fontsize=7.6, color=COL_SLATE_500, style="italic", zorder=5)
ax.text(cx, 4.12, "YAYILIM", ha="center", va="center",
fontsize=11, color=COL_PRIMARY, weight="bold", zorder=5)
ax.set_xlim(-0.15, 2.25)
ax.set_ylim(-0.95, 4.40)
ax.set_aspect("equal")
ax.axis("off")
def _ws_draw_proof(ax, cycle_w):
ax.add_patch(FancyBboxPatch(
(0.04, 0.04), 3.92, 4.42,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.2, zorder=1))
ax.text(2.0, 4.18, "HER NEGATİF ÇEVRİM\nBİR TANIK İÇERİR", ha="center",
va="center", fontsize=11, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(0.22, 3.55,
"Çevrim C = (v₀ → v₁ → … → vₖ = v₀) üzerinde\n"
"her kenar için üçgen eşitsizliği:",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, zorder=4)
ax.text(2.0, 3.02,
r"$\delta_V(v_i)\ \leq\ \delta_{V-1}(v_{i-1}) + w(v_{i-1}, v_i)$",
ha="center", va="center", fontsize=10.5, color=COL_PRIMARY, zorder=4)
ax.text(0.22, 2.62, "Çevrim boyunca TOPLA (Σ):", ha="left", va="center",
fontsize=8.6, color=COL_TEXT, weight="bold", zorder=4)
ax.text(2.0, 2.18,
r"$\sum_i \delta_V(v_i)\ \leq\ \sum_i \delta_{V-1}(v_i)\ +\ w(C)$",
ha="center", va="center", fontsize=10.5, color=COL_PRIMARY, zorder=4)
ax.text(2.0, 1.80, "(çevrim → her iki yanda aynı düğüm kümesi)",
ha="center", va="center", fontsize=7.6, color=COL_SLATE_500,
style="italic", zorder=4)
ax.add_patch(FancyBboxPatch(
(0.30, 1.10), 3.40, 0.52,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=3))
ax.text(2.0, 1.36,
r"$w(C) = %d\ <\ 0\ \Rightarrow\ \sum \delta_V\ <\ \sum \delta_{V-1}$" % cycle_w,
ha="center", va="center", fontsize=9.6, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(2.0, 0.66,
"Sol toplam KESİN küçük → en az bir vᵢ'de\n"
"δ_V(vᵢ) < δ_{V−1}(vᵢ) = TANIK",
ha="center", va="center", fontsize=8.8, color=COL_TEXT,
weight="bold", zorder=4)
ax.text(2.0, 0.22,
"Çelişki: tanık yoksa hiç düşüş olmaz, ama w(C)<0 düşüşü zorlar.",
ha="center", va="center", fontsize=7.4, color=COL_SLATE_500,
style="italic", zorder=4)
ax.set_xlim(-0.05, 4.05)
ax.set_ylim(-0.05, 4.55)
ax.set_aspect("equal")
ax.axis("off")
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_ws_adj, _ws_weight = build_bf_example()
_ws_d = bellman_ford_classic(_ws_adj, _ws_weight, "a")
assert _ws_d == {"a": 0, "b": -INF, "c": -INF, "d": -INF}, _ws_d
_ws_V = len(_ws_adj)
_ws_table = k_edge_distances(_ws_adj, _ws_weight, "a", _ws_V)
_ws_d_Vm1 = _ws_table[_ws_V - 1]
_ws_d_V = _ws_table[_ws_V]
_ws_witnesses = [v for v in _ws_adj if _ws_d_V[v] < _ws_d_Vm1[v]]
assert _ws_witnesses == ["b"], _ws_witnesses
assert _ws_d_Vm1["b"] == -5 and _ws_d_V["b"] == -7
_ws_reach = _reachable_from(_ws_adj, set(_ws_witnesses))
assert _ws_reach == {"b", "c", "d"}, _ws_reach
_ws_cycle_w = path_weight(_ws_weight, ["b", "c", "d", "b"])
assert _ws_cycle_w == -2
_ws_neginf = {v for v in _ws_adj if _ws_d[v] == -INF}
assert _ws_neginf == {"b", "c", "d"}, _ws_neginf
fig, _ws_axes = plt.subplots(1, 3, figsize=(11.0, 5.5),
gridspec_kw={"width_ratios": [1.05, 0.85, 1.25]})
fig.patch.set_facecolor(COL_WHITE)
_ws_draw_graph(_ws_axes[0], "a", _ws_witnesses, _ws_neginf)
_ws_draw_spread(_ws_axes[1], _ws_witnesses, _ws_reach)
_ws_draw_proof(_ws_axes[2], _ws_cycle_w)
fig.suptitle(
"Bellman-Ford: TANIK (V. turda düşer) → DFS erişilebilirlik → −∞ yayılımı · "
"her negatif çevrim bir tanık içerir",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
plt.tight_layout(rect=(0, 0, 1, 0.95))
plt.show()
```
## 7. Graf Çoğaltma {#sec-7-graf-cogaltma}
Modifiye Bellman-Ford'un fikri: bir düğümün **birçok sürümünü** yap; $v$'nin $k$. sürümü "$v$'ye en fazla $k$ kenarla ulaşmak" durumunu temsil etsin. Buna **graf çoğaltma (graph duplication)** denir.
> *"this is an idea called graph duplication."* — Ku, 30:51
$V+1$ seviye kur; seviye $k$'daki `v_k` düğümü, "$v$'ye en fazla $k$ kenarla ulaşmak". Kenarlar yalnızca **daha yüksek** seviyeye gider → çizge bir **DAG** olur (geriye kenar yok).
> *"if we connect edges from one level to only higher levels... then this graph is going to be a DAG."* — Ku, 33:14
DAG olduğu için DAG relaxation'ı (doğrusal) çağırabiliriz. Çoğaltılmış çizge $V$ kat büyür: $V \cdot (V+1)$ düğüm, $V \cdot (V+E)$ kenar — bu da DAG relaxation'ı $O(V \cdot (V+E)) = O(V \cdot E)$ yapar (Bölüm 2 indirgemesiyle).
@fig-graph-duplication örnek çizgeyi $V+1 = 5$ seviyeye açar (20 düğüm = $4 \times 5$): orijinal kenarlar seviye atlar, her düğüme $0$-ağırlıklı kalma kenarı eklenir, seviye-içi kenar olmadığından sonuç bir DAG'dır; vurgulu yol $a_0 \to b_1 \to c_2 \to d_3 \to b_4$ çevrimin "açılmış" hâlidir.
```{python}
#| label: fig-graph-duplication
#| fig-cap: "Graf çoğaltma: V+1 seviye + 0-kalma kenarları → DAG (Bellman-Ford'un kalbi) (L12 §7-8 İMZA). Tek panel, 5 yatay şerit k = 0..4 (V+1 = 5 seviye, solda seviye etiketi + ≤ k kenar). Her şeritte a, b, c, d kopyaları küçük daireler. Orijinal kenarlar SEVİYE ATLAYAN oklar: a0→b1 (−5) amber örnek vurgulu; çevrim kenarları b→c(−4), c→d(3), d→b(−1) bir seviye atlayarak çizilir (orijinalde çevrim, burada düz). Her düğüme dik kesikli 0-ağırlıklı KALMA kenarı (v,k) → (v,k+1) (δₖ ≤ δₖ₋₁). VURGU YOLU a0 → b1 → c2 → d3 → b4 amber kalın = çevrimin AÇILMIŞ hali. Sağ NOT kutusu (Ku §7-8): (v,k) = v'ye en fazla k kenarla (31:36); orijinal kenar → (u,k)→(v,k+1); kalma kenarı (v,k)→(v,k+1); seviye-içi kenar YOK → geri kenar YOK → bu çizge bir DAG (33:14); şimdi D16 dag_relaxation kara kutusu çağrılabilir; boyut V(V+1) düğüm → toplam O(V·E). Veri MOTORDAN: build_duplicated_dag → 4*5 = 20 düğüm; w2[(a0,b1)] = −5 (seviye atlar), w2[(a0,a1)] = 0 (kalma); adj2[a0] = [(a,1),(b,1)]."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-graph-duplication (L12 §7-8 İMZA): V+1 seviye çoğaltma → DAG.
# Veri MOTORDAN (build_bf_example / build_duplicated_dag). networkx YOK.
_GD_NODES = ["a", "b", "c", "d"]
_GD_COL_X = {"a": 0.0, "b": 2.0, "c": 4.0, "d": 4.0}
_GD_COL_DX = {"a": 0.0, "b": 0.0, "c": -0.45, "d": 0.45}
_GD_LEVEL_DY = 2.3
_GD_R = 0.26
_GD_N_LEVELS = 5
_GD_ORIG_EDGES = [("a", "b", -5), ("b", "c", -4), ("c", "d", 3), ("d", "b", -1)]
_GD_HILITE_PATH = [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("b", 4)]
_GD_HILITE_SET = set(zip(_GD_HILITE_PATH[:-1], _GD_HILITE_PATH[1:]))
def _gd_pos(node, k):
x = _GD_COL_X[node] + _GD_COL_DX[node]
y = -k * _GD_LEVEL_DY
return x, y
def _gd_draw_node(ax, node, k, on_path):
x, y = _gd_pos(node, k)
fc = COL_AMBER_100 if on_path else COL_BG
ec = COL_ACCENT if on_path else COL_PRIMARY
lw = 2.6 if on_path else 1.6
ax.add_patch(Circle((x, y), _GD_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=6))
tcol = COL_AMBER_700 if on_path else COL_TEXT
ax.text(x, y, node, ha="center", va="center", fontsize=11.5,
color=tcol, weight="bold", zorder=7)
ax.text(x + _GD_R + 0.02, y - _GD_R - 0.02, str(k), ha="left", va="top",
fontsize=7.5, color=COL_SLATE_500, weight="bold", zorder=7)
def _gd_draw_skip_edge(ax, u, v, k, wt, hot):
x0, y0 = _gd_pos(u, k)
x1, y1 = _gd_pos(v, k + 1)
if hot:
ecol, lw, alpha = COL_ACCENT, 3.0, 1.0
else:
ecol, lw, alpha = COL_PRIMARY, 1.7, 0.9
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=14,
color=ecol, linewidth=lw, alpha=alpha,
shrinkA=_GD_R * 74, shrinkB=_GD_R * 74, zorder=4,
connectionstyle="arc3,rad=0.0"))
mx, my = (x0 + x1) * 0.5, (y0 + y1) * 0.5
neg = wt < 0
bg = COL_AMBER_100 if hot else (COL_BG if not neg else COL_WHITE)
ec = COL_ACCENT if hot else (COL_AMBER_600 if neg else COL_SLATE_400)
tcol = COL_AMBER_700 if (hot or neg) else COL_TEXT
ax.add_patch(FancyBboxPatch(
(mx - 0.20, my - 0.135), 0.40, 0.27,
boxstyle="round,pad=0.01,rounding_size=0.06",
fc=bg, ec=ec, linewidth=1.9 if hot else 1.2, zorder=8))
ax.text(mx, my, str(wt), ha="center", va="center",
fontsize=8.5, color=tcol, weight="bold", zorder=9)
def _gd_draw_stay_edge(ax, node, k, hot):
x0, y0 = _gd_pos(node, k)
x1, y1 = _gd_pos(node, k + 1)
if hot:
ecol, lw = COL_ACCENT, 2.4
else:
ecol, lw = COL_SLATE_400, 1.3
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=11,
color=ecol, linewidth=lw, linestyle=(0, (3, 2.5)),
shrinkA=_GD_R * 74, shrinkB=_GD_R * 74, zorder=3))
mx, my = x0 + 0.13, (y0 + y1) * 0.5
ax.text(mx, my, "0", ha="left", va="center", fontsize=7,
color=COL_SLATE_500 if not hot else COL_AMBER_700,
style="italic", zorder=5)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_gd_adj, _gd_weight = build_bf_example()
_gd_adj2, _gd_weight2 = build_duplicated_dag(_gd_adj, _gd_weight)
_gd_V = len(_gd_adj)
assert _gd_V == 4
assert len(_gd_adj2) == 4 * 5 == 20, len(_gd_adj2)
assert _gd_weight2[(("a", 0), ("b", 1))] == -5
assert _gd_weight2[(("a", 0), ("a", 1))] == 0
assert _gd_adj2[("a", 0)] == [("a", 1), ("b", 1)], _gd_adj2[("a", 0)]
for _u, _v, _wt in _GD_ORIG_EDGES:
assert _gd_weight[(_u, _v)] == _wt
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
_gd_x_left = -1.55
_gd_x_right = 5.35
for _k in range(_GD_N_LEVELS):
_y = -_k * _GD_LEVEL_DY
if _k % 2 == 0:
ax.add_patch(FancyBboxPatch(
(_gd_x_left, _y - _GD_LEVEL_DY * 0.42), _gd_x_right - _gd_x_left,
_GD_LEVEL_DY * 0.84, boxstyle="round,pad=0.0,rounding_size=0.05",
fc=COL_BG, ec="none", alpha=0.55, zorder=0))
ax.text(_gd_x_left + 0.12, _y + 0.46, f"k = {_k}", ha="left", va="center",
fontsize=10.5, color=COL_PRIMARY, weight="bold", zorder=2)
ax.text(_gd_x_left + 0.12, _y + 0.14, "≤ %d kenar" % _k, ha="left",
va="center", fontsize=7.5, color=COL_SLATE_500, style="italic", zorder=2)
for _k in range(_GD_N_LEVELS - 1):
for _node in _GD_NODES:
_hot = ((_node, _k), (_node, _k + 1)) in _GD_HILITE_SET
_gd_draw_stay_edge(ax, _node, _k, _hot)
for _k in range(_GD_N_LEVELS - 1):
for _u, _v, _wt in _GD_ORIG_EDGES:
_hot = ((_u, _k), (_v, _k + 1)) in _GD_HILITE_SET
_gd_draw_skip_edge(ax, _u, _v, _k, _wt, _hot)
_gd_hl_nodes = set(_GD_HILITE_PATH)
for _k in range(_GD_N_LEVELS):
for _node in _GD_NODES:
_gd_draw_node(ax, _node, _k, (_node, _k) in _gd_hl_nodes)
ax.text(2.2, 0.92,
"vurgu: a → b → c → d → b (çevrimin AÇILMIŞ hali: orijinalde "
"çevrim, burada SEVİYE ATLAYAN düz yol)",
ha="center", va="center", fontsize=8.5, color=COL_AMBER_700,
weight="bold", zorder=10)
_gd_nx0, _gd_nbot, _gd_nw, _gd_nh = 5.75, -8.05, 4.7, 8.0
ax.add_patch(FancyBboxPatch(
(_gd_nx0, _gd_nbot), _gd_nw, _gd_nh,
boxstyle="round,pad=0.05,rounding_size=0.12",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=2))
_gd_tx = _gd_nx0 + 0.30
ax.text(_gd_tx, _gd_nbot + _gd_nh - 0.45, "GRAF ÇOĞALTMA (Ku L12 §7-8)",
ha="left", va="center", fontsize=10.5, color=COL_AMBER_700,
weight="bold", zorder=4)
_gd_lines = [
("• (v, k) düğümü = \"v'ye en fazla", COL_TEXT, 9.0, False),
(" k kenarla\" (Ku 31:36)", COL_SLATE_500, 8.5, True),
("", COL_TEXT, 5, False),
("• orijinal kenar u→v → seviye", COL_TEXT, 9.0, False),
(" atlar: (u,k) → (v,k+1)", COL_SLATE_500, 8.5, True),
("", COL_TEXT, 5, False),
("• KALMA kenarı (0): (v,k)→(v,k+1)", COL_TEXT, 9.0, False),
(" δₖ ≤ δₖ₋₁ korunur", COL_SLATE_500, 8.5, True),
("", COL_TEXT, 5, False),
("• seviye-içi kenar YOK", COL_AMBER_700, 9.5, False),
(" → geri kenar YOK", COL_AMBER_700, 9.5, False),
(" → bu çizge bir DAG (33:14)", COL_AMBER_700, 9.5, False),
("", COL_TEXT, 5, False),
("• şimdi D16 dag_relaxation", COL_PRIMARY, 9.0, False),
(" KARA KUTUSU çağrılabilir", COL_PRIMARY, 9.0, False),
]
_gd_ly = _gd_nbot + _gd_nh - 1.00
for _txt, _col, _fs, _ital in _gd_lines:
if _txt:
ax.text(_gd_tx, _gd_ly, _txt, ha="left", va="center", fontsize=_fs,
color=_col, weight="bold" if not _ital else "normal",
style="italic" if _ital else "normal", zorder=4)
_gd_ly -= 0.40
ax.plot([_gd_nx0 + 0.30, _gd_nx0 + _gd_nw - 0.30], [_gd_nbot + 0.62, _gd_nbot + 0.62],
color=COL_ACCENT, linewidth=1.0, alpha=0.6, zorder=3)
ax.text(_gd_nx0 + _gd_nw * 0.5, _gd_nbot + 0.33,
"boyut: V(V+1) düğüm → toplam O(V · E)",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=4)
fig.suptitle(
"Graf çoğaltma: V+1 seviye + 0-kalma kenarları → DAG (Bellman-Ford'un kalbi)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.set_xlim(_gd_x_left - 0.3, _gd_nx0 + _gd_nw + 0.3)
ax.set_ylim(-(_GD_N_LEVELS - 1) * _GD_LEVEL_DY - 1.1, 1.35)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 8. Graf Dönüşümü Örneği {#sec-8-graf-donusumu-ornegi}
Örnek: $a, b, c, d$ düğümlü yönlü çizge; $b \to c \to d \to b$ çevrimi ($-4 + 3 + (-1) = -2$, negatif). $V+1 = 5$ kopya (seviye 0-4). Kurallar:
- **Seviye içi kenar YOK** (çevrimleri kırar).
- Orijinal her $(u, v)$ kenarı için: seviye $k$'daki $u$'yu, seviye $k+1$'deki $v$'ye bağla (aynı ağırlık). Örn. `a_0 → b_1` (ağırlık $-5$).
- Her düğüm için **$0$-ağırlıklı "kalma" kenarı**: `v_k → v_{k+1}` ("bir kenar kullanmadan aynı yerde dur" — *en fazla* $k$ kenar koşulunu simüle eder).
> *"vertex Vk in level k represents reaching vertex V using at most k edges."* — Ku, 31:36
Böylece `a_0`'dan `b_3`'e bir yol = orijinal çizgede en fazla 3 kenarlı bir $a \to b$ yolu (örn. $a \to c \to d \to b$). Kenarlar daima seviye atladığından çizge çevrimsizdir.
::: {.callout-note title="Aynı çevrim, iki yerde"}
@fig-graph-duplication ve bu bölümün örneği **aynı çizgeyi** kullanır: motorun `build_bf_example` çevrimi $b \to c \to d \to b = (-4) + 3 + (-1) = -2$, Notion §8 anlatısıyla birebir aynı çevrim. Yani çoğaltma figüründeki vurgu yolu, buradaki dönüşüm örneğinin sayısal karşılığıdır.
:::
## 9. Bellman-Ford Algoritması {#sec-9-bellman-ford-algoritmasi}
Dört adım:
```python
def bellman_ford(graph, s):
# 1. V+1 seviyeli cogaltilmis DAG G' kur (seviye-atlamali + 0-agirlikli kalma kenarlari)
G_prime = build_duplicated_dag(graph) # O(V(V+E))
# 2. DAG relaxation ile s_0'dan tum v_k'ya delta hesapla
delta = dag_relaxation(G_prime, source=(s, 0)) # O(V(V+E))
# 3. Sonlu mesafeleri ata: d(s,v) = delta(s_0, v_{V-1})
d = {v: delta[(v, V - 1)] for v in graph.vertices}
# 4. Taniklari bul, eristikleri -inf isaretle
for v in graph.vertices:
if delta[(v, V)] < delta[(v, V - 1)]: # tanik kosulu
for u in reachable_from(graph, v): # O(E) her tanik
d[u] = float('-inf')
return d
```
Üçüncü adımda $d(s, v) = \delta(s_0, v_{V-1})$ ($V-1$ kenarlı mesafe) atanır; bu, sonlu mesafeler için doğrudur.
@fig-bf-algorithm bu dört adımı dikey bir akışta toplar: (1) $G'$ kur (çoğaltma), (2) DAG relaxation (Ders 16 kara kutusu), (3) sonlu ata, (4) tanık + $-\infty$ yay; toplam $O(V \cdot E)$. Yan notta motorun iki bağımsız sürümü (`via_dag` ve `classic`) örnek çizgede ve 100 rastgele çizgede birebir aynı sonucu verir.
```{python}
#| label: fig-bf-algorithm
#| fig-cap: "Bellman-Ford = graf çoğaltma + Ders 16 DAG relaxation kara kutusu → O(V·E) (L12 §9 İMZA). Dikey akış, dört adım kutusu (numara + başlık + açıklama + süre rozeti). (1) G′ KUR — graf çoğaltma: V+1 seviye, (u,k)→(v,k+1) kenar + (v,k)→(v,k+1) 0-kalma kenarı [O(V·(V+E))]; sağında V+1 seviye katman ikonu. (2) DAG RELAXATION — s₀'dan tüm vₖ'ye Ders 16 kara kutusu (topolojik sıra = seviye) [O(V·(V+E))]; sağında 'Ders 16 kara kutu' rozeti. (3) SONLU ATA — d(v) = δ(s₀, v_{V−1}); en kısa yollar BASİT → ≤ V−1 kenar [O(V)]. (4) TANIK + −∞ YAY — δ(v_V) < δ(v_{V−1}) → tanık; erişilenlere −∞ (negatif çevrim) [O(V·E)]; sağında örnek çizge a→b(−5) + çevrim b→c→d→b = −2, çevrimden erişilen b,c,d düğümleri −∞ boyalı. En altta TOPLAM = O(V·E) (Ku 54:30). Yan not: klasik BF bu çoğaltmayı YAPMAZ — V−1 tur kenar gevşetir, V. turda hâlâ gevşeyen = tanık (Egzersiz 4); motor iki sürümü de çalıştırdı, via_dag == classic == {a:0, b,c,d:−∞} (örnek + 100 rastgele çizgede birebir). Veri MOTORDAN: bellman_ford_via_dag == bellman_ford_classic; tanık δ_V(b)=−7 < δ_{V−1}(b)=−5."
#| fig-width: 10.4
#| fig-height: 7.0
# fig-bf-algorithm (L12 §9 İMZA): dört adımlık dikey akış + iki sürüm eşitliği.
# Veri MOTORDAN (build_bf_example / bellman_ford_via_dag / bellman_ford_classic /
# k_edge_distances). networkx YOK — elle koordinat.
_BA_POS = {"a": (0.0, 1.0), "b": (1.0, 1.0), "c": (2.0, 1.6), "d": (2.0, 0.4)}
_BA_EDGES = [("a", "b", -5, False), ("b", "c", -4, True),
("c", "d", 3, True), ("d", "b", -1, True)]
_BA_R = 0.22
def _ba_draw_example_graph(ax, ox, oy, neg_nodes):
def P(v):
x, y = _BA_POS[v]
return (ox + x, oy + y)
for u, v, wt, cyc in _BA_EDGES:
ux, uy = P(u)
vx, vy = P(v)
ecol = COL_ACCENT if cyc else COL_PRIMARY
cstyle = "arc3,rad=-0.28" if (u, v) == ("d", "b") else "arc3,rad=0.0"
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=12,
color=ecol, linewidth=2.2 if cyc else 1.8,
shrinkA=_BA_R * 70, shrinkB=_BA_R * 70,
connectionstyle=cstyle, zorder=2))
if (u, v) == ("d", "b"):
mx, my = (ux + vx) * 0.5 - 0.42, (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.135, my - 0.115), 0.27, 0.23,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100 if cyc else COL_WHITE,
ec=COL_ACCENT if cyc else COL_SLATE_400,
linewidth=1.5 if cyc else 1.0, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center", fontsize=8,
color=tcol, weight="bold", zorder=7)
for v, (x, y) in _BA_POS.items():
is_src = (v == "a")
is_neg = (v in neg_nodes)
if is_src:
fc, ec, tc, lw = COL_BG, COL_PRIMARY, COL_TEXT, 2.0
elif is_neg:
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.8
px, py = P(v)
ax.add_patch(Circle((px, py), _BA_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(px, py, v, ha="center", va="center", fontsize=10,
color=tc, weight="bold", zorder=6)
if is_neg:
ax.text(px, py + _BA_R + 0.16, "−∞", ha="center", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6)
ax_, ay_ = P("a")
ax.text(ax_, ay_ - _BA_R - 0.16, "kaynak", ha="center", va="center",
fontsize=7, color=COL_SLATE_500, weight="bold", zorder=6)
ax.text(ox + 1.5, oy + 2.18, "çevrim b→c→d→b = −2 (negatif)", ha="center",
va="center", fontsize=7.5, color=COL_AMBER_700, style="italic", zorder=6)
ax.text(ox + 1.5, oy - 0.18, "çevrimden erişilen b, c, d → δ = −∞",
ha="center", va="center", fontsize=7.5, color=COL_AMBER_700,
style="italic", zorder=6)
def _ba_draw_layers_icon(ax, ox, oy, n_levels=5):
bar_w, bar_h, gap = 1.1, 0.13, 0.115
for k in range(n_levels):
y = oy - k * (bar_h + gap)
is_top = (k == 0)
ax.add_patch(FancyBboxPatch(
(ox, y), bar_w, bar_h, boxstyle="round,pad=0.005,rounding_size=0.03",
fc=COL_AMBER_100 if is_top else COL_BG,
ec=COL_ACCENT if is_top else COL_SLATE_400,
linewidth=1.6 if is_top else 1.1, zorder=4))
ax.text(ox + bar_w + 0.10, y + bar_h * 0.5, f"k={k}",
ha="left", va="center", fontsize=6.5, color=COL_SLATE_500, zorder=4)
ax.text(ox + bar_w * 0.5, oy + bar_h + 0.13, "V+1 seviye", ha="center",
va="center", fontsize=7, color=COL_PRIMARY, weight="bold", zorder=4)
ax.text(ox + bar_w * 0.5, oy - n_levels * (bar_h + gap) + 0.02, "(çoğaltma)",
ha="center", va="center", fontsize=6.5, color=COL_SLATE_500,
style="italic", zorder=4)
def _ba_draw_ders16_badge(ax, ox, oy):
w, h = 1.7, 0.74
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.13, "DAG RELAX", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(ox + w * 0.5, oy - 0.15, "Ders 16 kara kutu", ha="center",
va="center", fontsize=7, color=COL_AMBER_700, style="italic", zorder=5)
def _ba_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 = 1.62, 0.40
bx = x + w - bw - 0.18
bcy = y + h - 0.34
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=9.5, color=COL_PRIMARY, weight="bold",
family="monospace", zorder=6)
tx = x + 0.86
ax.text(tx, y + h - 0.34, title, ha="left", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=5)
ax.text(tx, y + 0.32, body, ha="left", va="center",
fontsize=8.2, color=COL_SLATE_500, zorder=5)
return (ncx, ncy), (x + w, y + h * 0.5)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_ba_adj, _ba_weight = build_bf_example()
_ba_d_via = bellman_ford_via_dag(_ba_adj, _ba_weight, "a")
_ba_d_classic = bellman_ford_classic(_ba_adj, _ba_weight, "a")
assert _ba_d_via == _ba_d_classic, (_ba_d_via, _ba_d_classic)
assert _ba_d_via == {"a": 0, "b": -INF, "c": -INF, "d": -INF}, _ba_d_via
_ba_V = len(_ba_adj)
_ba_tab = k_edge_distances(_ba_adj, _ba_weight, "a", _ba_V)
assert _ba_tab[_ba_V - 1]["b"] == -5 and _ba_tab[_ba_V]["b"] == -7
_ba_neg_nodes = {v for v in _ba_adj if _ba_d_via[v] == -INF}
assert _ba_neg_nodes == {"b", "c", "d"}, _ba_neg_nodes
fig, ax = plt.subplots(figsize=(10.4, 7.0))
fig.patch.set_facecolor(COL_WHITE)
_ba_bx0 = 0.0
_ba_box_w, _ba_box_h = 6.2, 1.12
_ba_v_gap = 0.58
_ba_top_y = 5.2
_ba_steps = [
(1, "G′ KUR — graf çoğaltma",
"V+1 seviye · (u,k)→(v,k+1) kenar + (v,k)→(v,k+1) 0-kalma kenarı",
"O(V·(V+E))", False),
(2, "DAG RELAXATION",
"s₀'dan tüm vₖ'ye Ders 16 kara kutusu (topolojik sıra = seviye)",
"O(V·(V+E))", True),
(3, "SONLU ATA",
"d(v) = δ(s₀, v_{V−1}) · en kısa yollar BASİT → ≤ V−1 kenar",
"O(V)", False),
(4, "TANIK + −∞ YAY",
"δ(v_V) < δ(v_{V−1}) → tanık · erişilenlere −∞ (negatif çevrim)",
"O(V·E)", True),
]
_ba_box_tops = []
for _idx, (_num, _title, _body, _badge, _accent) in enumerate(_ba_steps):
_y = _ba_top_y - _idx * (_ba_box_h + _ba_v_gap)
_ba_draw_step_box(ax, _ba_bx0, _y, _ba_box_w, _ba_box_h, _num, _title,
_body, _badge, accent=_accent)
_ba_box_tops.append((_ba_bx0 + _ba_box_w * 0.5, _y + _ba_box_h))
_ba_arrow_x = _ba_bx0 + 0.42
for _idx in range(len(_ba_steps) - 1):
_y_bot = _ba_top_y - _idx * (_ba_box_h + _ba_v_gap)
_y_next_top = _ba_top_y - (_idx + 1) * (_ba_box_h + _ba_v_gap) + _ba_box_h
ax.add_patch(FancyArrowPatch(
(_ba_arrow_x, _y_bot), (_ba_arrow_x, _y_next_top),
arrowstyle="-|>", mutation_scale=15, color=COL_AMBER_700,
linewidth=2.2, zorder=2))
_ba_tot_y = _ba_top_y - len(_ba_steps) * (_ba_box_h + _ba_v_gap)
ax.add_patch(FancyArrowPatch(
(_ba_arrow_x, _ba_tot_y + _ba_box_h + _ba_v_gap), (_ba_arrow_x, _ba_tot_y + 0.50),
arrowstyle="-|>", mutation_scale=15, color=COL_AMBER_700, linewidth=2.2, zorder=2))
ax.add_patch(FancyBboxPatch(
(_ba_bx0, _ba_tot_y), _ba_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(_ba_bx0 + 0.30, _ba_tot_y + 0.31, "TOPLAM", ha="left", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(_ba_bx0 + _ba_box_w - 0.30, _ba_tot_y + 0.31, "O(V·E)", ha="right",
va="center", fontsize=13, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=5)
ax.text(_ba_bx0 + _ba_box_w * 0.5, _ba_tot_y + 0.31, "(Ku 54:30)", ha="center",
va="center", fontsize=7.5, color=COL_AMBER_700, style="italic", zorder=5)
_ba_right_x = _ba_bx0 + _ba_box_w + 0.55
_ba_draw_layers_icon(ax, _ba_right_x, _ba_box_tops[0][1] - 0.12, n_levels=_ba_V + 1)
_ba_y2 = _ba_top_y - 1 * (_ba_box_h + _ba_v_gap) + _ba_box_h * 0.5
_ba_draw_ders16_badge(ax, _ba_right_x, _ba_y2)
_ba_y4_top = _ba_top_y - 3 * (_ba_box_h + _ba_v_gap) + _ba_box_h
_ba_draw_example_graph(ax, _ba_right_x - 0.15, _ba_y4_top - 2.35, _ba_neg_nodes)
_ba_note_y = _ba_tot_y - 0.55
ax.text(_ba_bx0, _ba_note_y,
"Yan not: klasik Bellman-Ford bu çoğaltmayı YAPMAZ — V−1 tur boyunca "
"TÜM kenarları gevşetir, V. turda hâlâ",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold", zorder=5)
ax.text(_ba_bx0, _ba_note_y - 0.32,
"gevşeyen düğüm = tanık (Egzersiz 4). Motor iki sürümü de çalıştırdı: "
"via_dag == classic == {a:0, b,c,d:−∞}",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, zorder=5)
ax.text(_ba_bx0, _ba_note_y - 0.62,
"BİREBİR — örnek çizgede ve 100 rastgele çizgede de (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(
"Bellman-Ford = graf çoğaltma + Ders 16 DAG relaxation kara kutusu → O(V·E)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(_ba_bx0 + _ba_box_w * 0.5, _ba_top_y + _ba_box_h + 0.30,
"genel SSSP: negatif kenar + negatif çevrim (−∞ tanığı) dahil · Ku L12 §9",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.4, _ba_right_x + 2.7)
ax.set_ylim(_ba_note_y - 0.95, _ba_top_y + _ba_box_h + 0.65)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 10. Doğruluk ve Çalışma Süresi {#sec-10-dogruluk-ve-calisma-suresi}
**Doğruluk ($k$ üzerinden tümevarım).** İddia: $\delta(s_0,$ `v_k` $) = \delta_k(s, v)$. Temel ($k = 0$): yalnız $s_0$ erişilir (0), gerisi $\infty$. Adım: `v_k`'ya en kısa yol, bir önceki seviyedeki bir komşudan gelir; $G'$'nin komşulukları orijinal komşuluklar + "kalma" kenarıdır → minimum, tam olarak $\delta_k$ tanımını verir. Böylece sonlu mesafeler doğru atanır; tanık koşulu da $-\infty$'ları yakalar.
**Çalışma süresi.** $G'$ kurma $O(V \cdot (V+E))$ + DAG relaxation aynı + her tanık için erişilebilirlik $O(E)$, en fazla $V$ tanık → $O(V \cdot E)$. Toplam $O(V \cdot E)$.
> *"this thing takes order V times E work."* — Ku, 54:30
(Not: orijinal Bellman-Ford bu çoğaltmayı *yapmaz* — $V$ tur kenar gevşetir; recitation'da $O(V)$ yer kullanan optimizasyon gösterilir.)
@fig-sssp-landscape bu dersi SSSP algoritma manzarasına yerleştirir: BFS (ağırlıksız), DAG relaxation (Ders 16, DAG), **Bellman-Ford** (bu ders, herhangi çizge $O(V \cdot E)$, amber vurgulu), Dijkstra (Ders 19, $\geq 0$); altında Bellman-Ford'un indirgeme şeridi (çoğalt → DAG → çözülmüş kara kutu) ve motorun tutarlılık tanığı (`bellman_ford_classic == dag_sssp`).
```{python}
#| label: fig-sssp-landscape
#| fig-cap: "SSSP algoritma manzarası: Bellman-Ford en geneli — herhangi çizge, negatif çevrim tespiti (O(V·E)) (L12 SENTEZ). Dört satırlık karşılaştırma panosu (algoritma | kabul ettiği çizge/kısıt | çalışma süresi | ders): (1) BFS — ağırlıksız çizge — O(V+E) [Ders 13]; (2) DAG relaxation — DAG + her ağırlık — O(V+E) [Ders 16]; (3) BELLMAN-FORD — HERHANGİ çizge, negatif çevrim TESPİT + −∞ — O(V·E) [BU DERS, amber vurgulu]; (4) Dijkstra — ağırlık ≥ 0 — O(V log V + E) [Ders 19]. Altında BF indirgeme şeridi: çoğalt (V+1 seviye) → DAG'a indirge (0-kalma kenarları) → çözülmüş kara kutu DAG relaxation — BF yeni algoritma icat etmez, problemi çözülmüş bir DAG SSSP'sine İNDİRGER (OMSCS reduction refleksi). Alt kutu: BF = en GENEL SSSP çözücü, negatif çevrimi bile tespit eder (δ = −∞); bedeli V çarpanı O(V·E); çizge kısıtlıysa DAG (O(V+E)) veya Dijkstra (≥0) daha hızlı. Tutarlılık tanığı (motordan): bellman_ford_classic == dag_sssp (D16 DAG, kaynak e) → δ = {e:0, f:3, g:5, h:6, d:3, c:8}. Veri MOTORDAN: BF classic == via_dag == {a:0, b:−∞, c:−∞, d:−∞}; çoğaltılmış DAG V+1 seviye = 20 düğüm."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-sssp-landscape (L12 SENTEZ): SSSP manzarası + BF indirgeme tutarlılık tanığı.
# Veri MOTORDAN (build_bf_example / bellman_ford_classic / bellman_ford_via_dag /
# build_weighted_dag_example / dag_sssp / build_duplicated_dag / path_weight).
_LS_ROWS = [
{"name": "BFS", "graph": "ağırlıksız çizge",
"icon": "○", "time": "O(V + E)", "tag": "Ders 13", "is_bf": False},
{"name": "DAG relaxation", "graph": "DAG + her ağırlık",
"icon": "▷", "time": "O(V + E)", "tag": "Ders 16", "is_bf": False},
{"name": "BELLMAN-FORD", "graph": "HERHANGİ çizge — negatif çevrim TESPİT + −∞",
"icon": "★", "time": "O(V · E)", "tag": "BU DERS", "is_bf": True},
{"name": "Dijkstra", "graph": "ağırlık ≥ 0",
"icon": "◆", "time": "O(V log V + E)", "tag": "Ders 19", "is_bf": False},
]
_LS_REDUCE = [
"çoğalt\n(V+1 seviye)",
"DAG'a indirge\n(0-kalma kenarları)",
"çözülmüş kara kutu\nDAG relaxation",
]
def _ls_draw_row(ax, row, x0, y, row_w, row_h):
is_bf = row["is_bf"]
if is_bf:
fc, ec, lw = COL_AMBER_100, COL_ACCENT, 2.8
name_col = COL_AMBER_700
else:
fc, ec, lw = COL_BG, COL_PRIMARY, 1.7
name_col = COL_TEXT
ax.add_patch(FancyBboxPatch(
(x0, y), row_w, row_h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=fc, ec=ec, linewidth=lw, zorder=3))
cy = y + row_h * 0.5
icon_x = x0 + 0.50
icon_col = COL_ACCENT if is_bf else COL_SLATE_500
ax.text(icon_x, cy, row["icon"], ha="center", va="center",
fontsize=15 if is_bf else 13, color=icon_col, weight="bold", zorder=5)
ax.text(x0 + 1.05, cy, row["name"], ha="left", va="center",
fontsize=12 if is_bf else 11, color=name_col, weight="bold", zorder=5)
mid_x = x0 + row_w * 0.485
ax.text(mid_x, cy, row["graph"], ha="center", va="center",
fontsize=9, color=COL_TEXT if is_bf else COL_SLATE_500,
zorder=5, style="normal" if is_bf else "italic")
time_x = x0 + row_w - 2.35
ax.add_patch(FancyBboxPatch(
(time_x, cy - 0.27), 1.55, 0.54, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_WHITE if not is_bf else COL_AMBER_300,
ec=COL_ACCENT if is_bf else COL_SLATE_400,
linewidth=2.0 if is_bf else 1.3, zorder=4))
ax.text(time_x + 0.775, cy, row["time"], ha="center", va="center",
fontsize=10 if is_bf else 9.5,
color=COL_AMBER_700 if is_bf else COL_TEXT,
weight="bold", family="monospace", zorder=5)
ax.text(x0 + row_w - 0.18, cy, row["tag"], ha="right", va="center",
fontsize=8, color=COL_AMBER_700 if is_bf else COL_SLATE_400,
weight="bold" if is_bf else "normal", zorder=5)
def _ls_draw_reduce(ax, x0, y, total_w):
n = len(_LS_REDUCE)
box_w = 2.55
gap = (total_w - n * box_w) / (n - 1) if n > 1 else 0.0
for i, label in enumerate(_LS_REDUCE):
bx = x0 + i * (box_w + gap)
last = (i == n - 1)
if last:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.4
else:
fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_SLATE_500, 1.5
ax.add_patch(FancyBboxPatch(
(bx, y), box_w, 0.70, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=fc, ec=ec, linewidth=lw, zorder=3))
ccx = bx + box_w * 0.5
ax.text(ccx, y + 0.35, label, ha="center", va="center",
fontsize=8, color=tcol, weight="bold", zorder=5)
if i < n - 1:
ax.add_patch(FancyArrowPatch(
(bx + box_w, y + 0.35), (bx + box_w + gap, y + 0.35),
arrowstyle="-|>", mutation_scale=13, color=COL_AMBER_600,
linewidth=1.8, zorder=4))
ax.text(x0, y + 0.92,
"Bellman-Ford NASIL? — yeni algoritma icat etmez; problemi ÇÖZÜLMÜŞ bir "
"DAG SSSP'sine İNDİRGER:",
ha="left", va="center", fontsize=8.5, color=COL_AMBER_700,
weight="bold", zorder=5)
# ---- motor verisi + ASSERT (figür yalnız doğrulanmış iddiaları gösterir) ----
_ls_adj, _ls_weight = build_bf_example()
_ls_d_classic = bellman_ford_classic(_ls_adj, _ls_weight, "a")
_ls_d_viadag = bellman_ford_via_dag(_ls_adj, _ls_weight, "a")
assert _ls_d_classic == _ls_d_viadag, (_ls_d_classic, _ls_d_viadag)
assert _ls_d_classic == {"a": 0, "b": -INF, "c": -INF, "d": -INF}, _ls_d_classic
assert path_weight(_ls_weight, ["b", "c", "d", "b"]) == -2
_ls_dadj, _ls_dweight, _ls_dtopo = build_weighted_dag_example()
_ls_bf_on_dag = bellman_ford_classic(_ls_dadj, _ls_dweight, "e")
_ls_dag_ref = dag_sssp(_ls_dadj, _ls_dweight, "e")
assert _ls_bf_on_dag == _ls_dag_ref, (_ls_bf_on_dag, _ls_dag_ref)
assert _ls_dag_ref == {"a": INF, "b": INF, "e": 0, "f": 3, "g": 5,
"h": 6, "d": 3, "c": 8}, _ls_dag_ref
_ls_adj2, _ls_w2 = build_duplicated_dag(_ls_adj, _ls_weight)
assert len(_ls_adj2) == len(_ls_adj) * (len(_ls_adj) + 1)
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
_ls_x0 = 0.30
_ls_row_w = 10.4
_ls_row_h = 0.78
_ls_gap_v = 0.26
_ls_y_top = 5.10
_ls_head_y = _ls_y_top + _ls_row_h + 0.26
ax.text(_ls_x0 + 0.80, _ls_head_y, "algoritma", ha="left", va="center",
fontsize=9, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(_ls_x0 + _ls_row_w * 0.485, _ls_head_y, "kabul ettiği çizge (kısıt)",
ha="center", va="center", fontsize=9, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(_ls_x0 + _ls_row_w - 2.35 + 0.775, _ls_head_y, "çalışma süresi",
ha="center", va="center", fontsize=9, color=COL_PRIMARY, weight="bold", zorder=5)
_ls_bf_y = None
_ls_last_row_y = None
for _r, _row in enumerate(_LS_ROWS):
_y = _ls_y_top - _r * (_ls_row_h + _ls_gap_v)
_ls_draw_row(ax, _row, _ls_x0, _y, _ls_row_w, _ls_row_h)
if _row["is_bf"]:
_ls_bf_y = _y
_ls_last_row_y = _y
_ls_strip_x0 = _ls_x0 + 0.30
_ls_strip_w = _ls_row_w - 0.60
_ls_strip_y = _ls_last_row_y - 1.85
_ls_draw_reduce(ax, _ls_strip_x0, _ls_strip_y, _ls_strip_w)
_ls_bf_cx = _ls_x0 + 1.6
ax.add_patch(FancyArrowPatch(
(_ls_bf_cx, _ls_bf_y), (_ls_bf_cx, _ls_strip_y + 1.10),
arrowstyle="-|>", mutation_scale=13, color=COL_AMBER_600,
linewidth=1.6, zorder=2, linestyle="--"))
_ls_box_y = _ls_strip_y - 1.30
ax.add_patch(FancyBboxPatch(
(_ls_x0, _ls_box_y), _ls_row_w, 0.82, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
ax.text(_ls_x0 + _ls_row_w * 0.5, _ls_box_y + 0.54,
"Bellman-Ford = en GENEL SSSP çözücü — negatif çevrimi bile tespit eder "
"(δ = −∞ döndürür)",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(_ls_x0 + _ls_row_w * 0.5, _ls_box_y + 0.20,
"bedeli V çarpanı: O(V · E). Çizge daha kısıtlıysa (DAG → O(V+E), "
"ağırlık ≥ 0 → Dijkstra) DAHA HIZLI yöntem seç.",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500,
style="italic", zorder=4)
ax.text(_ls_x0, _ls_box_y - 0.42,
"tutarlılık tanığı (motordan): aynı çoğaltma fikriyle "
"bellman_ford_classic == dag_sssp (D16 DAG, kaynak e) → δ = "
"{e:0, f:3, g:5, h:6, d:3, c:8}",
ha="left", va="center", fontsize=8.2, color=COL_TEXT,
family="monospace", zorder=5)
fig.suptitle(
"SSSP algoritma manzarası: Bellman-Ford en geneli — herhangi çizge, negatif çevrim tespiti (O(V·E))",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
ax.set_xlim(-0.2, _ls_row_w + 0.7)
ax.set_ylim(_ls_box_y - 0.80, _ls_head_y + 0.45)
ax.set_aspect("auto")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d18}
1. **Hedef**: genel çizgede SSSP; $\infty$ (erişilemez), $-\infty$ (negatif çevrimden), sonlu; $O(V \cdot E)$.
2. **Basit yol**: $\delta$ sonlu → tekrarsız yol → en fazla **$V-1$ kenar**.
3. **k-kenar mesafesi** $\delta_k$: en fazla $k$ kenarlı en kısa yol; $k = V-1$ yeter (sonlu için).
4. **Tanık**: $\delta_V < \delta_{V-1}$ → negatif çevrim; $\delta = -\infty \Leftrightarrow$ tanıktan erişilir.
5. **Her negatif çevrim bir tanık içerir** (çevrim üzerinde toplam + üçgen eşitsizliği + $w(C) < 0$).
6. **Graf çoğaltma**: $V+1$ seviye, seviye-atlamalı kenarlar + $0$-ağırlıklı kalma → DAG.
7. **Algoritma**: $G'$ kur → DAG relaxation → $\delta(s_0, v_{V-1})$ ata → tanıktan $-\infty$ yay; $O(V \cdot E)$.
::: {.callout-important title="Tek Bir Cümle"}
Bellman-Ford, "sonlu en kısa yol $V-1$ kenardan uzun olamaz" gerçeğini kullanır: çizgeyi $V+1$ seviyeye çoğaltıp DAG yapar, DAG relaxation çağırır, $V$ kenarda hâlâ kısalan tanıkları bulup onlardan $-\infty$ yayar — hepsi $O(V \cdot E)$.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d18}
::: {.callout-note collapse="true" title="Soru 1: Neden “δ sonluysa en fazla V−1 kenarlı yolları kontrol etmek yeter”? Bu Bellman-Ford'u nasıl sonlandırır?"}
**Cevap:**
$\delta(s, v)$ sonluysa, en kısa yolların içindeki her çevrimin ağırlığı $\geq 0$ olmalıdır (negatif olsaydı tekrar dolaşıp $-\infty$ yapardık). Sıfır/pozitif çevrimleri atarak **basit** (düğüm-tekrarsız) bir en kısa yol elde ederiz; basit yol en fazla $V$ düğüm → **$V-1$ kenar** içerir. Böylece sonsuz sayıda yol yerine, kenar sayısını $V-1$ ile sınırlı **sonlu** bir kümeye bakarız — algoritma sonlanır (her $k = 0 \ldots V-1$ için adım adım mesafe).
:::
::: {.callout-note collapse="true" title="Soru 2: “Tanık (witness)” nedir ve −∞ düğümleriyle ilişkisi nedir?"}
**Cevap:**
Tanık, **$V$ kenarlı** en kısa mesafesi **$(V-1)$ kenarlı** mesafesinden kesinlikle küçük olan bir düğümdür. Bu, $V$ kenarlık daha kısa bir yolun var olması demektir; ama $V$ kenar $> V-1$ düğüm olduğundan o yol bir düğümü tekrar eder → içinde bir negatif ağırlıklı çevrim vardır. İlişki: $\delta(s, v) = -\infty \Leftrightarrow v$ bir tanıktan erişilebilir. Çünkü her negatif çevrim bir tanık içerir (kanıtlandı) ve negatif çevrimden erişilen her düğüm sınırsızca kısalan bir yola sahiptir. Algoritma tüm tanıkları bulur, onlardan erişilenleri $-\infty$ yapar.
:::
::: {.callout-note collapse="true" title="Soru 3: Graf çoğaltma çizgeyi neden bir DAG'a çevirir, ve bu neden işe yarar?"}
**Cevap:**
Çoğaltmada her düğümün $V+1$ sürümü (her seviye için biri) yapılır ve **kenarlar yalnız daha yüksek seviyeye** gider (`v_k → v_{k+1}` seviye atlamalı ve "kalma" `v_k → v_{k+1}`). Geriye kenar olmadığından çevrim oluşamaz → **DAG**. İşe yarar çünkü DAG relaxation'ı (Ders 16, doğrusal $O(V+E)$) bu çoğaltılmış çizgeye uygulayabiliriz; çizge $V$ kat büyüdüğünden $O(V \cdot (V+E)) = O(V \cdot E)$ elde ederiz. Yani çevrimli problemi, çözmeyi bildiğimiz çevrimsiz bir probleme **indirgemiş** oluruz.
:::
::: {.callout-note collapse="true" title="Soru 4: Neden Bellman-Ford yönsüz çizgelerde “ilginç değil”?"}
**Cevap:**
Yönsüz bir çizgede tek bir negatif ağırlıklı kenar bile bir negatif çevrim üretir: o kenar üzerinde ileri-geri gidersek (uzunluk-2 çevrim) toplam ağırlık negatiftir, sonsuza dek tekrarlanabilir. Yani yönsüzde "negatif çevrim var mı?" sorusu "negatif kenar var mı?" ile aynıdır ($O(E)$ basit kontrol) ve $s$'nin bağlı bileşeninde negatif kenar varsa her şey $-\infty$ olur. Bu yüzden problem yalnızca **yönlü** çizgelerde anlamlı; ders yönlü hâle odaklanır.
:::
## Egzersizler {#sec-egzersizler-d18}
**Egzersiz 1.** Küçük bir negatif-çevrimli yönlü çizgede, $k = 0 \ldots V$ için $\delta_k(s, v)$ tablosunu elle doldur; hangi düğümlerin tanık olduğunu ($\delta_V < \delta_{V-1}$) işaretle.
**Egzersiz 2.** Bir çizge için çoğaltılmış DAG $G'$'yi ($V+1$ seviye, kalma kenarları) çiz; `a_0`'dan bir `v_{V-1}`'e bir yolun, orijinalde en fazla $V-1$ kenarlı bir yola karşılık geldiğini doğrula.
**Egzersiz 3.** "Her negatif çevrim bir tanık içerir" kanıtını, çevrim üzerinde toplama ve üçgen eşitsizliği adımlarını yazarak yeniden üret.
**Egzersiz 4.** Bellman-Ford'u Python'da yaz (çoğaltma olmadan, klasik $V$-tur kenar gevşetme); negatif çevrim tespitini $V$. turda bir gevşetme olup olmadığına bakarak ekle.
**Egzersiz 5.** $O(V \cdot (V+E)) \to O(V \cdot E)$ indirgemesini bir çizgede uygula: BFS ile erişilemeyenleri at, kalan çizgede $V = O(E)$ olduğunu doğrula.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d18}
::: {.callout-warning title="Sonraki: Ders 19 (L13) — Dijkstra"}
**Ders 19 (L13): Dijkstra** — Jason Ku ile, ağırlıklar **negatif değilse** çok daha hızlı bir algoritma: Dijkstra. Negatif çevrim derdi olmadığından, açgözlü (greedy) bir öncelik kuyruğuyla her düğümü bir kez "kesinleştirir" → $O(V \log V + E)$, doğrusala yakın. Bellman-Ford'un $V \cdot E$'sinden hızlı; çoğu gerçek problem (yol ağı) için tercih edilen.
**Ders 19 Öncesi Yapılacak:**
- Bu dersin egzersizlerini, özellikle Egzersiz 1 ($\delta_k$ tablosu) ve 4 (klasik Bellman-Ford) çöz.
- "Simple yol $\leq V-1$ kenar" ve "tanık" tanımlarını ezberden anlat.
- Ana cümleyi tekrar oku: *"Sonlu en kısa yol $V-1$ kenardan uzun olamaz; çoğalt, DAG yap, gevşet, tanıkları $-\infty$ yap."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d18}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **Bellman-Ford hedefi** | Genel çizgede SSSP; $\infty$ / $-\infty$ / sonlu; $O(V \cdot E)$ | Böl. 1 |
| **Basit en kısa yol** | $\delta$ sonlu → tekrarsız → $\leq V-1$ kenar | Böl. 3 |
| **k-kenar mesafesi $\delta_k$** | En fazla $k$ kenarlı en kısa yol; $k = V-1$ yeter | Böl. 4 |
| **Tanık (witness)** | $\delta_V < \delta_{V-1}$ → negatif çevrim kanıtı | Böl. 5-6 |
| **$-\infty$ kuralı** | $\delta = -\infty \Leftrightarrow$ bir tanıktan erişilebilir | Böl. 5 |
| **Graf çoğaltma** | $V+1$ seviye, seviye-atlamalı + kalma kenarı → DAG | Böl. 7-8 |
| **Algoritma** | $G'$ kur → DAG relaxation → $\delta$ ($s_0$ → $V-1$ seviyesi) → tanık $-\infty$ | Böl. 9 |
| **Çalışma süresi** | $O(V \cdot E)$ (DAG relaxation $V$ kat büyük çizgede) | Böl. 10 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d18}
::: {.callout-tip title="6 köprü"}
Bu ders, "DAG kısıtını kaldıran en genel SSSP" fikrini kurar ve graf çoğaltma ile çevrimli/negatif problemi çözülmüş bir DAG'a indirger — köprülerin özeti:
1. **Bellman-Ford** → distance-vector yönlendirme (RIP), ağ topoloji keşfi, gecikme tabanlı yol.
2. **Negatif çevrim tespiti** → arbitraj (döviz çevrim grafı kâr döngüsü), kısıt tutarsızlığı (fark kısıtları).
3. **Graf çoğaltma** → durum-augmentasyonu: zaman-genişletilmiş çizge, yakıt/mod katmanları, takvim çakışması.
4. **k-kenar mesafesi** → sınırlı-atlama en kısa yol (en fazla $k$ aktarma), kademeli yayılım.
5. **DAG'a indirgeme** → "zor problemi kolay kara kutuya çevir" (reduction); OMSCS CS 6515 ana teması.
6. **Üçgen eşitsizliği + toplama argümanı** → ortalama/amortize analiz, potansiyel fonksiyon kanıtları.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
Bellman-Ford'un sırrı tek bir gözlemdir — sonlu bir en kısa yol $V-1$ kenardan uzun olamaz. Çizgeyi $V+1$ seviyeye çoğaltıp çevrimsiz (DAG) hâle getirir, çözmeyi bildiğimiz DAG relaxation'ı çağırır; $V$ kenarda hâlâ kısalan düğümleri "tanık" olarak yakalayıp onlardan erişilen her şeye $-\infty$ yayar. Çevrimli/negatif problemi, çevrimsiz bir probleme indirger — bedeli yalnızca bir $V$ faktörü, yani $O(V \cdot E)$.
:::
