---
title: "Ağırlıklı En Kısa Yollar"
subtitle: "Kenarlara tamsayı ağırlık w: E → ℤ verince en kısa yol = toplam ağırlığın minimumu; iki yeni tuzak (yol yok → +∞, negatif çevrim erişilir → −∞); mesafe yeter (ebeveyn işaretçileri δ'dan O(V+E)'de kurulur); bir DAG'da SSSP'yi ∞'dan başlayan tahminleri topolojik sırada üçgen eşitsizliğine göre güvenle gevşeterek O(V+E)'de çöz; algoritma haritası DAG / Bellman-Ford / Dijkstra"
---
::: {.callout-note title="Bölüm bilgisi"}
- **Ku'nun videosu:** [YouTube — Lecture 11: Weighted Shortest Paths](https://www.youtube.com/watch?v=5cF5Bgv59Sc) (≈58 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 11: Weighted Shortest Paths](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-11-weighted-shortest-paths/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 16 (L11)
- **Hoca:** Jason Ku (ağırlıklı en kısa yollar ünitesinin açılışı)
- **Okuma süresi:** ≈26 dk
> Bir önceki ders BFS/DFS ile uzaklığı **kenar sayısıyla** ölçtü; bu ders her kenara bir tamsayı **ağırlık** verir ve "en az kenar" yerine "en az toplam ağırlık" arar. Bu, sonraki dört dersin (DAG relaxation, Bellman-Ford, Dijkstra, Johnson) temelidir.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d16}
Şimdiye dek uzaklığı **kenar sayısıyla** ölçtük (BFS/DFS). Bugün Jason Ku ile **ağırlıklı en kısa yollar** ünitesini açıyoruz: her kenara bir tamsayı **ağırlık** veririz ve iki düğüm arasında "en az kenar" yerine "en az toplam ağırlık" ararız. Bu genelleştirme, sonraki dört dersin (DAG relaxation, Bellman-Ford, Dijkstra, Johnson) temelidir.
> *"instead of... the number of edges in a path... we're going to count an integer associated with that edge. It's going to be called a weight."* — Ku, 3:33
Üç ana fikir bu derste yan yana gelir:
1. **Ağırlıklı en kısa yol** $\delta(s, t)$ — yol ağırlıklarının minimumu; iki yeni tuzak: yol yoksa $+\infty$, **negatif ağırlıklı çevrim** erişilirse $-\infty$.
2. **Mesafe yeter** — yalnızca $\delta$ mesafelerini hesapla; ebeveyn işaretçilerini sonradan doğrusal zamanda kur.
3. **DAG relaxation** — bir DAG'da, topolojik sırada **kenar gevşetme (relax)** ile SSSP'yi $O(V + E)$'de çöz.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 16'nın (L11) kavram haritası: kök = ağırlıklı en kısa yollar (Ku). Beş dal — (1) ağırlık fonksiyonu w: her kenara tamsayı ağırlık (pozitif, negatif ya da sıfır); yol ağırlığı = kenar ağırlıklarının toplamı; en kısa yol = minimum toplam ağırlık. (2) iki tuzak: yol yoksa arti sonsuz (erişilemez); negatif ağırlıklı çevrim erişilirse eksi sonsuz (minimum yok, infimum). (3) algoritma haritası: kısıt azaldıkça süre doğrusaldan uzaklaşır — DAG relaxation doğrusal, Bellman-Ford genel, Dijkstra negatif yok. (4) mesafe yeter: yalnız mesafeyi hesapla; ebeveyn işaretçileri sonradan doğrusal zamanda kurulur. (5) DAG relaxation: tahminleri sonsuzdan başlat, topolojik sırada üçgen eşitsizliğine göre güvenle gevşet, doğrusalda bitir. Sonuç: tek gevşetme tekniği, dört dersin temeli."
flowchart TD
A["Ders 16 (L11): Ağırlıklı En Kısa Yollar"] --> W["ağırlık fonksiyonu w<br/>her kenara tamsayı ağırlık"]
W --> W1["yol ağırlığı = kenar ağırlıkları toplamı<br/>en kısa yol = minimum toplam ağırlık"]
A --> T["iki tuzak<br/>arti sonsuz / eksi sonsuz"]
T --> T1["yol yok → arti sonsuz (erişilemez)<br/>negatif çevrim → eksi sonsuz (infimum)"]
A --> M["algoritma haritası<br/>DAG · Bellman-Ford · Dijkstra"]
M --> M1["kısıt azaldıkça süre artar<br/>DAG doğrusal → Bellman-Ford genel"]
A --> P["mesafe yeter<br/>ebeveyn sonradan"]
P --> P1["yalnız mesafeyi hesapla<br/>ebeveyn işaretçisi δ'dan doğrusal"]
A --> R["DAG relaxation<br/>üçgen eşitsizliği"]
R --> R1["sonsuzdan başla, topolojik sırada gevşet<br/>güvenli relax → doğrusal"]
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 W,T,M,P,R branch
class W1,T1,M1,P1,R1 leaf
```
::: {.callout-tip title="Builder Notu — Ağırlık Girince Dünya Değişir"}
BFS/DFS, "en az kenar" sorusunu doğrusal zamanda çözdü. Kenarlara ağırlık verince soru değişir: artık kenar saymıyoruz, **toplam ağırlığı** topluyoruz — ve iki yeni tuzak doğuyor (yol yok, negatif çevrim). Önce neyi sorduğumuzu (ağırlıklı en kısa yol), sonra nasıl çözdüğümüzü (DAG relaxation) ele alırız.
- **İleriye → GPS/yönlendirme:** ağırlıklı en kısa yol, Google Maps'in özüdür (kenar = yol, ağırlık = süre/mesafe); ağ gecikmesi (latency) yönlendirmesi de aynı.
- **İleriye → kritik yol/zamanlama:** DAG relaxation, proje zamanlama (PERT/CPM) ve build sistemlerinde "en uzun/en kısa yol" hesabıdır.
- **İleriye → sezgisel arama:** üçgen eşitsizliği (triangle inequality), sezgisel-yönlü `A*` aramasının teorik dayanağıdır.
- **Geriye → BFS (Ders 13):** ağırlıksız en kısa yolu BFS verdi; bu ders onu *genelleştirir* — BFS, tüm ağırlıklar eşit olan özel durumdur.
Tek cümle: *Kenarlara ağırlık verince "en kısa yol" toplam ağırlığın minimumu olur; bir DAG'da bunu, mesafe tahminlerini topolojik sırada üçgen eşitsizliğine göre gevşeterek $O(V + E)$'de çözeriz.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 16 (L11) Ağırlıklı En Kısa Yollar motoru (_engine.py D16
# bölümü: INF → brute_dag_sssp) + D15 topological_order/finishing_order +
# D13 bfs (uniform indirgeme 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 bu hücrede
# tanımlanan path_weight / relax_edge / dag_relaxation / dag_sssp /
# dag_relaxation_trace / parents_from_distances / uniform_weight_sssp /
# build_weighted_dag_example / build_negative_cycle_example / brute_dag_sssp /
# topological_order / bfs + 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"
# "güvenli/onay" yeşilimsi ton — cost_matrix paletiyle uyumlu (relax-safe rozeti)
COL_OK = "#3f7d5e"
COL_OK_BG = "#cfe8da"
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 D13 (L9) — bfs (uniform-ağırlık indirgeme için, L11 §5).
# adj = dict {düğüm: çıkış komşu listesi}.
# ---------------------------------------------------------------------------
def bfs(adj, s):
"""BFS (L9 §8): kaynaktan katman katman; (delta, parent) döndürür. O(V+E)."""
delta = {s: 0}
parent = {s: None}
queue = deque([s])
while queue:
u = queue.popleft()
for v in adj[u]:
if v not in delta: # henüz görülmemiş
delta[v] = delta[u] + 1
parent[v] = u
queue.append(v)
return delta, parent
# ---------------------------------------------------------------------------
# _engine.py D15 (L10) — finishing_order / topological_order
# (DAG'da TERS bitiş sırası = topolojik sıra; DAG relaxation bunu kullanır).
# ---------------------------------------------------------------------------
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) # tüm komşular bitti → bitiş
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) — Ağırlıklı En Kısa Yollar — Ku
# w: E → ℤ; yol ağırlığı = kenar toplamı; δ(s,t) = min; iki tuzak (+∞ yol yok,
# −∞ negatif çevrim erişilir); mesafe YETER (ebeveyn δ'dan O(V+E) kurulur);
# DAG relaxation: ∞'dan başla, topolojik sırada üçgen eşitsizliği ihlalinde
# gevşet (relax GÜVENLİ) → O(V+E).
# ---------------------------------------------------------------------------
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.
Döndürür: gevşetildi mi (figür izi için)."""
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, Notion pseudocode birebir): d=∞, d[s]=0;
topolojik sırada her u'nun çıkış komşularını 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 dag_relaxation_trace(adj, weight, s, topo_order):
"""fig-dag-relaxation için: her işlenen u'da gevşetilen kenarlar + d anlık."""
d = {v: INF for v in adj}
d[s] = 0
steps = []
for u in topo_order:
relaxed = []
for v in adj[u]:
old = d[v]
if relax_edge(d, weight, u, v):
relaxed.append((v, old, d[v]))
steps.append({"u": u, "relaxed": relaxed, "d": dict(d)})
return {"steps": steps, "d": d}
def parents_from_distances(adj, weight, s, d):
"""Mesafeden ebeveyn kurma (L11 §7): δ(s,v) = δ(s,u) + w(u,v) olan ilk
(u,v) kenarı en kısa yolun parçası → P[v]=u. Tek geçiş O(V+E)."""
parent = {s: None}
for u in adj:
if d[u] == INF:
continue
for v in adj[u]:
if v not in parent and d[v] == d[u] + weight[(u, v)]:
parent[v] = u
return parent
def uniform_weight_sssp(adj, s, c):
"""BFS-indirgeme özel durumu (L11 §5): tüm ağırlıklar = c > 0 →
BFS mesafesi × c."""
delta, _ = bfs(adj, s)
return {v: delta[v] * c for v in delta}
def build_weighted_dag_example():
"""L11 §10 çalışılan örneğine uyumlu DAG (Notion anlatı sayıları birebir):
topolojik sıra a, b, e, f, g, h, d, c; kaynak e.
Kenarlar: a→b(1); e→f(3); f→h(8), f→g(2); g→h(1), g→d(−2); d→c(5).
Beklenen δ(e,·): e=0, f=3, g=5 (3+2), h=6 (5+1; 11'i değiştirir),
d=3 (5−2), c=8 (3+5); a=b=+∞ (e'den erişilmez).
"""
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
def build_negative_cycle_example():
"""L11 §4 örneği (Notion birebir): çevrim b→f→g→c→b ağırlığı
(−4)+2+1+(−1) = −2 — her turda −2 kazanılır → δ = −∞."""
weight = {("b", "f"): -4, ("f", "g"): 2, ("g", "c"): 1, ("c", "b"): -1}
cycle = ["b", "f", "g", "c", "b"]
return weight, cycle
def brute_dag_sssp(adj, weight, s):
"""Bağımsız tanık: tüm basit yolları DFS ile sayıp min ağırlık (küçük DAG).
dag_relaxation'dan FARKLI mekanizma."""
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. Ağırlıksızdan Ağırlığa: Neden ve Nasıl {#sec-1-agirliksizdan-agirliga}
Son iki ders BFS/DFS ile ağırlıksız problemleri (SSSP, erişilebilirlik, bağlı bileşenler, topolojik sıralama) doğrusal zamanda çözdü. Şimdi genelleştiriyoruz: her kenara bir **tamsayı ağırlık** atayan bir **ağırlık fonksiyonu** $w: E \to \mathbb{Z}$. Ağırlıklar pozitif, negatif veya sıfır olabilir.
Neden? Gerçek uygulamalar: yol ağında mesafe/süre (Vassar Street ile Amherst arası kısa, köprü uzun), ağ gecikmesi, sosyal ağda ilişki gücü (hatta "frenemy" için negatif).
## 2. Ağırlık Gösterimi {#sec-2-agirlik-gosterimi}
Çizgeyi komşuluk listesiyle saklıyorduk; ağırlığı iki yolla ekleriz:
- **Komşulukla birlikte:** her komşuyu ağırlığıyla bir **ikili (tuple)** olarak sakla.
- **Ayrı sözlük:** kenarları ağırlıklarına eşleyen ayrı bir hash tablosu (edge → weight).
Tek varsayım: bir kenarın ağırlığı $O(1)$'de sorgulanabilir (hash tablosu veya hash-tablosu-of-hash-tablosu).
## 3. Ağırlıklı Yol ve En Kısa Yol {#sec-3-agirlikli-yol-ve-en-kisa-yol}
Bir **yolun ağırlığı** $w(\pi)$, yoldaki kenarların ağırlıklarının **toplamıdır**.
> *"the weight of a path... is just going to be the sum of the weights in the edges in the path."* — Ku, 11:08
Örneğin §4'te kullanacağımız çizgede $a \to b \to f \to g = -5 + (-4) + 2 = -7$. **Ağırlıklı en kısa yol**, iki düğüm arasında **minimum ağırlıklı** yoldur.
> *"a shortest path... is a minimum weight path from s to t."* — Ku, 13:29
Mesafeyi $\delta(s, t)$ ile gösteririz: $s$'den $t$'ye tüm yolların ağırlık minimumu. (Uyarı: ağırlıklı yol bir kenarı birden çok kez kullanabilir — *basit yol* değilse; en kısa yolların bunu yapmadığını sonra göreceğiz.)
@fig-weighted-graph ağırlıklı bir DAG üzerinde yol ağırlığı fikrini gösterir: her kenarda bir ağırlık rozeti var (negatif $g \to d = -2$ amber vurgulu), vurgulu yol $\pi = e \to f \to g \to d$ amber kalın, altta toplam kutusu $w(\pi) = 3 + 2 + (-2) = 3$ — kenar ağırlıklarının toplamı (kenar sayısı değil).
```{python}
#| label: fig-weighted-graph
#| fig-cap: "Ağırlıklı çizge: w: E → ℤ ve yol ağırlığı = kenar ağırlıklarının TOPLAMI (L11 §1-3). Örnek ağırlıklı DAG (kaynak e): kenarlar e→f(3), f→h(8), f→g(2), g→h(1), g→d(−2 AMBER negatif), d→c(5); a, b ayrık üst köşe (e'den ERİŞİLMEZ → δ=+∞, soluk çizilir). Vurgulu yol π = e→f→g→d amber kalın; sağ alt toplam kutusu w(π) = 3 + 2 + (−2) = 3 (kenar ağırlıklarının TOPLAMI, kenar SAYISI değil). Yan kutu: ağırlık fonksiyonu w: E → ℤ — pozitif, negatif ya da sıfır olabilir (gerçek hayat: yol = süre, ağ = gecikme). Alt not: en kısa yol δ(s,t) = MİNİMUM toplam ağırlıklı yol (artık en az kenar değil; negatif kenar daha uzun bir yolu kısaltabilir). Veri MOTORDAN: path_weight(w, [e,f,g,d]) = 3 + 2 + (−2) = 3 (Ku 11:08, 13:29)."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-weighted-graph (L11 §1-3): ağırlıklı DAG + yol ağırlığı = TOPLAM.
# Veri MOTORDAN (build_weighted_dag_example / path_weight). networkx YOK — elle koordinat.
_WG_POS = {
"e": (0.0, 1.0), "f": (1.0, 1.0), "g": (2.0, 1.0),
"h": (3.0, 1.6), "d": (3.0, 0.4), "c": (4.0, 0.4),
"a": (0.0, 2.2), "b": (1.0, 2.2),
}
_WG_R = 0.20
_WG_SCALE = 1.45
_WG_OX, _WG_OY = 0.55, 0.55
_WG_FAINT = {"a", "b"}
_WG_PATH = ["e", "f", "g", "d"]
_WG_PATH_EDGES = {("e", "f"), ("f", "g"), ("g", "d")}
def _wg_P(node):
ux, uy = _WG_POS[node]
return _WG_OX + ux * _WG_SCALE, _WG_OY + uy * _WG_SCALE
def _wg_edge(ax, u, v, w_uv):
ux, uy = _wg_P(u)
vx, vy = _wg_P(v)
on_path = (u, v) in _WG_PATH_EDGES
faint = (u in _WG_FAINT or v in _WG_FAINT)
negative = (w_uv < 0)
if faint:
col, lw, alpha, b_ec, b_fc = COL_SLATE_400, 1.4, 0.45, COL_SLATE_400, COL_WHITE
elif on_path:
col, lw, alpha, b_ec, b_fc = COL_ACCENT, 3.4, 1.0, COL_AMBER_700, COL_AMBER_100
elif negative:
col, lw, alpha, b_ec, b_fc = COL_PRIMARY, 2.0, 1.0, COL_AMBER_700, COL_AMBER_100
else:
col, lw, alpha, b_ec, b_fc = COL_PRIMARY, 2.0, 1.0, COL_SLATE_500, COL_BG
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=16, color=col,
linewidth=lw, alpha=alpha, shrinkA=_WG_R * _WG_SCALE * 1.85,
shrinkB=_WG_R * _WG_SCALE * 1.85, zorder=4 if on_path else 2))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
dx, dy = vx - ux, vy - uy
norm = (dx * dx + dy * dy) ** 0.5 or 1.0
px, py = -dy / norm, dx / norm
off = 0.0 if abs(dx) < 1e-9 else 0.16
bx, by = mx + px * off, my + py * off
wtxt = ("−" + str(abs(w_uv))) if negative else str(w_uv)
badge_lw = 2.2 if on_path else (2.0 if negative else 1.4)
ax.add_patch(Circle((bx, by), 0.165, facecolor=b_fc, edgecolor=b_ec,
linewidth=badge_lw, alpha=0.45 if faint else 1.0, zorder=6))
tcol = COL_SLATE_400 if faint else b_ec
ax.text(bx, by, wtxt, ha="center", va="center", fontsize=10.5,
color=tcol, weight="bold", zorder=7, alpha=0.45 if faint else 1.0)
def _wg_node(ax, node):
x, y = _wg_P(node)
faint = node in _WG_FAINT
on_path = node in _WG_PATH
if faint:
fc, ec, tcol, lw, alpha = COL_WHITE, COL_SLATE_400, COL_SLATE_400, 1.4, 0.55
elif on_path:
fc, ec, tcol, lw, alpha = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 3.0, 1.0
else:
fc, ec, tcol, lw, alpha = COL_BG, COL_PRIMARY, COL_TEXT, 2.0, 1.0
ax.add_patch(Circle((x, y), _WG_R * _WG_SCALE, facecolor=fc, edgecolor=ec,
linewidth=lw, alpha=alpha, zorder=8))
ax.text(x, y, node, ha="center", va="center", fontsize=14,
color=tcol, weight="bold", zorder=9, alpha=alpha)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_wg_adj, _wg_w, _wg_topo = build_weighted_dag_example()
_wg_pw = path_weight(_wg_w, _WG_PATH)
assert _wg_topo == ["a", "b", "e", "f", "g", "h", "d", "c"], _wg_topo
assert _wg_w[("g", "d")] == -2, _wg_w[("g", "d")]
assert _wg_pw == 3, _wg_pw # 3 + 2 + (−2)
_wg_seg = [_wg_w[(_WG_PATH[i], _WG_PATH[i + 1])] for i in range(len(_WG_PATH) - 1)]
assert _wg_seg == [3, 2, -2], _wg_seg
assert sum(_wg_seg) == _wg_pw, (_wg_seg, _wg_pw)
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
for _u in _wg_adj:
for _v in _wg_adj[_u]:
_wg_edge(ax, _u, _v, _wg_w[(_u, _v)])
for _node in _WG_POS:
_wg_node(ax, _node)
fig.suptitle(
"Ağırlıklı çizge: w: E → ℤ · yol ağırlığı = kenar ağırlıklarının TOPLAMI",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
_wg_ap = _wg_P("a")
ax.text(_wg_ap[0] - 0.10, _wg_ap[1] + _WG_R * _WG_SCALE + 0.30,
"a, b: e'den ERİŞİLMEZ (δ = +∞, yol yok)", ha="left", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=9)
_wg_ex, _wg_ey = _wg_P("e")
ax.text(_wg_ex, _wg_ey - _WG_R * _WG_SCALE - 0.28, "kaynak s = e", ha="center",
va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=9)
# YOL VURGUSU + TOPLAM kutusu (sağ alt)
_bx, _by, _bw, _bh = 7.05, 0.45, 4.05, 1.30
ax.add_patch(FancyBboxPatch(
(_bx, _by), _bw, _bh, boxstyle="round,pad=0.05,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=10))
ax.text(_bx + 0.22, _by + _bh - 0.27, "vurgulu yol π = e→f→g→d (amber)",
ha="left", va="center", fontsize=10, color=COL_AMBER_700, weight="bold", zorder=11)
ax.text(_bx + 0.22, _by + _bh - 0.60,
f"w(π) = {_wg_seg[0]} + {_wg_seg[1]} + (−{abs(_wg_seg[2])}) = {_wg_pw}",
ha="left", va="center", fontsize=12.5, color=COL_TEXT, weight="bold",
family="monospace", zorder=11)
ax.text(_bx + 0.22, _by + 0.22, "kenar ağırlıklarının TOPLAMI (kenar SAYISI değil)",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, style="italic", zorder=11)
# YAN kutu: ağırlık fonksiyonu w: E → ℤ
_sx, _sy, _sw, _sh = 7.05, 2.15, 4.05, 1.78
ax.add_patch(FancyBboxPatch(
(_sx, _sy), _sw, _sh, boxstyle="round,pad=0.05,rounding_size=0.10",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.6, zorder=10))
ax.text(_sx + 0.22, _sy + _sh - 0.28, "ağırlık fonksiyonu w: E → ℤ", ha="left",
va="center", fontsize=10.5, color=COL_TEXT, weight="bold", zorder=11)
ax.text(_sx + 0.22, _sy + _sh - 0.62, "ağırlık POZİTİF, NEGATİF ya da SIFIR olabilir",
ha="left", va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=11)
ax.add_patch(Circle((_sx + 0.42, _sy + _sh - 0.96), 0.135, facecolor=COL_AMBER_100,
edgecolor=COL_AMBER_700, linewidth=2.0, zorder=11))
ax.text(_sx + 0.42, _sy + _sh - 0.96, "−2", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=12)
ax.text(_sx + 0.66, _sy + _sh - 0.96, "g→d negatif kenar (amber rozet)", ha="left",
va="center", fontsize=8.6, color=COL_SLATE_500, zorder=11)
ax.text(_sx + 0.22, _sy + 0.24, "gerçek hayat: yol = süre · ağ = gecikme",
ha="left", va="center", fontsize=9, color=COL_PRIMARY, weight="bold", zorder=11)
ax.text(0.30, -0.30,
"en kısa yol δ(s, t) = MİNİMUM toplam ağırlıklı yol "
"(artık \"en az kenar\" DEĞİL — negatif kenar daha uzun bir yolu kısaltabilir)",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, style="italic", zorder=9)
ax.set_xlim(-0.2, 11.4)
ax.set_ylim(-0.65, 4.55)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 4. İki Tuzak: +∞ ve −∞ {#sec-4-iki-tuzak}
$\delta$ tanımında iki şey ters gidebilir:
1. **Yol yoksa:** $\delta(s, t) = +\infty$ (uzlaşım, BFS'teki gibi).
2. **Sonlu en kısa yol yoksa:** kenarları döne döne **giderek daha kısa** bir yol bulunabiliyorsa $\delta$ tanımsızdır; bu durumda $\delta = -\infty$ (minimum değil, *infimum*).
> *"It's possible that a finite length shortest path doesn't exist."* — Ku, 15:26
**Çalışılan Örnek — negatif ağırlıklı çevrim.** Bu, **negatif ağırlıklı çevrim** olduğunda olur. Örnek çizgede $b \to f \to g \to c \to b = (-4) + 2 + 1 + (-1) = -2$. $b$'ye $-5$ ağırlıklı kenarla varıp bu çevrimde her tur $-2$ kazanırsak, sonsuza dek küçülürüz → sonlu en kısa yol yok.
> *"we could have negative weight cycles."* — Ku, 18:46
Kural: $s$'den $v$'ye giden bir yol bir **negatif ağırlıklı çevrim üzerindeki** düğümden geçiyorsa, $\delta(s, v) = -\infty$. Bu durumda ebeveyn işaretçisiyle uğraşmayız (sonlu yol yok); bunun yerine bir negatif çevrim döndürmek isteyebiliriz (bu, sonraki dersin Bellman-Ford konusudur).
@fig-two-traps iki tuzağı yan yana koyar: solda $+\infty$ (iki ayrık küme, geçiş yok), sağda $-\infty$ (negatif çevrim $b \to f \to g \to c \to b$ erişilir, her tur $-2$ kazanç).
```{python}
#| label: fig-two-traps
#| fig-cap: "Ağırlıklı en kısa yolun iki tuzağı: +∞ (erişilemez) ve −∞ (negatif çevrim) (L11 §4, İMZA figür). SOL panel +∞ TUZAĞI: iki ayrık küme — kaynak s'nin erişebildiği küme (s→p, ağırlık 4) ve t'nin kopuk bileşeni (t→q); aralarında kesikli '?' engeli, geçiş yok → δ(s,t) = +∞ (erişilemez). SAĞ panel −∞ TUZAĞI: kaynak s'den çevrime −5 ile giriş (b'ye); çevrim b→f→g→c→b elmas yerleşimle, kenar ağırlıkları MOTORDAN: b→f(−4 amber), f→g(2), g→c(1), c→b(−1 amber); çevrim çevresinde dönen kavisli oklar. Çevrim toplamı kutusu (−4)+2+1+(−1) = −2 (AMBER): her tur −2 kazanç → istediğin kadar küçült → δ = −∞ (minimum yok, infimum). Alt şerit: +∞ = erişilemez, −∞ = negatif çevrim erişilir (sonlu en kısa yol YOK). Veri MOTORDAN: build_negative_cycle_example çevrim [b,f,g,c,b], path_weight = −2 (Ku 15:26, 18:46)."
#| fig-width: 11.0
#| fig-height: 6.2
# fig-two-traps (L11 §4 İMZA): +∞ (ayrık küme) vs −∞ (negatif çevrim).
# Veri MOTORDAN (build_negative_cycle_example / path_weight). networkx YOK.
_TT_R = 0.34
_TT_BW, _TT_BH = 0.50, 0.34
def _tt_node(ax, x, y, label, src=False, dim=False):
if src:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 3.0
elif dim:
fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_SLATE_500, 1.6
else:
fc, ec, tcol, lw = COL_BG, COL_PRIMARY, COL_TEXT, 2.2
ax.add_patch(Circle((x, y), _TT_R, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=5))
ax.text(x, y, label, ha="center", va="center", fontsize=14, color=tcol,
weight="bold", zorder=6)
def _tt_badge(ax, x, y, text, negative=False):
if negative:
fc, ec, tcol = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
else:
fc, ec, tcol = COL_WHITE, COL_PRIMARY, COL_TEXT
ax.add_patch(FancyBboxPatch(
(x - _TT_BW * 0.5, y - _TT_BH * 0.5), _TT_BW, _TT_BH,
boxstyle="round,pad=0.02,rounding_size=0.06", fc=fc, ec=ec, linewidth=1.6, zorder=7))
ax.text(x, y, text, ha="center", va="center", fontsize=9.5, color=tcol,
weight="bold", zorder=8)
def _tt_arrow(ax, p0, p1, color, lw=2.2, shrink=_TT_R * 60, rad=0.0):
cs = f"arc3,rad={rad}" if rad else None
ax.add_patch(FancyArrowPatch(
p0, p1, arrowstyle="-|>", mutation_scale=16, color=color, linewidth=lw,
shrinkA=shrink, shrinkB=shrink, zorder=3, connectionstyle=cs))
def _tt_plus_inf(ax):
ax.text(2.0, 5.55, "+∞ TUZAĞI", ha="center", va="center", fontsize=13,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(2.0, 5.08, "s'den t'ye hiçbir yol yok", ha="center", va="center",
fontsize=9.5, color=COL_SLATE_500, style="italic", zorder=6)
_tt_node(ax, 0.85, 3.55, "s", src=True)
_tt_node(ax, 0.85, 2.25, "p")
_tt_arrow(ax, (0.85, 3.55 - _TT_R), (0.85, 2.25 + _TT_R), COL_SLATE_500, shrink=0)
_tt_badge(ax, 0.85, 2.90, "4")
ax.add_patch(FancyBboxPatch(
(0.20, 1.55), 1.30, 2.70, boxstyle="round,pad=0.04,rounding_size=0.14",
fc="none", ec=COL_SLATE_400, linewidth=1.4, linestyle="--", zorder=1))
ax.text(0.85, 1.30, "s'nin erişebildiği", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, zorder=6)
_tt_node(ax, 3.35, 3.55, "t", dim=True)
_tt_node(ax, 3.35, 2.25, "q", dim=True)
_tt_arrow(ax, (3.35, 3.55 - _TT_R), (3.35, 2.25 + _TT_R), COL_SLATE_400, shrink=0)
_tt_badge(ax, 3.35, 2.90, "2")
ax.add_patch(FancyBboxPatch(
(2.70, 1.55), 1.30, 2.70, boxstyle="round,pad=0.04,rounding_size=0.14",
fc="none", ec=COL_SLATE_400, linewidth=1.4, linestyle="--", zorder=1))
ax.text(3.35, 1.30, "t'nin bileşeni (kopuk)", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, zorder=6)
ax.plot([2.10, 2.10], [1.85, 3.95], color=COL_SLATE_400, linewidth=1.6,
linestyle=(0, (2, 3)), zorder=1)
ax.add_patch(Circle((2.10, 2.90), 0.40, facecolor=COL_WHITE, edgecolor=COL_SLATE_400,
linewidth=1.8, linestyle="--", zorder=2))
ax.text(2.10, 2.90, "?", ha="center", va="center", fontsize=18,
color=COL_SLATE_500, weight="bold", zorder=3)
ax.text(2.10, 2.20, "yol yok", ha="center", va="center", fontsize=7.5,
color=COL_SLATE_500, style="italic", zorder=3)
ax.add_patch(FancyBboxPatch(
(0.45, 0.30), 3.10, 0.66, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_AMBER_600, linewidth=1.8, zorder=4))
ax.text(2.0, 0.63, "yol YOK → δ(s, t) = +∞ (erişilemez)", ha="center",
va="center", fontsize=11, color=COL_AMBER_700, weight="bold", zorder=5)
ax.set_xlim(0.0, 4.0)
ax.set_ylim(0.0, 5.9)
ax.set_aspect("equal")
ax.axis("off")
def _tt_minus_inf(ax, weight, cycle, cyc_w):
ax.text(3.05, 5.55, "−∞ TUZAĞI", ha="center", va="center", fontsize=13,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(3.05, 5.08, "negatif çevrim erişilebilir", ha="center", va="center",
fontsize=9.5, color=COL_SLATE_500, style="italic", zorder=6)
pos = {"b": (2.05, 3.30), "f": (3.30, 4.20), "g": (4.55, 3.30), "c": (3.30, 2.40)}
s_pos = (0.55, 3.30)
_tt_node(ax, s_pos[0], s_pos[1], "s", src=True)
_tt_arrow(ax, s_pos, pos["b"], COL_PRIMARY, lw=2.0)
_tt_badge(ax, (s_pos[0] + pos["b"][0]) * 0.5, (s_pos[1] + pos["b"][1]) * 0.5, "−5")
edges = [("b", "f"), ("f", "g"), ("g", "c"), ("c", "b")]
for (u, v) in edges:
w = weight[(u, v)]
neg = w < 0
col = COL_ACCENT if neg else COL_PRIMARY
_tt_arrow(ax, pos[u], pos[v], col, lw=2.4 if neg else 2.0)
bx = (pos[u][0] + pos[v][0]) * 0.5
by = (pos[u][1] + pos[v][1]) * 0.5
_tt_badge(ax, bx, by, f"{w:+d}".replace("-", "−"), negative=neg)
for name, (x, y) in pos.items():
_tt_node(ax, x, y, name)
cx, cy = 3.30, 3.30
for (a0, a1) in [(0.55, 1.55), (2.15, 3.15), (3.75, 4.75), (5.35, 6.05)]:
x0, y0 = cx + 1.35 * math.cos(a0), cy + 1.05 * math.sin(a0)
x1, y1 = cx + 1.35 * math.cos(a1), cy + 1.05 * math.sin(a1)
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=11,
color=COL_AMBER_600, linewidth=1.4, zorder=2,
connectionstyle="arc3,rad=0.30", alpha=0.75))
ax.text(cx, cy, "↻", ha="center", va="center", fontsize=15,
color=COL_AMBER_600, weight="bold", zorder=2, alpha=0.85)
ax.add_patch(FancyBboxPatch(
(1.85, 1.05), 2.95, 0.62, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=4))
cyc_w_str = str(cyc_w).replace("-", "−")
ax.text(3.325, 1.36, f"çevrim toplamı: (−4)+2+1+(−1) = {cyc_w_str}",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.add_patch(FancyBboxPatch(
(0.30, 0.20), 5.50, 0.70, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_AMBER_600, linewidth=1.8, zorder=4))
ax.text(3.05, 0.55,
"her tur −2 kazanç → istediğin kadar küçült → δ = −∞ (minimum yok, infimum)",
ha="center", va="center", fontsize=9.3, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.set_xlim(0.0, 6.1)
ax.set_ylim(0.0, 5.9)
ax.set_aspect("equal")
ax.axis("off")
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_tt_weight, _tt_cycle = build_negative_cycle_example()
_tt_cyc_w = path_weight(_tt_weight, _tt_cycle)
assert _tt_cycle == ["b", "f", "g", "c", "b"], _tt_cycle
assert _tt_weight == {("b", "f"): -4, ("f", "g"): 2,
("g", "c"): 1, ("c", "b"): -1}, _tt_weight
assert _tt_cyc_w == -2, _tt_cyc_w
assert INF == float("inf")
fig, (_tt_axl, _tt_axr) = plt.subplots(
1, 2, figsize=(11.0, 6.2), gridspec_kw={"width_ratios": [4.0, 6.1]})
fig.patch.set_facecolor(COL_WHITE)
_tt_plus_inf(_tt_axl)
_tt_minus_inf(_tt_axr, _tt_weight, _tt_cycle, _tt_cyc_w)
fig.suptitle(
"Ağırlıklı en kısa yolun iki tuzağı: +∞ (erişilemez) ve −∞ (negatif çevrim)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985)
fig.text(0.5, 0.035,
"+∞ = erişilemez | −∞ = negatif çevrim erişilir (sonlu en kısa yol YOK)",
ha="center", va="center", fontsize=10, color=COL_SLATE_500, style="italic")
fig.subplots_adjust(left=0.02, right=0.98, top=0.90, bottom=0.10, wspace=0.08)
plt.show()
```
## 5. BFS'e İndirgenebilen Özel Durumlar {#sec-5-bfse-indirgenebilen-ozel-durumlar}
Ağırlıklı SSSP'nin bazı özel halleri **BFS**'e indirgenir:
- **Tüm ağırlıklar = 1:** zaten ağırlıksız çizge — BFS doğrudan çözer.
- **Tüm ağırlıklar = aynı pozitif değer $c$:** $c$'ye böl → ağırlıksız çöz → sonuçları $c$ ile çarp.
- **Pozitif ağırlıkları seri kenarlara aç:** ağırlık 4'lük bir kenar, 4 ardışık (seri) ağırlık-1 kenara dönüştürülür. Tüm ağırlıklar toplamı asimptotik olarak $V + E$'den küçükse, bu dönüşüm + BFS yine **doğrusal**.
Genel ağırlıklı SSSP'yi doğrusal zamanda çözmek **açık problemdir** (bilinmiyor).
## 6. Genel Manzara: DAG / Bellman-Ford / Dijkstra {#sec-6-genel-manzara}
Üç algoritma, üç kısıt seviyesi:
- **DAG relaxation** (bu ders): çizge bir **DAG** ise — ağırlıklar *herhangi bir* tamsayı olabilir (negatif dahil, çevrim olmadığından sorun yok) — $O(V + E)$ doğrusal.
- **Bellman-Ford** (Ders 18, L12): *herhangi* çizge (çevrim, negatif çevrim dahil); $\sim O(V \cdot E)$ (karesel benzeri); pratik ve yaygın.
- **Dijkstra** (Ders 19, L13): ağırlıklar **negatif değilse**; $\sim O(V \log V + E)$ (doğrusala yakın, $V$'de bir log faktörü). Çoğu gerçek problem (yol ağı) negatif olmadığından Dijkstra en sık kullanılandır.
@fig-algorithm-map bu üç algoritmayı kısıt seviyesine göre dizer ve çalışılan DAG örneğinde $\delta$ değerlerini gösterir (motor kanıtı: $e=0, f=3, g=5, h=6, d=3, c=8$).
```{python}
#| label: fig-algorithm-map
#| fig-cap: "Ağırlıklı SSSP: üç algoritma, üç kısıt seviyesi — kısıt azaldıkça süre doğrusaldan uzaklaşır (L11 §6, İMZA figür). ÜST: örnek ağırlıklı DAG (kaynak e); her düğümün yanında motordan δ değeri (e=0, f=3, g=5, h=6, d=3, c=8; a,b = +∞ erişilmez, soluk). g→d = −2 negatif kenar AMBER (gevşetmeyi bozmaz). ALT: 3 satırlık karşılaştırma panosu, kısıt azaldıkça süre artar. Satır 1 DAG RELAXATION (bu ders L11, AMBER çerçeve): kısıt çizge DAG + ağırlık ∈ ℤ negatif OK → O(V+E) doğrusal. Satır 2 BELLMAN-FORD (Ders 18 L12): kısıt YOK, genel çizge, negatif çevrimi TESPİT eder (δ=−∞) → O(V·E) en genel/en yavaş. Satır 3 DIJKSTRA (Ders 19 L13): kısıt ağırlık ≥ 0 → O(V log V + E) doğrusala yakın. Alt not: genel SSSP'yi doğrusal zamanda çözmek hâlâ AÇIK PROBLEM; çoğu gerçek problem (yol ağı, mesafe) negatif içermez → Dijkstra en yaygın. Veri MOTORDAN: dag_sssp(e) = {e:0,f:3,g:5,h:6,d:3,c:8,a:∞,b:∞}."
#| fig-width: 10.5
#| fig-height: 6.6
# fig-algorithm-map (L11 §6 İMZA): üç algoritma, üç kısıt seviyesi.
# Veri MOTORDAN (build_weighted_dag_example / dag_sssp / dag_relaxation_trace).
_AM_POS = {
"e": (0.0, 1.0), "f": (1.0, 1.0), "g": (2.0, 1.0),
"h": (3.0, 1.6), "d": (3.0, 0.4), "c": (4.0, 0.4),
"a": (0.0, 2.2), "b": (1.0, 2.2),
}
_AM_EDGES = [
("e", "f", 3, False), ("f", "h", 8, False), ("f", "g", 2, False),
("g", "h", 1, False), ("g", "d", -2, True), ("d", "c", 5, False),
("a", "b", 1, False),
]
_AM_FADED = {"a", "b"}
_AM_R = 0.26
def _am_draw_dag(ax, ox, oy, scale, delta):
def P(node):
gx, gy = _AM_POS[node]
return ox + gx * scale, oy + gy * scale
for u, v, w, neg in _AM_EDGES:
faded = (u in _AM_FADED) or (v in _AM_FADED)
ux, uy = P(u)
vx, vy = P(v)
if neg:
ecol, lw = COL_AMBER_600, 2.6
elif faded:
ecol, lw = COL_SLATE_400, 1.4
else:
ecol, lw = COL_PRIMARY, 2.0
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=15, color=ecol,
linewidth=lw, shrinkA=_AM_R * scale * 1.05, shrinkB=_AM_R * scale * 1.05,
zorder=2, alpha=0.55 if faded else 1.0))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
if neg:
bfc, bec, btc = COL_AMBER_100, COL_AMBER_600, COL_AMBER_700
elif faded:
bfc, bec, btc = COL_WHITE, COL_SLATE_400, COL_SLATE_400
else:
bfc, bec, btc = COL_WHITE, COL_PRIMARY, COL_TEXT
ax.add_patch(FancyBboxPatch(
(mx - 0.155, my - 0.135), 0.31, 0.27, boxstyle="round,pad=0.01,rounding_size=0.06",
fc=bfc, ec=bec, linewidth=1.5, zorder=4, alpha=0.6 if faded else 1.0))
ax.text(mx, my, str(w), ha="center", va="center", fontsize=8.5, color=btc,
weight="bold", zorder=5, alpha=0.7 if faded else 1.0)
for node, (gx, gy) in _AM_POS.items():
x, y = P(node)
faded = node in _AM_FADED
is_src = (node == "e")
if is_src:
fc, ec, lw, tc = COL_AMBER_100, COL_ACCENT, 3.0, COL_AMBER_700
elif faded:
fc, ec, lw, tc = COL_WHITE, COL_SLATE_400, 1.4, COL_SLATE_400
else:
fc, ec, lw, tc = COL_BG, COL_PRIMARY, 2.0, COL_TEXT
ax.add_patch(Circle((x, y), _AM_R, facecolor=fc, edgecolor=ec, linewidth=lw,
zorder=5, alpha=0.6 if faded else 1.0))
ax.text(x, y, node, ha="center", va="center", fontsize=12, color=tc,
weight="bold", zorder=6, alpha=0.7 if faded else 1.0)
dv = delta[node]
dtxt = "∞" if dv == INF else str(dv)
ax.text(x + _AM_R + 0.04, y + _AM_R - 0.02, f"δ={dtxt}", ha="left", va="bottom",
fontsize=7.5, color=COL_SLATE_400 if faded else COL_AMBER_700,
weight="bold", zorder=7, alpha=0.7 if faded else 1.0)
sx, sy = P("e")
ax.text(sx - _AM_R - 0.08, sy - 0.02, "kaynak", ha="right", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=7)
ax_, ay_ = P("a")
bx_, by_ = P("b")
ax.text((ax_ + bx_) * 0.5, ay_ + _AM_R + 0.20, "a, b: e'den erişilmez (δ = +∞)",
ha="center", va="bottom", fontsize=7.5, color=COL_SLATE_400, style="italic", zorder=6)
def _am_icon_dag(ax, cx, cy):
r = 0.085
xs = [cx - 0.30, cx, cx + 0.30]
for x in xs:
ax.add_patch(Circle((x, cy), r, facecolor=COL_AMBER_100, edgecolor=COL_ACCENT,
linewidth=1.6, zorder=6))
for i in range(len(xs) - 1):
ax.add_patch(FancyArrowPatch(
(xs[i] + r, cy), (xs[i + 1] - r, cy), arrowstyle="-|>", mutation_scale=9,
color=COL_AMBER_700, linewidth=1.5, zorder=5))
def _am_icon_general(ax, cx, cy):
r = 0.075
pts = [(cx - 0.26, cy - 0.16), (cx + 0.26, cy - 0.16), (cx, cy + 0.22)]
for (x, y) in pts:
ax.add_patch(Circle((x, y), r, facecolor=COL_BG, edgecolor=COL_PRIMARY,
linewidth=1.6, zorder=6))
for i, j in [(0, 1), (1, 2), (2, 0)]:
x0, y0 = pts[i]
x1, y1 = pts[j]
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=8, color=COL_SLATE_500,
linewidth=1.4, zorder=5, shrinkA=6, shrinkB=6, connectionstyle="arc3,rad=0.20"))
def _am_icon_noneg(ax, cx, cy):
r = 0.22
ax.add_patch(Circle((cx, cy), r, facecolor=COL_WHITE, edgecolor=COL_PRIMARY,
linewidth=1.8, zorder=6))
ax.text(cx, cy, "−", ha="center", va="center", fontsize=12, color=COL_SLATE_500,
weight="bold", zorder=7)
off = r * 0.74
ax.plot([cx - off, cx + off], [cy + off, cy - off], color=COL_AMBER_600,
linewidth=2.2, zorder=8, solid_capstyle="round")
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_am_adj, _am_w, _am_topo = build_weighted_dag_example()
_am_delta = dag_sssp(_am_adj, _am_w, "e")
for _u, _v, _wt, _neg in _AM_EDGES:
assert _am_w[(_u, _v)] == _wt, (_u, _v, _wt, _am_w[(_u, _v)])
assert _am_delta == {"e": 0, "f": 3, "g": 5, "h": 6,
"d": 3, "c": 8, "a": INF, "b": INF}, _am_delta
_am_tr = dag_relaxation_trace(_am_adj, _am_w, "e", _am_topo)
assert _am_tr["d"] == _am_delta, (_am_tr["d"], _am_delta)
fig, ax = plt.subplots(figsize=(10.5, 6.6))
fig.patch.set_facecolor(COL_WHITE)
_am_draw_dag(ax, ox=0.55, oy=3.05, scale=1.55, delta=_am_delta)
ax.text(0.55 + 2.0 * 1.55, 3.05 + 2.2 * 1.55 + 0.62,
"örnek ağırlıklı DAG — ağırlık ∈ ℤ (negatif OK, çevrim YOK)", ha="center",
va="center", fontsize=10.5, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(0.55 + 2.0 * 1.55, 3.05 - 0.10,
"dag_sssp(e) δ doğrulandı: e=0, f=3, g=5, h=6, d=3, c=8 "
"(g→d = −2 negatif kenar gevşetmeyi bozmaz)", ha="center", va="center",
fontsize=8.0, color=COL_AMBER_700, style="italic", zorder=6)
_am_icon_x, _am_name_x, _am_cons_x, _am_time_x = 0.55, 1.15, 4.65, 8.05
_am_row_y = [2.05, 1.05, 0.05]
_am_row_h = 0.86
_am_pano_l, _am_pano_r = 0.18, 10.25
_am_head_y = _am_row_y[0] + _am_row_h * 0.5 + 0.30
ax.text(_am_name_x, _am_head_y, "algoritma (ders)", ha="left", va="center",
fontsize=9, color=COL_SLATE_500, weight="bold", zorder=6)
ax.text(_am_cons_x, _am_head_y, "kısıt", ha="left", va="center", fontsize=9,
color=COL_SLATE_500, weight="bold", zorder=6)
ax.text(_am_time_x, _am_head_y, "çalışma süresi", ha="left", va="center", fontsize=9,
color=COL_SLATE_500, weight="bold", zorder=6)
_am_rows = [
{"icon": _am_icon_dag, "name": "DAG RELAXATION", "lesson": "bu ders · L11",
"cons": "çizge DAG (çevrim yok)\nağırlık ∈ ℤ — negatif OK", "time": "O(V + E)",
"time_tag": "doğrusal", "highlight": True},
{"icon": _am_icon_general, "name": "BELLMAN-FORD", "lesson": "Ders 18 · L12",
"cons": "kısıt YOK — genel çizge\nnegatif çevrimi TESPİT eder (δ = −∞)",
"time": "O(V · E)", "time_tag": "en genel · en yavaş", "highlight": False},
{"icon": _am_icon_noneg, "name": "DIJKSTRA", "lesson": "Ders 19 · L13",
"cons": "ağırlık ≥ 0 (negatif yok)", "time": "O(V log V + E)",
"time_tag": "doğrusala yakın", "highlight": False},
]
for _r, _row in enumerate(_am_rows):
_y = _am_row_y[_r]
if _row["highlight"]:
_bfc, _bec, _blw = COL_AMBER_100, COL_ACCENT, 2.6
else:
_bfc, _bec, _blw = COL_BG, COL_SLATE_400, 1.4
ax.add_patch(FancyBboxPatch(
(_am_pano_l, _y - _am_row_h * 0.5), _am_pano_r - _am_pano_l, _am_row_h,
boxstyle="round,pad=0.02,rounding_size=0.06", fc=_bfc, ec=_bec, linewidth=_blw,
zorder=2, alpha=0.95))
_row["icon"](ax, _am_icon_x, _y)
_name_col = COL_AMBER_700 if _row["highlight"] else COL_TEXT
ax.text(_am_name_x, _y + 0.13, _row["name"], ha="left", va="center", fontsize=10.5,
color=_name_col, weight="bold", zorder=5)
ax.text(_am_name_x, _y - 0.18, _row["lesson"], ha="left", va="center", fontsize=7.8,
color=COL_SLATE_500, style="italic", zorder=5)
ax.text(_am_cons_x, _y, _row["cons"], ha="left", va="center", fontsize=8.3,
color=COL_TEXT, zorder=5)
_time_col = COL_AMBER_700 if _row["highlight"] else COL_PRIMARY
ax.text(_am_time_x, _y + 0.13, _row["time"], ha="left", va="center", fontsize=11,
color=_time_col, weight="bold", family="monospace", zorder=5)
ax.text(_am_time_x, _y - 0.18, _row["time_tag"], ha="left", va="center", fontsize=7.8,
color=COL_SLATE_500, style="italic", zorder=5)
ax.text(_am_pano_r - 0.10, _am_row_y[0] + _am_row_h * 0.5 - 0.02, "bu ders", ha="right",
va="top", fontsize=7.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text((_am_pano_l + _am_pano_r) * 0.5, _am_row_y[-1] - _am_row_h * 0.5 - 0.34,
"genel SSSP'yi DOĞRUSAL zamanda çözmek hâlâ AÇIK PROBLEM · "
"çoğu gerçek problem (yol ağı, mesafe) negatif ağırlık içermez → Dijkstra en yaygın",
ha="center", va="center", fontsize=8.2, color=COL_SLATE_500, style="italic", zorder=6)
fig.suptitle(
"Ağırlıklı SSSP: üç algoritma, üç kısıt seviyesi — kısıt azaldıkça süre doğrusaldan uzaklaşır",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
ax.set_xlim(-0.05, 10.55)
ax.set_ylim(_am_row_y[-1] - _am_row_h * 0.5 - 0.70, 3.05 + 2.2 * 1.55 + 1.05)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 7. En Kısa Yol Ağacı: Mesafeden Ebeveyn {#sec-7-en-kisa-yol-agaci-mesafeden-ebeveyn}
BFS gibi iki şey döndürürüz: mesafeler $\delta$ ve ebeveyn işaretçileri (en kısa yol ağacı). Ama ikisini de her algoritmada taşımak angaryadır. **İddia:** yalnızca mesafeler verilirse, ebeveyn işaretçileri **doğrusal zamanda** geri kurulabilir.
> *"distances are actually sufficient for us to reconstruct parent pointers if we need them later."* — Ku, 28:57
Algoritma (yalnız $\delta$ sonlu olan $v$'ler için): her $u$ için, her $v \in \text{Adj}^{+}(u)$: $v$'ye henüz ebeveyn atanmamışsa **ve** $\delta(s, v) = \delta(s, u) + w(u, v)$ ise (bu kenar bir en kısa yolun parçası), $P(v) = u$ ata. Tüm düğümler + komşular üzerinde bir geçiş → $O(V + E)$. Bu yüzden bundan sonra yalnızca **mesafeleri** hesaplamaya odaklanırız.
@fig-parents-from-d bu fikri üç blokta gösterir: solda yalnız $\delta$ tablosu (figürün tek girdisi), ortada kontrol kuralı ($\delta(h)=6=\delta(g)+1$ ✓, $\delta(h)=6\neq\delta(f)+8=11$ ✗), sağda kurulan en kısa yol ağacı (ebeveyn kenarları kalın).
```{python}
#| label: fig-parents-from-d
#| fig-cap: "Mesafe YETER: en kısa yol ağacı yalnızca δ tablosundan kurulur (L11 §7, İMZA figür). SOL blok: yalnız δ(e,·) tablosu (figürün TEK girdisi) — e:0, f:3, g:5, h:6, d:3, c:8; a, b ∞ (erişilmez köşeler soluk). ORTA blok: kontrol kuralı — her (u,v) kenarı için δ(v) = δ(u)+w(u,v) mi? EŞİTSE bu kenar bir en kısa yolun parçası → P(v)=u. İki örnek: δ(h)=6 = δ(g)+1 = 5+1 ✓ (P(h)=g, yeşil onay); δ(h)=6 ≠ δ(f)+8 = 11 ✗ (f→h en kısa yolda DEĞİL, üstü çizili). SAĞ blok: kurulan en kısa yol ağacı — ebeveyn kenarları KALIN slate ok (f←e, g←f, h←g, d←g, c←d); en kısa yola katılmayan kenar (f→h) soluk; erişilmez a→b soluk. Alt not: tek geçiş O(V+E) — bu yüzden TÜM en kısa yol algoritmaları yalnız MESAFEYE odaklanır; ebeveynler δ'dan ücretsizce kurulur. Veri MOTORDAN: parents_from_distances → f←e, g←f, h←g, d←g, c←d (Ku 28:57)."
#| fig-width: 11.0
#| fig-height: 6.2
# fig-parents-from-d (L11 §7 İMZA): mesafe yeter — ebeveyn δ'dan kurulur.
# Veri MOTORDAN (build_weighted_dag_example / dag_relaxation / parents_from_distances).
_PF_POS = {
"e": (0.0, 1.0), "f": (1.0, 1.0), "g": (2.0, 1.0),
"h": (3.0, 1.6), "d": (3.0, 0.4), "c": (4.0, 0.4),
"a": (0.0, 2.2), "b": (1.0, 2.2),
}
_PF_R = 0.26
_PF_EDGES = [
("e", "f", 3), ("f", "h", 8), ("f", "g", 2),
("g", "h", 1), ("g", "d", -2), ("d", "c", 5), ("a", "b", 1),
]
def _pf_fmt(val):
return "∞" if val == INF else str(val)
def _pf_table(ax, x0, y0, d, order):
row_h, col_w = 0.46, 1.55
ax.text(x0 + col_w * 0.5, y0 + row_h * 0.5, "δ(e, ·) — TEK girdi", ha="center",
va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=6)
for k, v in enumerate(order):
y = y0 - (k + 1) * row_h
reachable = d[v] != INF
if reachable:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 1.8, COL_AMBER_700
else:
fc, ec, lw, tcol = COL_WHITE, COL_SLATE_400, 1.0, COL_SLATE_400
ax.add_patch(FancyBboxPatch(
(x0, y), col_w, row_h * 0.92, boxstyle="round,pad=0.01,rounding_size=0.04",
fc=fc, ec=ec, linewidth=lw, zorder=3))
ax.text(x0 + col_w * 0.30, y + row_h * 0.46, v, ha="center", va="center",
fontsize=11, color=tcol, weight="bold", zorder=5)
ax.text(x0 + col_w * 0.72, y + row_h * 0.46, _pf_fmt(d[v]), ha="center",
va="center", fontsize=11, color=tcol, weight="bold", zorder=5)
y_bot = y0 - (len(order) + 1) * row_h - 0.16
ax.text(x0 + col_w * 0.5, y_bot, "a, b: e'den erişilmez (∞)", ha="center",
va="center", fontsize=7.8, color=COL_SLATE_500, style="italic", zorder=5)
def _pf_check(ax, x0, y_top, d, w):
box_w, box_h = 4.55, 3.50
ax.add_patch(FancyBboxPatch(
(x0, y_top - box_h), box_w, box_h, boxstyle="round,pad=0.04,rounding_size=0.08",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.6, zorder=2))
cx = x0 + 0.28
ax.text(cx, y_top - 0.40, "KONTROL KURALI", ha="left", va="center", fontsize=10.5,
color=COL_TEXT, weight="bold", zorder=5)
ax.text(cx, y_top - 0.86, r"her $(u,v)$ kenarı için:", ha="left", va="center",
fontsize=9.5, color=COL_TEXT, zorder=5)
ax.text(cx, y_top - 1.26, r"$\delta(v) = \delta(u) + w(u,v)$ ?", ha="left",
va="center", fontsize=11, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(cx, y_top - 1.70, "EŞİTSE → bu kenar bir en kısa yolun parçası → P(v) = u",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700, weight="bold", zorder=5)
ax.plot([cx - 0.05, x0 + box_w - 0.28], [y_top - 1.98, y_top - 1.98],
color=COL_SLATE_400, linewidth=0.8, alpha=0.5, zorder=3)
dh, dg, df = d["h"], d["g"], d["f"]
w_gh, w_fh = w[("g", "h")], w[("f", "h")]
y1 = y_top - 2.36
ax.add_patch(FancyBboxPatch(
(cx - 0.08, y1 - 0.16), box_w - 0.46, 0.40, boxstyle="round,pad=0.02,rounding_size=0.05",
fc=COL_OK_BG, ec=COL_OK, linewidth=1.6, zorder=3))
ax.text(cx + 0.04, y1 + 0.04,
r"$\delta(h){=}%d = \delta(g){+}1 = %d{+}%d$" % (dh, dg, w_gh),
ha="left", va="center", fontsize=9.5, color=COL_OK, weight="bold", zorder=5)
ax.text(cx + 2.95, y1 + 0.04, "✓ P(h) = g", ha="left", va="center", fontsize=9.5,
color=COL_OK, weight="bold", zorder=5)
y2 = y_top - 2.92
ax.add_patch(FancyBboxPatch(
(cx - 0.08, y2 - 0.16), box_w - 0.46, 0.40, boxstyle="round,pad=0.02,rounding_size=0.05",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.2, zorder=3))
ax.text(cx + 0.04, y2 + 0.04,
r"$\delta(h){=}%d \neq \delta(f){+}8 = %d$" % (dh, df + w_fh),
ha="left", va="center", fontsize=9.5, color=COL_SLATE_500, zorder=5)
ax.text(cx + 2.95, y2 + 0.04, "✗ f→h SP'de değil", ha="left", va="center",
fontsize=9.0, color=COL_SLATE_500, zorder=5)
ax.plot([cx + 0.04, cx + 1.92], [y2 + 0.04, y2 + 0.04], color=COL_SLATE_500,
linewidth=1.1, alpha=0.85, zorder=6)
def _pf_tree(ax, ox, oy, scale, d, parent):
def P(node):
gx, gy = _PF_POS[node]
return ox + gx * scale, oy + gy * scale
parent_edges = {(parent[v], v) for v in parent if parent[v] is not None}
ax.text(ox + 2.0 * scale, oy + 2.2 * scale + 0.50, "KURULAN EN KISA YOL AĞACI",
ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=6)
for u, v, wt in _PF_EDGES:
ux, uy = P(u)
vx, vy = P(v)
is_parent = (u, v) in parent_edges
reachable = d.get(u, INF) != INF and d.get(v, INF) != INF
if is_parent:
col, lw, z, alpha = COL_PRIMARY, 3.0, 4, 1.0
elif reachable:
col, lw, z, alpha = COL_SLATE_400, 1.4, 2, 0.65
else:
col, lw, z, alpha = COL_SLATE_400, 1.2, 1, 0.40
shrink = _PF_R * scale * 100.0
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=14, color=col,
linewidth=lw, alpha=alpha, shrinkA=shrink, shrinkB=shrink, zorder=z))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
is_neg = wt < 0
if is_parent:
bfc, bec, btc = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
elif is_neg:
bfc, bec, btc = COL_AMBER_100, COL_AMBER_600, COL_AMBER_700
else:
bfc, bec, btc = COL_WHITE, COL_SLATE_400, COL_SLATE_500
ax.add_patch(Circle((mx, my), 0.115, facecolor=bfc, edgecolor=bec, linewidth=1.4,
zorder=6, alpha=alpha if not is_parent else 1.0))
ax.text(mx, my, str(wt), ha="center", va="center", fontsize=7.2, color=btc,
weight="bold", zorder=7, alpha=alpha if not is_parent else 1.0)
for node, (gx, gy) in _PF_POS.items():
x, y = P(node)
reachable = d.get(node, INF) != INF
if node == "e":
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 3.0, COL_AMBER_700
elif reachable:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 2.0, COL_TEXT
else:
fc, ec, lw, tcol = COL_WHITE, COL_SLATE_400, 1.2, COL_SLATE_400
ax.add_patch(Circle((x, y), _PF_R, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=5))
ax.text(x, y, node, ha="center", va="center", fontsize=11, color=tcol,
weight="bold", zorder=6)
ex, ey = P("e")
ax.text(ex, ey - _PF_R - 0.13, "kaynak", ha="center", va="top", fontsize=8,
color=COL_AMBER_700, weight="bold", zorder=6)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_pf_adj, _pf_w, _pf_topo = build_weighted_dag_example()
_pf_d = dag_relaxation(_pf_adj, _pf_w, "e", _pf_topo)
_pf_p = parents_from_distances(_pf_adj, _pf_w, "e", _pf_d)
assert _pf_d == {"a": INF, "b": INF, "e": 0, "f": 3, "g": 5,
"h": 6, "d": 3, "c": 8}, _pf_d
assert _pf_p["f"] == "e" and _pf_p["g"] == "f" and _pf_p["h"] == "g", _pf_p
assert _pf_p["d"] == "g" and _pf_p["c"] == "d", _pf_p
assert _pf_d["h"] == _pf_d["g"] + _pf_w[("g", "h")], (_pf_d["h"], _pf_d["g"]) # 6 = 5+1
assert _pf_d["h"] != _pf_d["f"] + _pf_w[("f", "h")], (_pf_d["h"], _pf_d["f"]) # 6 ≠ 11
fig, ax = plt.subplots(figsize=(11.0, 6.2))
fig.patch.set_facecolor(COL_WHITE)
_pf_table(ax, x0=0.10, y0=4.30, d=_pf_d, order=["e", "f", "g", "h", "d", "c", "a", "b"])
_pf_check(ax, x0=2.05, y_top=4.30, d=_pf_d, w=_pf_w)
_pf_tree(ax, ox=7.30, oy=0.60, scale=0.92, d=_pf_d, parent=_pf_p)
ax.add_patch(FancyArrowPatch(
(1.78, 2.55), (2.02, 2.55), arrowstyle="-|>", mutation_scale=16,
color=COL_AMBER_600, linewidth=2.4, zorder=6))
ax.add_patch(FancyArrowPatch(
(6.68, 2.55), (7.05, 2.55), arrowstyle="-|>", mutation_scale=16,
color=COL_AMBER_600, linewidth=2.4, zorder=6))
fig.suptitle(
"Mesafe YETER: en kısa yol ağacı yalnızca δ tablosundan kurulur",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975)
ax.text(5.70, -0.28,
"tek geçiş O(V + E) — bu yüzden TÜM en kısa yol algoritmaları yalnız MESAFEYE "
"odaklanır; ebeveynler δ'dan ücretsizce kurulur (Ku 28:57)",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500, style="italic", zorder=6)
ax.set_xlim(-0.15, 11.35)
ax.set_ylim(-0.55, 5.05)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 8. DAG Relaxation: Mesafe Tahminleri ve Üçgen Eşitsizliği {#sec-8-dag-relaxation-tahminler-ucgen}
Fikir: her $v$ için bir **mesafe tahmini** $d(s, v)$ tut; başta $+\infty$ (kaynak için 0). Değişmez: tahmin daima $\delta$'yı **yukarıdan sınırlar** (üst sınır); bilgi geldikçe **kademeli olarak düşür**.
> *"we're going to maintain that they upper-bound this thing and gradually lower until they're equal."* — Ku, 38:20
Ne zaman düşürürüz? Tahmin **üçgen eşitsizliğini (triangle inequality)** ihlal ettiğinde. Üçgen eşitsizliği: herhangi bir $x$ için $\delta(u, v) \leq \delta(u, x) + \delta(x, v)$ (yolları $x$'ten geçenlerle kısıtlamak minimumu küçültemez).
> *"the shortest path distance from u to v can't be bigger than... from u to x plus... from x to v."* — Ku, 41:07
**Kenar gevşetme (relax).** Bir $(u, v)$ kenarı için $d(s, v) > d(s, u) + w(u, v)$ ise (yani $u$ üzerinden $v$'ye gitmek mevcut tahminden iyiyse), tahmini düşür: $d(s, v) \leftarrow d(s, u) + w(u, v)$. "Relax" tarihsel bir terimdir; ihlal edilen bir kısıtı *yerel olarak* çözer (başka yerde yeni ihlal doğabilir, ama bu kısıt artık sağlanır).
## 9. Relax Güvenlidir {#sec-9-relax-guvenlidir}
Gevşetme **güvenlidir (safe):** her mesafe tahmini $d(s, v)$ daima ya $+\infty$'dur ya da $s$'den $v$'ye **gerçek bir yolun ağırlığıdır** — asla "uydurma" bir değer değil.
> *"each distance estimate s, v is weight of some path from s to v or infinite."* — Ku, 45:17
Kanıt (kısa): $(u, v)$'yi gevşetirken $d(s, v) \leftarrow d(s, u) + w(u, v)$. Varsayımla $d(s, u)$ zaten $s$'den $u$'ya bir yolun ağırlığıydı; ona $u \to v$ kenarını eklersek sonuç yine $s$'den $v$'ye bir yolun ağırlığıdır. Değişmez korunur. Bu yüzden tahmin hiçbir zaman gerçek en kısa mesafenin altına inmez — yalnızca ona yaklaşır.
@fig-triangle-relax bu iki temeli yan yana koyar: solda üçgen eşitsizliği $\delta(u,v) \leq \delta(u,x) + \delta(x,v)$, sağda relax öncesi/sonrası — $d(v)=12$ üstü çizili, $d(u)+w = 5+4 = 9$ amber yeni değer.
```{python}
#| label: fig-triangle-relax
#| fig-cap: "Gevşetme (relax) GÜVENLİDİR — üçgen eşitsizliği + tahmin asla δ'nın altına inmez (L11 §8-9, İMZA figür). SOL panel ÜÇGEN EŞİTSİZLİĞİ (§8): üç düğüm u, x, v üçgen yerleşim; alt düz kenar = doğrudan en kısa yol δ(u,v), üstte iki kenarlı kırık yol δ(u,x) + δ(x,v) kesikli. Eşitsizlik kutusu δ(u,v) ≤ δ(u,x) + δ(x,v); not: x'ten geçmeye ZORLAMAK minimumu KÜÇÜLTEMEZ. SAĞ panel RELAX (§9, öncesi/sonrası): mini durum s →(d(u)=5) u →(w(u,v)=4) v; eski d(v)=12 üstü çizili (soluk), yeni d(u)+w = 5+4 = 9 amber. Koşul kutusu d(v) > d(u)+w(u,v) ise DÜŞÜR (12 > 9 → evet, relax_edge = True). GÜVENLİ rozeti (yeşil): her d(v) tahmini ya ∞ ya GERÇEK bir yolun ağırlığıdır → asla çok-küçük uydurma değer üretilmez → d(v) hiçbir zaman δ(s,v)'nin altına inmez. Alt not: 'relax' tarihsel terim, ihlal edilen kısıtı yerel çözer. Veri MOTORDAN: relax_edge(d={s:0,u:5,v:12}, w(u,v)=4) → d(v) 12→9 (5+4) True; ikinci çağrı False (Ku 41:07 + 45:17)."
#| fig-width: 11.0
#| fig-height: 6.0
# fig-triangle-relax (L11 §8-9 İMZA): üçgen eşitsizliği + relax güvenli.
# Veri MOTORDAN (relax_edge / path_weight). networkx YOK — elle koordinat.
_TR_R = 0.34
def _tr_node(ax, x, y, label, src=False):
fc = COL_AMBER_100 if src else COL_BG
ec = COL_ACCENT if src else COL_PRIMARY
lw = 3.0 if src else 2.2
ax.add_patch(Circle((x, y), _TR_R, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=5))
ax.text(x, y, label, ha="center", va="center", fontsize=15,
color=COL_AMBER_700 if src else COL_TEXT, weight="bold", zorder=6)
def _tr_triangle(ax):
pu = (0.55, 0.65)
pv = (3.55, 0.65)
px = (2.05, 3.05)
ax.add_patch(FancyArrowPatch(
pu, pv, arrowstyle="-|>", mutation_scale=17, color=COL_PRIMARY, linewidth=3.0,
shrinkA=_TR_R * 70, shrinkB=_TR_R * 70, zorder=3))
ax.text((pu[0] + pv[0]) * 0.5, pu[1] - 0.46, "δ(u, v) — doğrudan en kısa yol",
ha="center", va="center", fontsize=10, color=COL_PRIMARY, weight="bold", zorder=6)
for a, b in ((pu, px), (px, pv)):
ax.add_patch(FancyArrowPatch(
a, b, arrowstyle="-|>", mutation_scale=15, color=COL_SLATE_500, linewidth=2.2,
shrinkA=_TR_R * 70, shrinkB=_TR_R * 70, zorder=2, linestyle=(0, (5, 2))))
ax.text((pu[0] + px[0]) * 0.5 - 0.42, (pu[1] + px[1]) * 0.5, "δ(u, x)", ha="right",
va="center", fontsize=9.5, color=COL_SLATE_500, weight="bold", zorder=6)
ax.text((px[0] + pv[0]) * 0.5 + 0.42, (px[1] + pv[1]) * 0.5, "δ(x, v)", ha="left",
va="center", fontsize=9.5, color=COL_SLATE_500, weight="bold", zorder=6)
_tr_node(ax, *pu, "u")
_tr_node(ax, *pv, "v")
_tr_node(ax, *px, "x")
bx, by, bw, bh = -0.10, -1.95, 4.35, 1.10
ax.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.05,rounding_size=0.10",
fc=COL_BG, ec=COL_ACCENT, linewidth=2.2, zorder=3))
ax.text(bx + bw * 0.5, by + bh - 0.34, r"$\delta(u,v)\ \leq\ \delta(u,x)\ +\ \delta(x,v)$",
ha="center", va="center", fontsize=15, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(bx + bw * 0.5, by + 0.30, "x'ten geçmeye ZORLAMAK minimumu KÜÇÜLTEMEZ",
ha="center", va="center", fontsize=9, color=COL_TEXT, style="italic", zorder=5)
ax.set_title("ÜÇGEN EŞİTSİZLİĞİ (§8)", color=COL_TEXT, fontsize=12.5, weight="bold", pad=12)
ax.set_xlim(-0.4, 4.5)
ax.set_ylim(-2.15, 3.95)
ax.set_aspect("equal")
ax.axis("off")
def _tr_relax(ax, d_before, d_after, du, w_uv):
ps = (0.50, 3.05)
pu = (2.55, 3.05)
pv = (4.60, 3.05)
ax.add_patch(FancyArrowPatch(
ps, pu, arrowstyle="-|>", mutation_scale=15, color=COL_PRIMARY, linewidth=2.4,
shrinkA=_TR_R * 66, shrinkB=_TR_R * 66, zorder=3))
ax.text((ps[0] + pu[0]) * 0.5, ps[1] + 0.42, f"d(u) = {du}", ha="center", va="center",
fontsize=9.5, color=COL_PRIMARY, weight="bold", zorder=6)
ax.add_patch(FancyArrowPatch(
pu, pv, arrowstyle="-|>", mutation_scale=15, color=COL_ACCENT, linewidth=2.8,
shrinkA=_TR_R * 66, shrinkB=_TR_R * 66, zorder=3))
ax.text((pu[0] + pv[0]) * 0.5, pu[1] + 0.42, f"w(u,v) = {w_uv}", ha="center",
va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6)
_tr_node(ax, *ps, "s", src=True)
_tr_node(ax, *pu, "u")
_tr_node(ax, *pv, "v")
vy = pv[1] - _TR_R - 0.30
ax.text(pv[0], vy, f"d(v) = {d_before}", ha="center", va="top", fontsize=11,
color=COL_SLATE_400, weight="bold", zorder=6)
ax.plot([pv[0] - 0.62, pv[0] + 0.62], [vy - 0.16, vy - 0.16], color=COL_SLATE_500,
linewidth=1.8, zorder=7)
ax.text(pv[0], vy - 0.46, f"d(u)+w = {du}+{w_uv} = {d_after}", ha="center", va="top",
fontsize=11.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.add_patch(FancyArrowPatch(
(pv[0] - 1.35, vy - 0.06), (pv[0] - 1.35, vy - 0.52), arrowstyle="-|>",
mutation_scale=15, color=COL_AMBER_600, linewidth=2.4, zorder=6))
ax.text(pv[0] - 1.55, vy - 0.29, "DÜŞÜR", ha="right", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold", style="italic", zorder=6)
cx, cy, cw, ch = 0.10, 0.55, 4.55, 0.92
ax.add_patch(FancyBboxPatch(
(cx, cy), cw, ch, boxstyle="round,pad=0.05,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=3))
ax.text(cx + cw * 0.5, cy + ch - 0.30, r"$d(v)\ >\ d(u) + w(u,v)$ ise DÜŞÜR",
ha="center", va="center", fontsize=12, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(cx + cw * 0.5, cy + 0.26,
f"{d_before} > {du}+{w_uv}={d_after} → evet, gevşet (relax_edge = True)",
ha="center", va="center", fontsize=9, color=COL_TEXT, zorder=5)
sx, sy, sw, sh = 0.10, -1.20, 4.55, 1.40
ax.add_patch(FancyBboxPatch(
(sx, sy), sw, sh, boxstyle="round,pad=0.05,rounding_size=0.10",
fc=COL_OK_BG, ec=COL_OK, linewidth=2.2, zorder=3))
ax.text(sx + 0.22, sy + sh - 0.28, "✓ GÜVENLİ", ha="left", va="center", fontsize=11.5,
color=COL_OK, weight="bold", zorder=5)
ax.text(sx + 0.22, sy + sh - 0.66, "her d(v) tahmini ya ∞ ya GERÇEK bir yolun ağırlığıdır",
ha="left", va="center", fontsize=9, color=COL_TEXT, zorder=5)
ax.text(sx + 0.22, sy + sh - 0.98, "asla çok-küçük uydurma değer üretilmez", ha="left",
va="center", fontsize=9, color=COL_TEXT, zorder=5)
ax.text(sx + 0.22, sy + 0.22, "⇒ d(v) hiçbir zaman δ(s,v)'nin altına inmez", ha="left",
va="center", fontsize=9.5, color=COL_OK, weight="bold", style="italic", zorder=5)
ax.set_title("RELAX GÜVENLİ (§9)", color=COL_TEXT, fontsize=12.5, weight="bold", pad=12)
ax.set_xlim(-0.4, 5.1)
ax.set_ylim(-1.45, 3.95)
ax.set_aspect("equal")
ax.axis("off")
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_tr_du, _tr_w_uv = 5, 4
_tr_d = {"s": 0, "u": _tr_du, "v": 12}
_tr_weight = {("u", "v"): _tr_w_uv}
_tr_before = _tr_d["v"]
_tr_relaxed = relax_edge(_tr_d, _tr_weight, "u", "v")
_tr_after = _tr_d["v"]
_tr_again = relax_edge(_tr_d, _tr_weight, "u", "v")
assert _tr_relaxed is True, _tr_relaxed
assert _tr_after == _tr_du + _tr_w_uv == 9, (_tr_after, _tr_du, _tr_w_uv)
assert _tr_before == 12, _tr_before
assert _tr_again is False, _tr_again
_tr_tri = {("u", "x"): 2, ("x", "v"): 3, ("u", "v"): 6}
assert path_weight(_tr_tri, ["u", "x", "v"]) == 5
assert path_weight(_tr_tri, ["u", "v"]) == 6
fig, (_tr_axl, _tr_axr) = plt.subplots(1, 2, figsize=(11.0, 6.0))
fig.patch.set_facecolor(COL_WHITE)
_tr_triangle(_tr_axl)
_tr_relax(_tr_axr, _tr_before, _tr_after, _tr_du, _tr_w_uv)
fig.suptitle(
"Gevşetme (relax) GÜVENLİDİR — üçgen eşitsizliği + tahmin asla δ'nın altına inmez",
color=COL_TEXT, fontsize=13, weight="bold", y=0.99)
fig.text(0.5, 0.018,
"\"relax\" tarihsel terim: ihlal edilen kısıtı yerel olarak çözer "
"(gergin bir tahmini gerçeğe doğru gevşetir) · (Ku 41:07 + 45:17)",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500, style="italic")
plt.tight_layout(rect=(0.0, 0.045, 1.0, 0.95))
plt.show()
```
## 10. DAG Relaxation Algoritması ve Doğruluğu {#sec-10-dag-relaxation-algoritma-dogruluk}
Algoritma: tüm $d(s, v) = +\infty$; $d(s, s) = 0$; sonra düğümleri **topolojik sırada** işle, her $u$ için tüm çıkış komşularını gevşet.
> *"we're going to process each vertex u in a topological sort order."* — Ku, 48:30
```python
def dag_relaxation(adj, weight, s, topo_order):
d = {v: float('inf') for v in adj} # tahminler
d[s] = 0
for u in topo_order: # topolojik sirada
for v in adj[u]: # cikis komsulari
if d[u] + weight[(u, v)] < d[v]: # ucgen esitsizligi ihlali
d[v] = d[u] + weight[(u, v)] # relax (guvenli)
return d
```
**Çalışılan Örnek — e'den en kısa yollar.** Topolojik sıra $a, b, e, f, g, h, d, c$. $a$ ve $b$ kaynaktan ($e$) önce geldiğinden $\infty$ kalır ($e$'den onlara yol yok). $e = 0$. $e \to f$ kenarı (ağırlık 3): $d(f) = 3$. $f$'yi işle: $3+8 = 11$, $3+2 = 5$. $g$'yi işle: $5+1 = 6$ (11'i 6 ile değiştir), $5+(-2) = 3$. Devam... sonuçta $\delta$: $a=b=+\infty$, $e=0$, $f=3$, $g=5$, $h=6$, $d=3$, $c=8$.
**Doğruluk (topolojik tümevarım).** Topolojik sıradaki $k.$ düğüm $v$; ondan öncekiler doğru (tümevarım varsayımı). $s$'den $v$'ye en kısa yolda $v$'den hemen önceki $u$, topolojik sırada $v$'den önce gelmek zorundadır (yoksa DAG değil) → $u$ doğru hesaplanmıştır; $u$ işlenirken $(u, v)$ kenarı gevşetildiğinden $d(v)$ doğru en kısa mesafeye iner. Her düğüm + komşuları bir kez → $O(V + E)$ doğrusal.
@fig-dag-relaxation algoritmayı tek bir akışta gösterir: üstte ağırlıklı DAG, altta topolojik sıra şeridi ($a, b, e, f, g, h, d, c$) ve her düğümün altında $d$-tahmini evrimi — $h$'nin $\infty \to 11 \to 6$ geçişi imza an ($g$ işlenirken daha iyi yol bulunur).
```{python}
#| label: fig-dag-relaxation
#| fig-cap: "DAG relaxation: ∞'dan başla, topolojik sırada gevşet — h ∞→11→6 (g daha iyi yol bulur) (L11 §10, İMZA figür). ÜST: örnek ağırlıklı DAG (kaynak e); kenar ağırlıkları rozette, g→d(−2) negatif amber (DAG'da sorun değil); a, b ayrık üst köşe (e'den erişilmez, soluk). ALT: topolojik sıra işleme şeridi a, b, e, f, g, h, d, c (soldan sağa, #1..#8 rozeti). a, b soluk + 'd = ∞ kaldı' (erişilmez). e = 0 (kaynak). Her düğümün altında d-tahmini evrimi mini sütun: f ∞→3; g ∞→5; h ∞→11→6 (11 üstü çizili, 6 amber — KLİMAKS: g işlenirken daha iyi yol! d[g]+w(g,h)=5+1=6 < 11); d ∞→3; c ∞→8. Alt not: topolojik sıra garantisi — bir düğüm işlenirken TÜM öncülleri zaten DOĞRU (tümevarım), tek geçiş yeter → O(V+E); negatif ağırlık (g→d=−2) sorun değil, çevrim olmadığından her kenar tek kez gevşetilir, −∞ tuzağı yok. Veri MOTORDAN: topo = [a,b,e,f,g,h,d,c]; dag_relaxation(e) = {a:∞,b:∞,e:0,f:3,g:5,h:6,d:3,c:8}; g adımı relaxed = [(h,11,6),(d,∞,3)] (Ku 48:30)."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-dag-relaxation (L11 §10 İMZA): topolojik sırada gevşet, h ∞→11→6 klimaks.
# Veri MOTORDAN (build_weighted_dag_example / dag_relaxation_trace / dag_relaxation).
_DG_POS = {
"e": (0.0, 1.0), "f": (1.0, 1.0), "g": (2.0, 1.0),
"h": (3.0, 1.6), "d": (3.0, 0.4), "c": (4.0, 0.4),
"a": (0.0, 2.2), "b": (1.0, 2.2),
}
_DG_EDGES = [
("e", "f", 3, False), ("f", "h", 8, False), ("f", "g", 2, False),
("g", "h", 1, False), ("g", "d", -2, True), ("d", "c", 5, False),
("a", "b", 1, False),
]
_DG_UNREACH = {"a", "b"}
_DG_R = 0.26
_DG_EVOL = {
"f": ["∞", "3"], "h": ["∞", "11", "6"], "g": ["∞", "5"],
"d": ["∞", "3"], "c": ["∞", "8"],
}
def _dg_draw_dag(ax, source):
for u, v, wt, neg in _DG_EDGES:
ux, uy = _DG_POS[u]
vx, vy = _DG_POS[v]
dim = (u in _DG_UNREACH or v in _DG_UNREACH)
ecol = COL_SLATE_400 if dim else (COL_ACCENT if neg else COL_PRIMARY)
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=15, color=ecol,
linewidth=2.4 if neg else 2.0, shrinkA=_DG_R * 78, shrinkB=_DG_R * 78,
alpha=0.45 if dim else 1.0, zorder=2))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
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.155, my - 0.13), 0.31, 0.26, boxstyle="round,pad=0.01,rounding_size=0.06",
fc=bg, ec=ec, linewidth=1.7 if neg else 1.1, alpha=0.45 if dim else 1.0, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center", fontsize=8.5 if not neg else 9,
color=tcol, weight="bold", alpha=0.5 if dim else 1.0, zorder=7)
for v, (x, y) in _DG_POS.items():
dim = (v in _DG_UNREACH)
is_src = (v == source)
fc = COL_AMBER_100 if is_src else COL_BG
ec = COL_ACCENT if is_src else (COL_SLATE_400 if dim else COL_PRIMARY)
lw = 3.0 if is_src else (1.4 if dim else 2.0)
ax.add_patch(Circle((x, y), _DG_R, facecolor=fc, edgecolor=ec, linewidth=lw,
alpha=0.5 if dim else 1.0, zorder=5))
tcol = COL_AMBER_700 if is_src else (COL_SLATE_400 if dim else COL_TEXT)
ax.text(x, y, v, ha="center", va="center", fontsize=12.5, color=tcol,
weight="bold", alpha=0.6 if dim else 1.0, zorder=6)
sx, sy = _DG_POS[source]
ax.text(sx - _DG_R - 0.10, sy - 0.02, "kaynak", ha="right", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(0.5, 2.78, "a, b — e'den erişilemez (ayrık)", ha="center", va="center",
fontsize=8, color=COL_SLATE_400, style="italic", zorder=6)
ax.text(2.5, 0.02, "g→d ağırlığı −2 (negatif — DAG'da sorun değil)", ha="center",
va="center", fontsize=8, color=COL_AMBER_700, style="italic", zorder=6)
ax.text(2.0, 3.18, "Ağırlıklı DAG (w: E → ℤ, kaynak e)", ha="center", va="center",
fontsize=11, color=COL_PRIMARY, weight="bold", zorder=6)
def _dg_evolution(ax, cx, top_y, seq, climax=False):
step = 0.30
n = len(seq)
for i, val in enumerate(seq):
y = top_y - i * step
is_last = (i == n - 1)
struck = climax and (i == n - 2)
if is_last:
col, fs, wt = COL_AMBER_700, 11, "bold"
elif struck:
col, fs, wt = COL_SLATE_400, 9, "normal"
else:
col, fs, wt = COL_SLATE_500, 9, "normal"
ax.text(cx, y, val, ha="center", va="center", fontsize=fs, color=col,
weight=wt, zorder=6)
if struck:
half = 0.085 + 0.02 * len(val)
ax.plot([cx - half, cx + half], [y, y], color=COL_AMBER_700, linewidth=1.6, zorder=7)
if i < n - 1:
ya = top_y - i * step - 0.10
yb = top_y - (i + 1) * step + 0.10
ax.add_patch(FancyArrowPatch(
(cx, ya), (cx, yb), arrowstyle="-|>", mutation_scale=8,
color=COL_AMBER_600 if (climax and i == n - 2) else COL_SLATE_400,
linewidth=1.8 if (climax and i == n - 2) else 1.1, zorder=6))
if climax:
by = top_y - (n - 1) * step
ax.add_patch(FancyBboxPatch(
(cx + 0.18, by - 0.20), 1.72, 0.46, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=8))
ax.text(cx + 0.30, by + 0.07, "★ g işlenirken daha iyi yol!", ha="left", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=9)
ax.text(cx + 0.30, by - 0.12, "d[g]+w(g,h) = 5+1 = 6 < 11", ha="left", va="center",
fontsize=7.5, color=COL_AMBER_700, family="monospace", zorder=9)
def _dg_strip(ax, x0, y0, topo, source):
cell_w, cell_h, gap = 0.86, 0.70, 0.34
for k, node in enumerate(topo):
x = x0 + k * (cell_w + gap)
unreach = (node in _DG_UNREACH)
is_src = (node == source)
if is_src:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.6
elif unreach:
fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_SLATE_400, 1.2
else:
fc, ec, tcol, lw = COL_BG, COL_PRIMARY, COL_TEXT, 2.0
ax.add_patch(FancyBboxPatch(
(x, y0), cell_w, cell_h, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=fc, ec=ec, linewidth=lw, alpha=0.55 if unreach else 1.0, zorder=4))
cx, cy = x + cell_w * 0.5, y0 + cell_h * 0.5
ax.text(cx, cy, node, ha="center", va="center", fontsize=13, color=tcol,
weight="bold", alpha=0.6 if unreach else 1.0, zorder=5)
ax.text(cx, y0 + cell_h + 0.13, f"#{k + 1}", ha="center", va="center", fontsize=7.5,
color=COL_SLATE_500, weight="bold", zorder=5)
if k < len(topo) - 1:
ax.add_patch(FancyArrowPatch(
(x + cell_w, cy), (x + cell_w + gap, cy), arrowstyle="-|>",
mutation_scale=10, color=COL_SLATE_400, linewidth=1.4, zorder=3))
col_y = y0 - 0.30
if unreach:
ax.text(cx, col_y - 0.28, "d = ∞", ha="center", va="center", fontsize=9.5,
color=COL_SLATE_500, weight="bold", zorder=5)
ax.text(cx, col_y - 0.58, "(∞ kaldı)", ha="center", va="center", fontsize=7.5,
color=COL_SLATE_400, style="italic", zorder=5)
continue
if is_src:
ax.text(cx, col_y - 0.28, "d = 0", ha="center", va="center", fontsize=9.5,
color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(cx, col_y - 0.58, "(kaynak)", ha="center", va="center", fontsize=7.5,
color=COL_SLATE_500, style="italic", zorder=5)
continue
_dg_evolution(ax, cx, col_y, _DG_EVOL[node], climax=(node == "h"))
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_dg_adj, _dg_w, _dg_topo = build_weighted_dag_example()
_dg_tr = dag_relaxation_trace(_dg_adj, _dg_w, "e", _dg_topo)
_dg_d = _dg_tr["d"]
_dg_direct = dag_relaxation(_dg_adj, _dg_w, "e", _dg_topo)
assert _dg_direct == _dg_d, (_dg_direct, _dg_d)
assert _dg_topo == ["a", "b", "e", "f", "g", "h", "d", "c"], _dg_topo
assert _dg_d == {"a": INF, "b": INF, "e": 0, "f": 3, "g": 5,
"h": 6, "d": 3, "c": 8}, _dg_d
_dg_g = next(s for s in _dg_tr["steps"] if s["u"] == "g")
assert _dg_g["relaxed"] == [("h", 11, 6), ("d", INF, 3)], _dg_g["relaxed"]
assert _DG_EVOL["h"] == ["∞", "11", "6"], _DG_EVOL["h"]
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
_dg_draw_dag(ax, source="e")
_dg_strip_x0, _dg_strip_y0 = 0.55, -1.35
ax.text(_dg_strip_x0 - 0.10, _dg_strip_y0 + 1.00,
"DAG RELAXATION — düğümleri TOPOLOJİK SIRADA işle, çıkış kenarlarını "
"gevşet (üçgen ihlalinde tahmin düşür)", ha="left", va="center", fontsize=9.5,
color=COL_AMBER_700, weight="bold", zorder=6)
_dg_strip(ax, _dg_strip_x0, _dg_strip_y0, _dg_topo, "e")
_dg_note_y = _dg_strip_y0 - 2.60
ax.text(_dg_strip_x0 - 0.10, _dg_note_y,
"Topolojik sıra garantisi: bir düğüm işlenirken TÜM öncülleri zaten DOĞRU "
"(tümevarım) — tek geçiş yeter → O(V + E)", ha="left", va="center", fontsize=9,
color=COL_TEXT, weight="bold", zorder=6)
ax.text(_dg_strip_x0 - 0.10, _dg_note_y - 0.34,
"negatif ağırlık (g→d = −2) sorun değil; çevrim olmadığı için her kenar tek kez "
"gevşetilir, −∞ tuzağı yok (Ku L11 §10)", ha="left", va="center", fontsize=8.4,
color=COL_SLATE_500, style="italic", zorder=6)
fig.suptitle(
"DAG relaxation: ∞'dan başla, topolojik sırada gevşet — h ∞→11→6 (g daha iyi yol bulur)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.set_xlim(-0.4, 11.2)
ax.set_ylim(_dg_note_y - 0.75, 3.45)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d16}
1. **Ağırlık** $w: E \to \mathbb{Z}$; **yol ağırlığı** = kenar ağırlıkları toplamı; **en kısa yol** = minimum ağırlık.
2. **İki tuzak**: yol yoksa $\delta = +\infty$; **negatif ağırlıklı çevrim** erişiliyorsa $\delta = -\infty$.
3. **BFS özel durumları**: ağırlık 1 / aynı pozitif / küçük-toplamlı seri açma → doğrusal.
4. **Algoritma haritası**: DAG → $O(V+E)$; Bellman-Ford → $O(V \cdot E)$; Dijkstra (negatif yok) → $O(V \log V + E)$.
5. **Mesafe yeter**: ebeveyn işaretçileri $\delta$'dan $O(V+E)$'de kurulur.
6. **DAG relaxation**: $d$ tahmini $\infty$'dan başlar, üçgen eşitsizliği ihlalinde gevşet; relax **güvenli**.
7. **Doğruluk**: topolojik sırada işle; tümevarımla tüm $d = \delta$; $O(V + E)$.
::: {.callout-important title="Tek Bir Cümle"}
Ağırlıklı en kısa yol, toplam kenar ağırlığının minimumudur; bir DAG'da bunu, $\infty$'dan başlayan mesafe tahminlerini topolojik sırada üçgen eşitsizliğine göre güvenle gevşeterek $O(V + E)$'de tam olarak çözeriz.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d16}
::: {.callout-note collapse="true" title="Soru 1: Negatif ağırlıklı çevrim neden en kısa yolu tanımsız (−∞) yapar? +∞ durumundan farkı ne?"}
**Cevap:**
$+\infty$, $s$'den $t$'ye **hiç yol olmadığı** durumdur (erişilemez). $-\infty$ ise yol *vardır* ama **sonlu en kısa yol yoktur**: $s$'den $v$'ye giden yol negatif ağırlıklı bir çevrim üzerindeki bir düğümden geçiyorsa, o çevrimi her dolaştığımızda ağırlık azalır (örn. tur başına $-2$), bu yüzden istediğimiz kadar küçük bir değere inebiliriz. Minimum erişilemez → infimum $-\infty$. Bu yüzden negatif çevrim erişilen düğümler için ebeveyn ağacı kurmayız.
:::
::: {.callout-note collapse="true" title="Soru 2: Neden yalnızca mesafeleri (δ) hesaplayıp ebeveyn işaretçilerini sonradan kuruyoruz?"}
**Cevap:**
Çünkü her algoritmada ikisini birden taşımak gereksiz angaryadır ve mesafeler ebeveyni *belirlemeye yeter*. $\delta$ verilince, her $u$ için her çıkış komşusu $v$'yi tara; $\delta(s, v) = \delta(s, u) + w(u, v)$ ise $(u, v)$ bir en kısa yolun son kenarıdır, $P(v) = u$ ata. Tüm düğüm + komşu üzerinde bir geçiş $O(V+E)$ — algoritmanın kendi alt sınırı zaten doğrusal olduğundan ek maliyet yok. Böylece tüm en kısa yol algoritmaları tek bir işe (mesafe) odaklanır.
:::
::: {.callout-note collapse="true" title="Soru 3: “Kenar gevşetme güvenlidir” ne demek ve neden önemli?"}
**Cevap:**
Güvenli (safe) = her mesafe tahmini $d(s, v)$ daima ya $+\infty$'dur ya da $s$'den $v$'ye **gerçek bir yolun** ağırlığıdır; asla hiçbir yola karşılık gelmeyen bir sayı olamaz. Gevşetmede $d(s, v) \leftarrow d(s, u) + w(u, v)$ yaparız; $d(s, u)$ zaten bir yolun ağırlığıysa, $u \to v$ kenarını ekleyince yine bir yolun ağırlığı olur. Önemi: tahmin **hiçbir zaman gerçek en kısa mesafenin altına inemez** (çünkü bir yol var, en kısa yol ondan kısa olamaz) — yani algoritma yukarıdan $\delta$'ya doğru iner ve doğru değerde durur.
:::
::: {.callout-note collapse="true" title="Soru 4: DAG relaxation neden topolojik sıra gerektirir? Sıra olmasaydı ne bozulurdu?"}
**Cevap:**
Doğruluk, "bir düğümü işlerken tüm geçerli öncüllerinin (incoming neighbors) zaten doğru hesaplanmış olması"na dayanır. Topolojik sıra tam bunu garanti eder: $s \to v$ en kısa yolunda $v$'den önceki $u$, topolojik sırada $v$'den **önce** gelir (DAG olduğundan), dolayısıyla $u$ işlenirken $d(u) = \delta(s, u)$ olmuştur ve $(u, v)$ gevşetilince $d(v)$ doğru değere iner. Rastgele sırada bir düğümü öncülü hesaplanmadan işlersek, onu eksik bilgiyle bırakırız; ayrıca çevrim olsaydı topolojik sıra zaten var olmazdı (bu yüzden DAG şart).
:::
## Egzersizler {#sec-egzersizler-d16}
**Egzersiz 1.** Verilen küçük ağırlıklı çizgede, belirtilen kaynaktan tüm $\delta$ değerlerini elle DAG relaxation ile hesapla; topolojik sıra seçimini de göster.
**Egzersiz 2.** Bir negatif ağırlıklı çevrim içeren çizge çiz; hangi düğümlerin $\delta = -\infty$, hangilerinin sonlu olduğunu işaretle.
**Egzersiz 3.** Pozitif ağırlıkları seri kenarlara açma dönüşümünü küçük bir çizgede uygula; toplam ağırlık $V + E$'yi aşmazsa BFS'in doğrusal kaldığını argümanla göster.
**Egzersiz 4.** Yalnızca $\delta$ mesafeleri verilen bir çizgede ebeveyn işaretçilerini kuran fonksiyonu Python'da yaz; süresinin $O(V + E)$ olduğunu doğrula.
**Egzersiz 5.** DAG relaxation'ın üçgen eşitsizliği koşulunu, "en uzun yol" (longest path) bulacak şekilde değiştir; bunun neden yalnızca DAG'da anlamlı olduğunu açıkla.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d16}
::: {.callout-warning title="Sonraki: Ders 18 (L12) — Bellman-Ford (araya Ders 17 = PS5 girer)"}
**Ders 18 (L12): Bellman-Ford** (araya **Ders 17 = PS5** problem oturumu girer) — Jason Ku ile, DAG kısıtını kaldırıyoruz: *herhangi* bir çizgede (çevrim, hatta negatif ağırlıklı çevrim dahil) SSSP. Aynı "relax" tekniğini kullanır ama topolojik sıra olmadığından kenarları **tekrar tekrar** gevşetir; karesel-benzeri $O(V \cdot E)$ ama pratik. Negatif çevrimleri de tespit eder.
**Ders 18 Öncesi Yapılacak:**
- Bu dersin egzersizlerini, özellikle Egzersiz 1 (DAG relaxation) ve 2 (negatif çevrim) çöz.
- Üçgen eşitsizliği + relax-güvenli değişmezini ezberden anlat.
- Ana cümleyi tekrar oku: *"DAG relaxation: $\infty$'dan başla, topolojik sırada güvenle gevşet, $O(V+E)$'de bitir."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d16}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **Ağırlık fonksiyonu** | $w: E \to \mathbb{Z}$; $O(1)$ sorgu (tuple veya hash) | Böl. 1-2 |
| **Yol ağırlığı $w(\pi)$** | Yoldaki kenar ağırlıklarının toplamı | Böl. 3 |
| **En kısa yol $\delta(s,t)$** | Minimum ağırlıklı yol; yok → $+\infty$ | Böl. 3-4 |
| **Negatif çevrim** | Erişilen düğüm için $\delta = -\infty$ (infimum) | Böl. 4 |
| **Algoritma haritası** | DAG $O(V+E)$ / Bellman-Ford $O(V \cdot E)$ / Dijkstra $O(V \log V + E)$ | Böl. 6 |
| **Üçgen eşitsizliği** | $\delta(u,v) \leq \delta(u,x) + \delta(x,v)$ | Böl. 8 |
| **Relax $(u,v)$** | $d(s,v) > d(s,u)+w(u,v)$ ise düşür; güvenli | Böl. 8-9 |
| **DAG relaxation** | Topolojik sırada relax; $O(V+E)$ | Böl. 10 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d16}
::: {.callout-tip title="6 köprü"}
Bu ders, "ağırlık girince en kısa yol = toplam ağırlığın minimumu" sezgisini kurar ve DAG relaxation ile gevşetme tekniğini açar — köprülerin özeti:
1. **Ağırlıklı en kısa yol** → GPS/yönlendirme (Google Maps, Waze), ağ yönlendirme (OSPF latency), oyun yol bulma.
2. **DAG relaxation** → proje zamanlama (kritik yol, PERT/CPM), build sistemi süre tahmini, elektronik tablo hesap sırası.
3. **Üçgen eşitsizliği** → `A*` sezgisel araması, metrik uzaylar, yer gömme (embedding) kalitesi.
4. **Relax (gevşetme)** → kısıt çözme (constraint relaxation), iteratif optimizasyon, label-correcting algoritmalar.
5. **Negatif çevrim tespiti** → arbitraj (döviz çevrim grafı), kâr döngüsü, tutarsızlık tespiti.
6. **Topolojik sıra + DP** → DAG üzerinde dinamik programlama; en kısa/en uzun yol DP'nin habercisidir (Ders 23-26, L15-L18).
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
Kenarlara ağırlık verince "en kısa yol" toplam ağırlığın minimumu olur ve iki yeni tuzak doğar ($+\infty$ yol yok, $-\infty$ negatif çevrim). Bir DAG'da bu problemi, $\infty$'dan başlayan mesafe tahminlerini topolojik sırada üçgen eşitsizliğine göre **güvenle gevşeterek** $O(V + E)$'de çözeriz — ve mesafeler, ebeveyn işaretçilerini sonradan kurmaya yeter.
:::
