---
title: "Dijkstra"
subtitle: "Ağırlıklar negatif değilse mesafe en kısa yol boyunca artar; bu yüzden düğümleri bir öncelik kuyruğundan artan mesafe sırasında çekip kenarlarını gevşeterek tek-kaynak en kısa yolu çözeriz — değiştirilebilir öncelik kuyruğu decrease_key ile gevşeyen tahminleri günceller, BFS'in ağırlıklı genellemesi, neredeyse doğrusal O(V log V + E)"
---
::: {.callout-note title="Bölüm bilgisi"}
- **Ku'nun videosu:** [YouTube — Lecture 13: Dijkstra](https://www.youtube.com/watch?v=NSHizBK9JD8) (~57 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 13: Dijkstra](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-13-dijkstra/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 19 (L13)
- **Hoca:** Jason Ku (ağırlıklı en kısa yollar ünitesinin negatif-olmayan ağırlık için hızlı algoritması)
- **Okuma süresi:** ~26 dk
> Bir önceki ders (Ders 18) Bellman-Ford *herhangi* bir çizgede çalışıyordu ama $O(V \cdot E)$ — yoğun çizgede $O(V^3)$ — yavaştı. Bu ders, **ağırlıklar negatif değilse** çok daha hızlı bir algoritma verir: kaynaktan dışa **artan mesafe** sırasında ilerleyen Dijkstra, neredeyse doğrusal $O(V \log V + E)$.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d19}
Bellman-Ford (Ders 18) *herhangi* bir çizgede çalışıyordu ama $O(V \cdot E)$ (yoğun çizgede $O(V^3)$). Bu ders (Jason Ku), **ağırlıklar negatif değilse** çok daha hızlı bir algoritma verir: **Dijkstra**. Negatif çevrim derdi olmadığından, kaynaktan dışa **artan mesafe** sırasında ilerler ve $O(V \log V + E)$ — doğrusala yakın — süreye iner.
> *"If weights greater than or equal to 0, then distances increase along shortest paths."* — Ku, 8:35
Üç ana fikir:
1. **Negatif olmayan ağırlık → tekdüze mesafe** — en kısa yol boyunca mesafe azalmaz; bu, "kaynaktan dışa büyüyen küre" sezgisini mümkün kılar.
2. **Artan sıra bilinirse DAG relaxation** — düğümleri artan mesafe sırasında işleyebilseydik, çizgeyi bir DAG'a çevirip doğrusal çözerdik.
3. **Değiştirilebilir öncelik kuyruğu** — sıradaki en yakın düğümü verimlice bulmak için `decrease_key` destekli bir öncelik kuyruğu.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 19'un (L13) kavram haritası: kök = Dijkstra (Ku) — negatif olmayan ağırlıklı tek-kaynak en kısa yol, BFS'in ağırlıklı genellemesi. Beş dal — (1) Gözlem 1: ağırlık negatif değilse mesafe en kısa yol boyunca artar; kaynaktan dışa büyüyen küre sezgisi. (2) Gözlem 2: düğümlerin artan mesafe sırası bilinirse çizge bir DAG'a iner → DAG relaxation doğrusal çözer; sıfır ağırlıklı kenarlar birleştirilir. (3) değiştirilebilir öncelik kuyruğu: build, delete_min, decrease_key; id ile anahtarı düşür; öncelik kuyruğu (Ders 12) artı çapraz bağ sözlüğü. (4) algoritma artı doğruluk: en yakını çıkar, kenarları gevşet, decrease_key ile güncelle; gevşetme güvenli artı çıkınca delta. (5) öncelik kuyruğu seçimi süreleri belirler: dizi kare V, ikili yığın E log V, Fibonacci yığını E artı V log V. Sonuç: BFS'i ağırlıklı dünyaya taşır; sırrı tek gözlem, negatif yoksa mesafe artar."
flowchart TD
A["Ders 19 (L13): Dijkstra"] --> G1["Gözlem 1: mesafe ARTAR"]
G1 --> G1a["ağırlık ≥ 0 → en kısa yol boyunca<br/>mesafe azalmaz; dışa büyüyen küre"]
A --> G2["Gözlem 2: sıra bilinirse DAG"]
G2 --> G2a["artan mesafe sırası → DAG relaxation<br/>doğrusal; sıfır kenarı birleştir"]
A --> P["değiştirilebilir öncelik kuyruğu"]
P --> Pa["build · delete_min · decrease_key<br/>id ile anahtar düşür · Ders 12 + sözlük"]
A --> D["algoritma + doğruluk"]
D --> Da["en yakını çıkar → gevşet → decrease_key<br/>gevşetme güvenli + çıkınca δ"]
A --> T["öncelik kuyruğu seçimi → süre"]
T --> Ta["dizi V² · ikili yığın E log V<br/>Fibonacci yığını E + V log V"]
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 G1,G2,P,D,T branch
class G1a,G2a,Pa,Da,Ta leaf
```
::: {.callout-tip title="Builder Notu — Negatif Yoksa Açgözlülük Doğru"}
Bellman-Ford genel çizgeyi $O(V \cdot E)$'de çözüyordu. Dijkstra, ağırlıkların negatif olmadığı kabulüyle tek bir gözlemden güç alır: mesafe en kısa yol boyunca artar, dolayısıyla "en yakın düğümü kesinleştir, bir daha dokunma" açgözlü stratejisi doğrudur. Bedeli $V \cdot E$ değil, neredeyse doğrusal $O(V \log V + E)$'dir.
- **İleriye → GPS/yönlendirme:** Dijkstra, Google Maps/Waze ve ağ yönlendirmenin (OSPF link-state) çekirdek algoritmasıdır.
- **İleriye → sezgisel arama:** Dijkstra'ya sezgisel (heuristic) eklenince `A*` olur; oyun yol bulma ve robotik hareket planlamada standart.
- **İleriye → öncelik kuyruğu seçimi:** array (yoğun) vs binary heap (seyrek) vs Fibonacci heap (teorik) — veri yapısı seçimi karmaşıklığı belirler.
- **Geriye → DAG relaxation (Ders 16) + öncelik kuyruğu (Ders 12):** Dijkstra ikisini birleştirir.
Tek cümle: *Negatif ağırlık yoksa mesafe en kısa yol boyunca artar; bu sayede düğümleri artan mesafe sırasında bir öncelik kuyruğundan çekip kenarlarını gevşeterek SSSP'yi $O(V \log V + E)$'de çözeriz — BFS'in ağırlıklı genellemesi.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 19 (L13) Dijkstra motoru (_engine.py D19 bölümü:
# ChangeablePQ → dijkstra → dijkstra_trace → build_dijkstra_example) + D18
# bellman_ford_classic (negatif-kenar çapraz kanıtı) + D16 relax_edge/INF +
# D12 heap_left/right/parent + 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 dijkstra / dijkstra_trace / build_dijkstra_example / ChangeablePQ /
# bellman_ford_classic / heap_left/right/parent / COL_*'ı IMPORT ETMEDEN kullanır.
#
# Notion'daki öğretim içeriği (görünür ```python blokları) bu motorun tarif
# seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir).
# ============================================================================
import math
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, FancyBboxPatch, FancyArrowPatch, Arc
# ---------------------------------------------------------------------------
# _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"
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
INF = float("inf")
# ---------------------------------------------------------------------------
# _engine.py D12 (L8) — ikili yığın indeks yardımcıları (ChangeablePQ için)
# ---------------------------------------------------------------------------
def heap_left(i):
"""Sol çocuk index'i (L8 §6): 2i + 1."""
return 2 * i + 1
def heap_right(i):
"""Sağ çocuk index'i: 2i + 2."""
return 2 * i + 2
def heap_parent(j):
"""Parent index'i: (j − 1) // 2."""
return (j - 1) // 2
# ---------------------------------------------------------------------------
# _engine.py D16 (L11) — relax_edge (gevşetme; D18 Bellman-Ford bunu kullanır)
# ---------------------------------------------------------------------------
def relax_edge(d, weight, u, v):
"""Kenar gevşetme (L11 §8): üçgen eşitsizliği ihlali varsa tahmini düşür."""
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
return True
return False
def _reachable_from(adj, start):
"""start kümesinden erişilebilen düğümler (negatif çevrim → −∞ yayma)."""
seen = set(start)
stack = list(start)
while stack:
u = stack.pop()
for v in adj[u]:
if v not in seen:
seen.add(v)
stack.append(v)
return seen
def bellman_ford_classic(adj, weight, s):
"""Klasik Bellman-Ford (D18): V−1 tur kenar gevşetme; V. turda hâlâ
gevşeyen düğümler TANIK → erişilenlere −∞ yay. Dijkstra'nın çapraz kanıtı."""
d = {v: INF for v in adj}
d[s] = 0
n = len(adj)
for _ in range(n - 1):
for u in adj:
if d[u] == INF:
continue
for v in adj[u]:
relax_edge(d, weight, u, v)
witnesses = set()
for u in adj:
if d[u] == INF:
continue
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
witnesses.add(v)
for v in _reachable_from(adj, witnesses):
d[v] = -INF
return d
# ---------------------------------------------------------------------------
# _engine.py D19 (L13) — Dijkstra — Ku; negatif-olmayan ağırlıklı SSSP, ~doğrusal
# ChangeablePQ = binary min-heap + id→konum CROSS-LINK sözlüğü (Notion §5).
# build / delete_min / decrease_key. BFS'in ağırlıklı genellemesi.
# ---------------------------------------------------------------------------
class ChangeablePQ:
"""Değiştirilebilir min-öncelik kuyruğu (L13 §5): binary min-heap +
id→konum sözlüğü (cross-link). build O(n), delete_min / decrease_key
O(log n). Öğe = (key, id); id benzersiz."""
def __init__(self, items=()):
self.a = [(k, i) for i, k in items] # (key, id)
self.pos = {item[1]: idx for idx, item in enumerate(self.a)}
for j in range(len(self.a) // 2 - 1, -1, -1): # heapify O(n)
self._sift_down(j)
def __len__(self):
return len(self.a)
def _swap(self, i, j):
self.a[i], self.a[j] = self.a[j], self.a[i]
self.pos[self.a[i][1]] = i
self.pos[self.a[j][1]] = j
def _sift_up(self, j):
while j > 0:
p = (j - 1) // 2
if self.a[p][0] <= self.a[j][0]:
break
self._swap(p, j)
j = p
def _sift_down(self, j):
n = len(self.a)
while True:
l, r, small = 2 * j + 1, 2 * j + 2, j
if l < n and self.a[l][0] < self.a[small][0]:
small = l
if r < n and self.a[r][0] < self.a[small][0]:
small = r
if small == j:
return
self._swap(j, small)
j = small
def delete_min(self):
"""En küçük anahtarlı id'yi çıkar. O(log n)."""
top_key, top_id = self.a[0]
last = self.a.pop()
del self.pos[top_id]
if self.a:
self.a[0] = last
self.pos[last[1]] = 0
self._sift_down(0)
return top_id, top_key
def decrease_key(self, vid, new_key):
"""id'li öğenin anahtarını DÜŞÜR (cross-link ile konumu O(1) bul,
yukarı süz). O(log n)."""
j = self.pos[vid]
assert new_key <= self.a[j][0], "decrease_key yalnız düşürür"
self.a[j] = (new_key, vid)
self._sift_up(j)
def is_valid_heap(self):
"""Doğrulama: min-heap özelliği + pos sözlüğü tutarlı."""
for j in range(len(self.a)):
for c in (2 * j + 1, 2 * j + 2):
if c < len(self.a) and self.a[j][0] > self.a[c][0]:
return False
return all(self.a[self.pos[i]][1] == i for i in self.pos)
def dijkstra(adj, weight, s):
"""Dijkstra (L13 §6, Notion pseudocode birebir): en yakını çıkar,
kenarlarını gevşet, decrease_key ile güncelle. Ağırlıklar ≥ 0 ŞART."""
d = {v: INF for v in adj}
d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
while len(Q):
u, _ = Q.delete_min()
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
Q.decrease_key(v, d[v])
return d
def dijkstra_trace(adj, weight, s):
"""fig-dijkstra-run için: her delete_min adımında (u, d_u, gevşetilenler).
Çıkarılma sırasının ARTAN mesafe olduğunu da döndürür (Gözlem B)."""
d = {v: INF for v in adj}
d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
steps = []
order = []
while len(Q):
u, ku = Q.delete_min()
order.append((u, ku))
relaxed = []
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
old = d[v]
d[v] = d[u] + weight[(u, v)]
Q.decrease_key(v, d[v])
relaxed.append((v, old, d[v]))
steps.append({"u": u, "d_u": ku, "relaxed": relaxed, "d": dict(d)})
return {"steps": steps, "order": order, "d": d}
def build_dijkstra_example():
"""L13 §6 Notion çalışılan örneği (anlatı sayıları birebir):
s→a(10), s→c(3); c→a(4), c→b(8), c→d(2); d→b(5); a→b(2).
Çıkarılma sırası s(0), c(3), d(5), a(7), b(9); a 10→7, b 11→10→9."""
adj = {"s": ["a", "c"], "a": ["b"], "b": [], "c": ["a", "b", "d"],
"d": ["b"]}
weight = {("s", "a"): 10, ("s", "c"): 3, ("c", "a"): 4, ("c", "b"): 8,
("c", "d"): 2, ("d", "b"): 5, ("a", "b"): 2}
return adj, weight
```
## 1. Manzara: Üç Algoritma ve Dijkstra'nın Yeri {#sec-1-manzara-uc-algoritma}
Şimdiye dek ağırlıklı SSSP için üç yol gördük: (1) **BFS** (ağırlıkları tek-kenarlara açarak — yalnız pozitif ve küçük-toplamlı), (2) **DAG relaxation** (çevrimsiz, herhangi ağırlık, doğrusal), (3) **Bellman-Ford** (genel, negatif çevrim dahil, $O(V \cdot E)$). Bellman-Ford yoğun çizgede $O(V^3)$ — yavaş.
Çoğu gerçek problemde ağırlıklar **negatif değildir** ("evime negatif mesafe yok"). Bu kısıtla çok daha iyisini yapabiliriz: **Dijkstra**, neredeyse doğrusal $O(V \log V + E)$. (Buradaki $\log V$ pratikte ~30-60'tan büyük olmaz.)
## 2. Gözlem 1: Negatif Olmayan Ağırlık → Mesafe Artar {#sec-2-gozlem-1-mesafe-artar}
İlk anahtar gözlem: ağırlıklar $\geq 0$ ise, en kısa yol boyunca mesafe **(zayıf) tekdüze artar**.
> *"If weights greater than or equal to 0, then distances increase along shortest paths."* — Ku, 8:35
Yani $s \to v$ en kısa yolu bir $u$'dan geçiyorsa, $\delta(s, u) \leq \delta(s, v)$ (aradaki alt-yolun ağırlığı negatif olamaz). Bu, "kaynak merkezli bir küreyi dışa büyütüp önce yakın düğümleri keşfet" stratejisini mümkün kılar. Negatif ağırlık olsaydı, çok uzaktaki bir düğüm negatif kenarla küre içine "sızabilirdi" — bu strateji çökerdi.
@fig-monotone-distance bu gözlemi eşmerkezli mesafe kürelerinde gösterir: kaynak $s$ merkezde, her düğüm $\delta(s, v)$ yarıçaplı bir kürede; en kısa yol $s \to c \to a \to b$ daima dışa doğru ($\delta$: $0 \to 3 \to 7 \to 9$, kesinlikle artan). Sağdaki karşı-örnek panel, hayali bir $-8$ kenarı eklenince uzak düğümün iç küreye "sızıp" yapının çöktüğünü — negatif ağırlığın neden yasak olduğunu — gösterir.
```{python}
#| label: fig-monotone-distance
#| fig-cap: "Gözlem 1 (Ku L13 §2): ağırlık ≥ 0 → mesafe en kısa yol BOYUNCA ARTAR — eşmerkezli mesafe küreleri sezgisi (L13 §2). SOL: kaynak s merkezde (0,0); yaylar δ = 3, 5, 7, 9 (örnek çizgenin δ değerleri). Her düğüm kendi δ yarıçaplı kürede; en kısa yol s→c→a→b amber, düğüm mesafeleri 0→3→7→9 ARTAN; yol boyunca δ büyür oku. SAĞ — KARŞI-ÖRNEK: aynı küre fikrine b'den iç küreye hayali −8 kenarı eklenirse uzak düğüm mesafesi geri DÜŞER (dış küreden iç küreye SIZAR) → eşmerkezli yapı çöker → açgözlü strateji çöker; negatif ağırlık YASAK gerekçesi. ALT NOT: çıkarılma sırası = artan mesafe s, c, d, a, b; \"distances increase along shortest paths\" (Ku 8:35). Veri MOTORDAN: dijkstra(s) = {s:0, c:3, d:5, a:7, b:9}; en kısa yol s→c→a→b mesafeleri 0→3→7→9 kesinlikle ARTAN; tüm ağırlıklar ≥ 0."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-monotone-distance (L13 §2): eşmerkezli mesafe küreleri + karşı-örnek.
# Veri MOTORDAN (build_dijkstra_example / dijkstra). networkx YOK — elle koordinat.
_MD_GRAPH_POS = {"s": (0.0, 1.0), "c": (1.0, 0.4), "a": (1.0, 1.6),
"d": (2.0, 0.4), "b": (2.6, 1.0)}
_MD_SP_PATH = ["s", "c", "a", "b"]
def _md_polar(r, deg):
t = math.radians(deg)
return (r * math.cos(t), r * math.sin(t))
def _md_draw_spheres(ax, delta):
ang = {"c": 50.0, "a": 70.0, "b": 88.0, "d": 18.0}
pos = {"s": (0.0, 0.0)}
for v, deg in ang.items():
pos[v] = _md_polar(delta[v], deg)
radii = sorted({delta[v] for v in delta if v != "s"}) # {3,5,7,9}
for r in radii:
ax.add_patch(Arc((0, 0), 2 * r, 2 * r, angle=0, theta1=-18, theta2=128,
color=COL_SLATE_400, linewidth=1.2, linestyle="--",
alpha=0.85, zorder=1))
lx, ly = _md_polar(r, 122)
ax.text(lx - 0.30, ly + 0.16, f"δ = {r}", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, style="italic", zorder=2)
for i in range(len(_MD_SP_PATH) - 1):
u, v = _MD_SP_PATH[i], _MD_SP_PATH[i + 1]
ux, uy = pos[u]
vx, vy = pos[v]
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=15,
color=COL_ACCENT, linewidth=2.8, shrinkA=18, shrinkB=18, zorder=4))
_R = 0.33
for v, (x, y) in pos.items():
on_path = (v in _MD_SP_PATH)
is_src = (v == "s")
if is_src:
fc, ec, tc, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.8
elif on_path:
fc, ec, tc, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.4
else:
fc, ec, tc, lw = COL_BG, COL_PRIMARY, COL_TEXT, 1.8
ax.add_patch(Circle((x, y), _R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, v, ha="center", va="center", fontsize=13,
color=tc, weight="bold", zorder=6)
if is_src:
ax.text(x - _R - 0.55, y - 0.02, "δ = 0", ha="center", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(x + _R + 0.55, y - 0.02, "kaynak", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, weight="bold", zorder=6)
else:
if v == "b":
lx, ly = x + _R + 0.85, y
else:
mag = math.hypot(x, y)
ux2, uy2 = (x / mag, y / mag) if mag > 1e-9 else (0, 1)
lx, ly = x + ux2 * (_R + 0.42), y + uy2 * (_R + 0.42)
col = COL_AMBER_700 if on_path else COL_TEXT
ax.text(lx, ly, f"δ = {delta[v]}", ha="center", va="center",
fontsize=9.5, color=col, weight="bold", zorder=7,
bbox=dict(boxstyle="round,pad=0.18", fc=COL_WHITE,
ec=col, linewidth=1.0, alpha=0.92))
a_in = _md_polar(3.0, 30)
a_out = _md_polar(9.2, 70)
ax.add_patch(FancyArrowPatch(
a_in, a_out, arrowstyle="-|>", mutation_scale=16,
color=COL_AMBER_600, linewidth=2.0, linestyle=":",
connectionstyle="arc3,rad=-0.32", zorder=3))
mlx, mly = _md_polar(7.6, 40)
ax.text(mlx, mly, "δ ARTAR\n(0→3→7→9)", ha="center", va="center",
fontsize=8.8, color=COL_AMBER_700, weight="bold",
style="italic", zorder=6,
bbox=dict(boxstyle="round,pad=0.3", fc=COL_WHITE,
ec=COL_AMBER_300, linewidth=1.3))
ax.text(2.4, 10.4, "Eşmerkezli mesafe küreleri (kaynak s merkezde)",
ha="center", va="center", fontsize=11.5, color=COL_PRIMARY,
weight="bold", zorder=6)
ax.text(2.4, 9.75,
"en kısa yol s → c → a → b daima DIŞA doğru → δ monoton artar",
ha="center", va="center", fontsize=8.8, color=COL_SLATE_500,
style="italic", zorder=6)
def _md_draw_counterexample(ax, ox, oy):
pw, ph = 4.4, 8.4
ax.add_patch(FancyBboxPatch(
(ox, oy), pw, ph, boxstyle="round,pad=0.06,rounding_size=0.18",
fc=COL_WHITE, ec=COL_AMBER_700, linewidth=2.0, linestyle="--", zorder=2))
cxp = ox + pw * 0.5
ax.text(cxp, oy + ph - 0.42, "KARŞI-ÖRNEK", ha="center", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(cxp, oy + ph - 0.92, "hayali negatif kenar eklenirse",
ha="center", va="center", fontsize=8.4, color=COL_SLATE_500,
style="italic", zorder=6)
cx, cy = cxp, oy + ph - 3.55
_r = 0.30
mini = [("s", 0.0, 0.0), ("c", -1.05, 0.70), ("b", 1.35, 0.45)]
for r in (1.25, 2.05):
ax.add_patch(Circle((cx, cy), r, facecolor="none",
edgecolor=COL_SLATE_400, linewidth=1.0,
linestyle="--", alpha=0.8, zorder=3))
posn = {v: (cx + dx, cy + dy) for v, dx, dy in mini}
for u, v in (("s", "c"), ("c", "b")):
ux, uy = posn[u]
vx, vy = posn[v]
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=11,
color=COL_AMBER_600, linewidth=1.8, shrinkA=14, shrinkB=14, zorder=4))
bx, by = posn["b"]
leak_x, leak_y = cx + 0.10, cy - 1.05
ax.add_patch(FancyArrowPatch(
(bx, by), (leak_x, leak_y), arrowstyle="-|>", mutation_scale=13,
color=COL_ACCENT, linewidth=2.4, linestyle=(0, (4, 2)),
connectionstyle="arc3,rad=-0.45", zorder=5))
ax.text(bx + 0.78, by - 0.62, "−8", ha="center", va="center", fontsize=10.5,
color=COL_ACCENT, weight="bold", zorder=6,
bbox=dict(boxstyle="round,pad=0.18", fc=COL_AMBER_100,
ec=COL_ACCENT, linewidth=1.4))
ax.add_patch(Circle((leak_x, leak_y), 0.13, facecolor=COL_ACCENT,
edgecolor=COL_AMBER_700, linewidth=1.4, zorder=6))
for v, (x, y) in posn.items():
is_src = (v == "s")
fc = COL_AMBER_100 if is_src else COL_BG
ec = COL_ACCENT if is_src else COL_PRIMARY
ax.add_patch(Circle((x, y), _r, facecolor=fc, edgecolor=ec,
linewidth=2.0 if is_src else 1.6, zorder=7))
ax.text(x, y, v, ha="center", va="center", fontsize=11,
color=COL_AMBER_700 if is_src else COL_TEXT,
weight="bold", zorder=8)
tx = ox + 0.30
ty = oy + 2.55
ax.text(tx, ty, "→ uzak düğüm mesafesi geri DÜŞER", ha="left", va="center",
fontsize=8.8, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(tx, ty - 0.52, "→ dış küreden iç küreye SIZAR", ha="left",
va="center", fontsize=8.8, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(tx, ty - 1.10, "eşmerkezli küre yapısı çöker —", ha="left",
va="center", fontsize=8.4, color=COL_SLATE_500, style="italic", zorder=6)
ax.text(tx, ty - 1.52, "açgözlü strateji de ÇÖKER.", ha="left", va="center",
fontsize=8.4, color=COL_SLATE_500, style="italic", zorder=6)
ax.text(cxp, oy + 0.42, "negatif ağırlık YASAK", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6,
bbox=dict(boxstyle="round,pad=0.28", fc=COL_AMBER_100,
ec=COL_AMBER_700, linewidth=1.5))
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_md_adj, _md_w = build_dijkstra_example()
_md_delta = dijkstra(_md_adj, _md_w, "s")
assert _md_delta == {"s": 0, "c": 3, "d": 5, "a": 7, "b": 9}, _md_delta
_md_path_d = [_md_delta[v] for v in _MD_SP_PATH]
assert _md_path_d == [0, 3, 7, 9], _md_path_d
assert all(_md_path_d[i] < _md_path_d[i + 1] for i in range(len(_md_path_d) - 1))
assert all(w >= 0 for w in _md_w.values()), _md_w
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
_md_draw_spheres(ax, _md_delta)
_md_draw_counterexample(ax, 10.4, 0.6)
ax.text(-5.6, -2.85,
"Gözlem 1 (Ku L13 §2): ağırlık ≥ 0 ise mesafe en kısa yol boyunca "
"ARTAR — \"distances increase along shortest paths\" (Ku 8:35).",
ha="left", va="center", fontsize=9.2, color=COL_TEXT,
weight="bold", zorder=6)
ax.text(-5.6, -3.42,
"Sonuç: en yakını kesinleştir, bir daha dokunma (Dijkstra "
"açgözlülüğü doğru) — çıkarılma sırası = artan mesafe s, c, d, a, b.",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500,
style="italic", zorder=6)
fig.suptitle(
"Gözlem 1: ağırlık ≥ 0 → mesafe en kısa yol boyunca ARTAR (eşmerkezli küre sezgisi)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.set_xlim(-6.2, 15.4)
ax.set_ylim(-3.9, 11.0)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 3. Gözlem 2: Artan Sıra Bilinirse DAG Relaxation {#sec-3-gozlem-2-artan-sira}
İkinci gözlem: SSSP'yi **daha hızlı** çözebiliriz — eğer düğümleri **artan mesafe sırasında** önceden bilirsek.
> *"we can solve single source shortest paths faster if we're given an order of vertices in increasing distance beforehand."* — Ku, 11:22
Neden? Gözlem 1 sayesinde, bu sıraya göre **geriye giden** her (pozitif) kenar en kısa yola katılamaz → atılır. Geriye yalnız ileri kenarlar kalır → bir **DAG** → DAG relaxation (doğrusal). (0-ağırlıklı kenarlar istisna: aynı mesafedeki düğümler arası 0-kenar, sırayı çevirerek düzeltilir; 0-ağırlıklı çevrim tek düğüme **birleştirilir/coalesce**.) Sorun: bu sırayı önceden bilmiyoruz — onu *hesaplamamız* gerek.
## 4. Dijkstra'nın Fikri {#sec-4-dijkstra-fikri}
Dijkstra (BFS'in ağırlıklı genellemesi; Hollandalı bilgisayar bilimci, "Dijkstra"da J sesi yok — Y'den gelir) iki gözlemi birleştirir:
> *"Relax edges from vertices in increasing distance from source."* — Ku, 23:09
Kenarları, düğümleri **artan mesafe sırasında** alarak gevşet. Ama "sıradaki en yakın düğüm" hangisi? Bunu önceden bilmediğimizden, **kademeli** hesaplarız:
> *"find the next vertex efficiently using a data structure."* — Ku, 23:47
## 5. Değiştirilebilir Öncelik Kuyruğu {#sec-5-degistirilebilir-oncelik-kuyrugu}
Gereken yapı: **değiştirilebilir öncelik kuyruğu (changeable priority queue)** — üç işlem:
> *"changeable priority queue has three operations... build... delete min... Decrease the key."* — Ku, 24:42
- **build(items):** $n$ öğeyle kur.
- **delete_min():** en küçük anahtarlı öğeyi çıkar.
- **decrease_key(id, k):** belirli **id**'li öğenin anahtarını daha küçük bir $k$'ya düşür.
Fark: her öğenin bir **anahtarı** (key, mesafe tahmini) **ve** benzersiz bir **id**'si (düğüm) vardır. `decrease_key`, id ile öğeyi bulup anahtarını günceller. İmplementasyon: normal bir öncelik kuyruğu (Ders 12) + bir **sözlük** (id → kuyruktaki konum) cross-link. Düğüm id'leri $0 \ldots V-1$ ise, sözlük yerine **direct access array** → $O(1)$ (hash'in beklenen $O(1)$'i yerine kesin $O(1)$).
@fig-changeable-pq imza şekildir: solda binary min-heap ağacı (her düğümde `(key, id)`) + altında id→konum cross-link sözlüğü; ortada `decrease_key(2, 0)` adımı (id 2'nin anahtarı $8 \to 0$, köke sift-up); sağda üç işlem ve maliyetleri. Çapraz bağ, gevşeyen bir düğümü taramadan $O(1)$ konumlandırmayı — dolayısıyla $O(\log n)$ `decrease_key`'i — mümkün kılar.
```{python}
#| label: fig-changeable-pq
#| fig-cap: "Değiştirilebilir öncelik kuyruğu = binary min-heap + id→konum CROSS-LINK sözlüğü → decrease_key O(log n) (L13 §5 İMZA). SOL: 5 düğümlü min-heap ağacı, her düğümde (key, id) çifti + altında pos sözlüğü tablosu (id → heap-konumu satırları); her satırdan ağaçtaki düğüme ince amber cross-link oku (id → konum O(1); D14 işaretçi dersinin akrabası). ORTA: decrease_key(2, 0) adımı — id 2'nin anahtarı 8 üstü çizili → 0, kökten yukarı sift-up okları; pos[2] ile konum O(1) bulundu → O(log n) süzülme. SAĞ: üç işlem kutusu build O(n) / delete_min O(log n) / decrease_key O(log n) (Ku 24:42) + id'ler 0..V−1 ise pos = doğrudan erişim dizisi → kesin O(1) notu. Veri MOTORDAN: ChangeablePQ([(0,5),(1,3),(2,8),(3,1),(4,9)]) heapify sonrası a = [(1,3),(3,1),(8,2),(5,0),(9,4)], is_valid_heap True; decrease_key(2,0) sonra delete_min() == (2,0) (id 2 köke geçti)."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-changeable-pq (L13 §5 İMZA): min-heap + cross-link + decrease_key.
# Veri MOTORDAN (ChangeablePQ). networkx YOK — elle koordinat.
_PQ_TREE_POS = {
0: (1.6, 3.0),
1: (0.7, 1.8), 2: (2.5, 1.8),
3: (0.25, 0.6), 4: (1.15, 0.6),
}
_PQ_NODE_R = 0.40
def _pq_draw_heap_tree(ax, heap, hot_idx=None):
n = len(heap)
centers = {}
for i in range(n):
for c in (heap_left(i), heap_right(i)):
if c < n:
ux, uy = _PQ_TREE_POS[i]
vx, vy = _PQ_TREE_POS[c]
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-",
color=COL_SLATE_400, linewidth=1.6,
shrinkA=_PQ_NODE_R * 72, shrinkB=_PQ_NODE_R * 72, zorder=1))
for i in range(n):
key, vid = heap[i]
x, y = _PQ_TREE_POS[i]
centers[i] = (x, y)
is_hot = (i == hot_idx)
fc = COL_AMBER_100 if is_hot else COL_BG
ec = COL_ACCENT if is_hot else COL_PRIMARY
lw = 2.8 if is_hot else 1.9
ax.add_patch(Circle((x, y), _PQ_NODE_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=4))
ax.text(x, y + 0.09, str(key), ha="center", va="center", fontsize=12.5,
color=COL_AMBER_700 if is_hot else COL_TEXT, weight="bold", zorder=5)
ax.text(x, y - 0.17, f"id {vid}", ha="center", va="center", fontsize=7.5,
color=COL_SLATE_500, zorder=5)
ax.text(x + _PQ_NODE_R + 0.02, y + _PQ_NODE_R - 0.02, f"[{i}]",
ha="left", va="center", fontsize=7, color=COL_SLATE_400,
style="italic", zorder=5)
rx, ry = _PQ_TREE_POS[0]
ax.text(rx, ry + _PQ_NODE_R + 0.18, "kök = min", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
return centers
def _pq_draw_pos_table(ax, x0, y0, heap, tree_centers):
pos = {vid: idx for idx, (_, vid) in enumerate(heap)}
row_h = 0.42
tbl_w = 1.95
ax.text(x0 + tbl_w * 0.5, y0 + row_h * 0.6, "pos sözlüğü (cross-link)",
ha="center", va="center", fontsize=8.5, color=COL_PRIMARY,
weight="bold", zorder=5)
ax.text(x0 + 0.45, y0 + row_h * 0.1, "id", ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, weight="bold", zorder=5)
ax.text(x0 + 1.45, y0 + row_h * 0.1, "konum", ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, weight="bold", zorder=5)
for r, vid in enumerate(sorted(pos)):
idx = pos[vid]
y = y0 - 0.18 - r * row_h
row_fc = COL_BG if (r % 2 == 0) else COL_WHITE
ax.add_patch(FancyBboxPatch(
(x0, y - row_h * 0.5), tbl_w, row_h * 0.9,
boxstyle="square,pad=0.0", fc=row_fc, ec=COL_SLATE_500,
linewidth=1.2, zorder=3))
ax.text(x0 + 0.45, y, str(vid), ha="center", va="center",
fontsize=9, color=COL_TEXT, weight="bold", zorder=4)
ax.text(x0 + 0.95, y, "→", ha="center", va="center",
fontsize=9, color=COL_SLATE_400, zorder=4)
ax.text(x0 + 1.45, y, f"[{idx}]", ha="center", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=4)
tx, ty = tree_centers[idx]
ax.add_patch(FancyArrowPatch(
(x0 + tbl_w + 0.02, y), (tx - _PQ_NODE_R - 0.04, ty),
arrowstyle="-|>", mutation_scale=8, color=COL_AMBER_300,
linewidth=1.0, zorder=2, shrinkA=2, shrinkB=2,
connectionstyle="arc3,rad=0.16", alpha=0.85))
ax.text(x0 + tbl_w * 0.5, y0 - 0.18 - len(pos) * row_h - 0.05,
"id → konum O(1) bulunur\n(D14 işaretçi dersinin akrabası)",
ha="center", va="center", fontsize=7, color=COL_SLATE_500,
style="italic", zorder=5)
def _pq_draw_decrease_key(ax, ox, oy):
ax.text(ox + 0.9, oy + 2.55, "decrease_key(2, 0)", ha="center", va="center",
fontsize=11, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=6)
ax.text(ox + 0.9, oy + 2.18, "id 2'nin anahtarı 8 → 0", ha="center",
va="center", fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=6)
cell_w, cell_h = 1.55, 0.78
cx = ox + 0.9
y_old = oy + 1.35
ax.add_patch(FancyBboxPatch(
(cx - cell_w * 0.5, y_old - cell_h * 0.5), cell_w, cell_h,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_WHITE, ec=COL_SLATE_400, linewidth=1.4, zorder=4))
ax.text(cx - 0.30, y_old, "8", ha="center", va="center", fontsize=14,
color=COL_SLATE_400, weight="bold", zorder=5)
ax.plot([cx - 0.46, cx - 0.14], [y_old, y_old], color=COL_AMBER_700,
linewidth=2.0, zorder=6)
ax.text(cx + 0.32, y_old, "id 2", ha="center", va="center", fontsize=8.5,
color=COL_SLATE_500, zorder=5)
ax.add_patch(FancyArrowPatch(
(cx, y_old - cell_h * 0.5 - 0.04), (cx, y_old - cell_h * 0.5 - 0.42),
arrowstyle="-|>", mutation_scale=14, color=COL_AMBER_700,
linewidth=2.2, zorder=5))
y_new = oy + 0.30
ax.add_patch(FancyBboxPatch(
(cx - cell_w * 0.5, y_new - cell_h * 0.5), cell_w, cell_h,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=4))
ax.text(cx - 0.30, y_new, "0", ha="center", va="center", fontsize=15,
color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(cx + 0.32, y_new, "id 2", ha="center", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold", zorder=5)
su_x = ox + 0.9
ax.add_patch(FancyArrowPatch(
(su_x, y_new - cell_h * 0.5 - 0.06), (su_x, y_new - cell_h * 0.5 - 0.66),
arrowstyle="-|>", mutation_scale=16, color=COL_ACCENT,
linewidth=2.6, zorder=5, connectionstyle="arc3,rad=0.0"))
ax.text(su_x + 0.06, y_new - cell_h * 0.5 - 0.36, "sift-up\n(yukarı süzül)",
ha="left", va="center", fontsize=8, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(ox + 0.9, oy - 0.85,
"0 < parent → yukarı yükselir;\nid 2 KÖKE geçer (yeni min)",
ha="center", va="center", fontsize=8, color=COL_SLATE_500,
style="italic", zorder=6)
ax.text(ox + 0.9, oy - 1.55,
"konum pos[2] ile O(1)\nbulundu → O(log n) süzülme",
ha="center", va="center", fontsize=7.5, color=COL_AMBER_700,
weight="bold", zorder=6)
def _pq_draw_op_box(ax, x, y, w, h, name, cost, 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))
ax.text(x + 0.20, y + h * 0.5, name, ha="left", va="center",
fontsize=10.5, color=COL_AMBER_700 if accent else COL_TEXT,
weight="bold", family="monospace", zorder=5)
ax.text(x + w - 0.20, y + h * 0.5, cost, ha="right", va="center",
fontsize=11, color=COL_AMBER_700 if accent else COL_PRIMARY,
weight="bold", family="monospace", zorder=5)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_pq_items = [(0, 5), (1, 3), (2, 8), (3, 1), (4, 9)] # (id, key)
_pq = ChangeablePQ(_pq_items)
assert _pq.is_valid_heap(), "heapify SONRASI min-heap geçersiz"
_pq_heap_before = list(_pq.a)
assert _pq_heap_before == [(1, 3), (3, 1), (8, 2), (5, 0), (9, 4)], _pq_heap_before
assert _pq.pos[2] == 2, _pq.pos
_pq2 = ChangeablePQ(_pq_items)
_pq2.decrease_key(2, 0)
assert _pq2.is_valid_heap(), "decrease_key SONRASI min-heap geçersiz"
assert _pq2.delete_min() == (2, 0)
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
_pq_centers = _pq_draw_heap_tree(ax, _pq_heap_before)
_pq_draw_pos_table(ax, -0.30, -0.30, _pq_heap_before, _pq_centers)
ax.text(1.45, 4.05, "Binary min-heap + cross-link", ha="center", va="center",
fontsize=11, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(2.95, 4.05, "· düğüm = (key, id)", ha="left", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=6)
_pq_mid_ox = 4.15
_pq_draw_decrease_key(ax, _pq_mid_ox, 0.55)
ax.add_patch(FancyArrowPatch(
(3.25, 1.6), (_pq_mid_ox - 0.05, 1.6), arrowstyle="-|>",
mutation_scale=15, color=COL_SLATE_400, linewidth=1.8, zorder=2))
_pq_rx = 7.55
_pq_bw, _pq_bh = 3.35, 0.80
_pq_v_gap = 0.32
_pq_top_y = 3.40
_pq_ops = [
("build", "O(n)", False),
("delete_min", "O(log n)", False),
("decrease_key", "O(log n)", True),
]
for _idx, (_name, _cost, _accent) in enumerate(_pq_ops):
_y = _pq_top_y - _idx * (_pq_bh + _pq_v_gap)
_pq_draw_op_box(ax, _pq_rx, _y, _pq_bw, _pq_bh, _name, _cost, accent=_accent)
ax.text(_pq_rx + _pq_bw * 0.5, _pq_top_y + _pq_bh + 0.30,
"Üç temel işlem (Ku 24:42)", ha="center", va="center",
fontsize=10.5, color=COL_PRIMARY, weight="bold", zorder=6)
_pq_note_y = _pq_top_y - 3 * (_pq_bh + _pq_v_gap) - 0.10
ax.add_patch(FancyBboxPatch(
(_pq_rx, _pq_note_y - 0.92), _pq_bw, 0.92,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=3))
ax.text(_pq_rx + _pq_bw * 0.5, _pq_note_y - 0.24, "id'ler 0..V−1 ise:",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(_pq_rx + _pq_bw * 0.5, _pq_note_y - 0.52, "pos = doğrudan erişim dizisi",
ha="center", va="center", fontsize=8.5, color=COL_TEXT, zorder=5)
ax.text(_pq_rx + _pq_bw * 0.5, _pq_note_y - 0.78, "→ konum araması KESİN O(1)",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", family="monospace", zorder=5)
fig.suptitle(
"Değiştirilebilir öncelik kuyruğu: min-heap + id→konum cross-link "
"→ decrease_key O(log n)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(5.5, 4.30,
"Dijkstra'nın motoru — kuyruktaki bir düğümün anahtarını gevşetme "
"(relax) ile düşürür · Ku L13 §5",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.7, _pq_rx + _pq_bw + 0.4)
ax.set_ylim(-2.85, 4.55)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 6. Dijkstra Algoritması {#sec-6-dijkstra-algoritmasi}
Başlat: $d(s, v) = \infty$ tüm $v$; $d(s, s) = 0$. Kuyruğu kur. Boşalana dek: en küçük tahminli $u$'yu çıkar, çıkış kenarlarını gevşet (gevşetince `decrease_key` ile kuyruğu güncelle).
> *"Dijkstra... designed this very nice generalization of BFS for weighted graphs."* — Ku, 22:02
```python
def dijkstra(adj, weight, s):
d = {v: float('inf') for v in adj}
d[s] = 0
Q = ChangeablePriorityQueue((v, d[v]) for v in adj) # build
while Q: # bos degilse
u = Q.delete_min() # en yakin dugum
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]: # ucgen esitsizligi ihlali
d[v] = d[u] + weight[(u, v)] # relax
Q.decrease_key(v, d[v]) # kuyrugu guncelle
return d
```
**Çalışılan Örnek.** Pozitif ağırlıklı, çevrimli yönlü çizge. $s = 0$ ile başla; $s$'yi çıkar, $a \to 10$, $c \to 3$ gevşet. Kuyruktaki en küçük: $c$ (3). $c$'yi çıkar, $a \to 7$ ($3 + 4$), $b \to 11$, $d \to 5$ gevşet. En küçük: $d$ (5). $d$'yi çıkar, $b \to 10$ ($5 + 5$). En küçük: $a$ (7). $a$'yı çıkar, $b \to 9$ ($7 + 2$). Sonra $b$ (9). Sonuç: $\delta = \{s{:}0, c{:}3, d{:}5, a{:}7, b{:}9\}$ — doğru en kısa mesafeler.
@fig-dijkstra-run bu örneğin tam adım izini gösterir: üstte çalışılan çizge (amber kenarlar = en kısa yol ağacı), altta 5 satırlık tablo. Her satır: `delete_min` edilen düğüm (kesinleşti/donduruldu), gevşetilen kenarlar, kuyrukta kalanlar ve `d` tablosunun anlık durumu. $b$ düğümü $\infty \to 11 \to 10 \to 9$ üç ayrı turda düşer — açgözlü çıkarma sonradan iyileşmeyi engellemez, çıkarılma anında değer kesinleşir.
```{python}
#| label: fig-dijkstra-run
#| fig-cap: "Dijkstra adım izi: en yakını çıkar · gevşet · decrease_key — çıkarma sırası = ARTAN mesafe (L13 §6 İMZA). ÜST: çalışılan örnek çizge (build_dijkstra_example) sabit yerleşim; düğüm = daire, kenar = yönlü ok + ağırlık rozeti; amber kenarlar = en kısa yol ağacı (gevşetmeyle d'yi belirleyen: s→c, c→a, c→d, a→b). ALT: 5 satırlık adım tablosu (motor order = artan mesafe). Her satır: delete_min edilen düğüm (amber daire + d-değeri + kesinleşti·donduruldu rozeti) · o turda gevşetilen kenarlar (v: eski→yeni, b sütunu ∞→11→10→9 amber vurgu) · kuyruk kalan mini-kutusu · d tablosunun anlık durumu. ALT NOT (Gözlem B): her düğüm BİR kez çıkar, sonra dondurulur — bir daha dokunulmaz; çıkarılma sırası s(0)→c(3)→d(5)→a(7)→b(9). Veri MOTORDAN: dijkstra_trace order = [(s,0),(c,3),(d,5),(a,7),(b,9)]; c relaxed [(a,10,7),(b,∞,11),(d,∞,5)], d [(b,11,10)], a [(b,10,9)]; trace.d == dijkstra == {s:0,a:7,b:9,c:3,d:5}; b evrimi ∞→11→10→9."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-dijkstra-run (L13 §6 İMZA): çalışılan örnek + adım izi tablosu.
# Veri MOTORDAN (dijkstra_trace / dijkstra / build_dijkstra_example). networkx YOK.
_DR_POS = {
"s": (0.0, 1.0), "c": (1.0, 0.4), "a": (1.0, 1.6),
"d": (2.0, 0.4), "b": (2.6, 1.0),
}
_DR_EDGES = [
("s", "a", 10), ("s", "c", 3), ("c", "a", 4), ("c", "b", 8),
("c", "d", 2), ("d", "b", 5), ("a", "b", 2),
]
_DR_TREE_EDGES = {("s", "c"), ("c", "a"), ("c", "d"), ("a", "b")}
_DR_R = 0.24
_DR_DCOLS = ["s", "a", "b", "c", "d"]
def _dr_fmt_d(val):
return "∞" if val == INF else str(val)
def _dr_draw_graph(ax, ox, oy, source):
def P(v):
x, y = _DR_POS[v]
return (ox + x, oy + y)
for u, v, wt in _DR_EDGES:
ux, uy = P(u)
vx, vy = P(v)
tree = (u, v) in _DR_TREE_EDGES
ecol = COL_ACCENT if tree else COL_SLATE_400
if (u, v) == ("s", "a"):
cstyle = "arc3,rad=-0.18"
elif (u, v) == ("c", "b"):
cstyle = "arc3,rad=0.22"
else:
cstyle = "arc3,rad=0.0"
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=13,
color=ecol, linewidth=2.4 if tree else 1.6,
shrinkA=_DR_R * 72, shrinkB=_DR_R * 72,
connectionstyle=cstyle, zorder=2))
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
if (u, v) == ("s", "a"):
my += 0.16
elif (u, v) == ("c", "b"):
mx += 0.18
my -= 0.10
elif (u, v) == ("c", "a"):
mx -= 0.16
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 tree else COL_WHITE,
ec=COL_ACCENT if tree else COL_SLATE_400,
linewidth=1.5 if tree else 1.0, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center", fontsize=8,
color=COL_AMBER_700 if tree else COL_TEXT, weight="bold", zorder=7)
for v, (x, y) in _DR_POS.items():
is_src = (v == source)
if is_src:
fc, ec, tc, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.8
else:
fc, ec, tc, lw = COL_BG, COL_PRIMARY, COL_TEXT, 2.0
px, py = P(v)
ax.add_patch(Circle((px, py), _DR_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(px, py, v, ha="center", va="center", fontsize=11,
color=tc, weight="bold", zorder=6)
sx, sy = P(source)
ax.text(sx - _DR_R - 0.10, sy, "kaynak", ha="right", va="center",
fontsize=7.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(ox + 1.3, oy + 2.18, "Çalışılan örnek (w: E → ℤ≥0, kaynak s)",
ha="center", va="center", fontsize=10.5, color=COL_PRIMARY,
weight="bold", zorder=6)
ax.text(ox + 1.3, oy - 0.28,
"amber kenarlar = en kısa yol ağacı (gevşetmeyle d'yi belirleyen)",
ha="center", va="center", fontsize=7.5, color=COL_AMBER_700,
style="italic", zorder=6)
def _dr_draw_d_snapshot(ax, x0, y_mid, d_state, changed):
cw = 0.46
cell_h = 0.40
for k, node in enumerate(_DR_DCOLS):
x = x0 + k * cw
hot = node in changed
ax.add_patch(FancyBboxPatch(
(x, y_mid - cell_h * 0.5), cw * 0.92, cell_h,
boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if hot else COL_WHITE,
ec=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.0 if hot else 1.1, zorder=4))
ax.text(x + cw * 0.46, y_mid + 0.005, _dr_fmt_d(d_state[node]),
ha="center", va="center", fontsize=8.2,
color=COL_AMBER_700 if hot else COL_TEXT, weight="bold", zorder=5)
ax.text(x + cw * 0.46, y_mid - cell_h * 0.5 - 0.13, node,
ha="center", va="center", fontsize=6.8,
color=COL_SLATE_500, zorder=5)
def _dr_draw_queue_box(ax, cx, y_mid, remaining):
txt = ", ".join(remaining) if remaining else "∅ (boş)"
w = 0.30 + 0.165 * max(len(txt), 4)
ax.add_patch(FancyBboxPatch(
(cx - w * 0.5, y_mid - 0.20), w, 0.40,
boxstyle="round,pad=0.01,rounding_size=0.06",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.2, zorder=4))
ax.text(cx, y_mid, txt, ha="center", va="center", fontsize=7.6,
color=COL_TEXT, weight="bold", zorder=5)
def _dr_draw_relax_chips(ax, x0, y_mid, relaxed):
if not relaxed:
ax.text(x0 + 0.05, y_mid, "— (gevşetme yok)", ha="left", va="center",
fontsize=7.6, color=COL_SLATE_400, style="italic", zorder=5)
return
chip_w = 1.30
gap = 0.12
for k, (v, old, new) in enumerate(relaxed):
x = x0 + k * (chip_w + gap)
hot = (v == "b")
ax.add_patch(FancyBboxPatch(
(x, y_mid - 0.20), chip_w, 0.40,
boxstyle="round,pad=0.01,rounding_size=0.07",
fc=COL_AMBER_100 if hot else COL_WHITE,
ec=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.0 if hot else 1.2, zorder=4))
ax.text(x + chip_w * 0.5, y_mid, f"{v}: {_dr_fmt_d(old)}→{_dr_fmt_d(new)}",
ha="center", va="center", fontsize=7.8,
color=COL_AMBER_700 if hot else COL_TEXT, weight="bold", zorder=5)
def _dr_draw_step_row(ax, y_mid, idx, u, d_u, relaxed, d_state, remaining,
x_node, x_relax, x_queue, x_dsnap):
ax.text(x_node - 0.62, y_mid, f"#{idx + 1}", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, weight="bold", zorder=5)
ax.add_patch(Circle((x_node, y_mid), 0.21, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=2.4, zorder=5))
ax.text(x_node, y_mid, u, ha="center", va="center", fontsize=11,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(x_node + 0.30, y_mid + 0.085, f"d={d_u}", ha="left", va="center",
fontsize=8.4, color=COL_TEXT, weight="bold", zorder=5)
ax.text(x_node + 0.30, y_mid - 0.135, "kesinleşti · donduruldu", ha="left",
va="center", fontsize=6.6, color=COL_AMBER_700, style="italic", zorder=5)
_dr_draw_relax_chips(ax, x_relax, y_mid, relaxed)
_dr_draw_queue_box(ax, x_queue, y_mid, remaining)
changed = {v for (v, _o, _n) in relaxed}
_dr_draw_d_snapshot(ax, x_dsnap, y_mid, d_state, changed)
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_dr_adj, _dr_w = build_dijkstra_example()
_dr_tr = dijkstra_trace(_dr_adj, _dr_w, "s")
_dr_direct = dijkstra(_dr_adj, _dr_w, "s")
assert _dr_tr["d"] == _dr_direct, (_dr_tr["d"], _dr_direct) # İKİ SÜRÜM BİREBİR
assert _dr_tr["order"] == [("s", 0), ("c", 3), ("d", 5), ("a", 7), ("b", 9)]
assert _dr_tr["d"] == {"s": 0, "a": 7, "b": 9, "c": 3, "d": 5}, _dr_tr["d"]
_dr_steps = _dr_tr["steps"]
assert _dr_steps[1]["u"] == "c" and _dr_steps[1]["relaxed"] == \
[("a", 10, 7), ("b", INF, 11), ("d", INF, 5)], _dr_steps[1]
assert _dr_steps[2]["u"] == "d" and _dr_steps[2]["relaxed"] == [("b", 11, 10)]
assert _dr_steps[3]["u"] == "a" and _dr_steps[3]["relaxed"] == [("b", 10, 9)]
_dr_b_vals = [s["d"]["b"] for s in _dr_steps]
assert _dr_b_vals == [INF, 11, 10, 9, 9], _dr_b_vals
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
_dr_draw_graph(ax, ox=0.30, oy=6.55, source="s")
_dr_x_node = 0.55
_dr_x_relax = 2.30
_dr_x_queue = 7.05
_dr_x_dsnap = 8.45
_dr_head_y = 5.65
ax.text(_dr_x_node, _dr_head_y, "delete_min", ha="center", va="center",
fontsize=8.8, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(_dr_x_relax + 1.9, _dr_head_y, "gevşetilen kenarlar (v: eski→yeni)",
ha="center", va="center", fontsize=8.8, color=COL_PRIMARY,
weight="bold", zorder=5)
ax.text(_dr_x_queue, _dr_head_y, "kuyruk kalan", ha="center", va="center",
fontsize=8.8, color=COL_PRIMARY, weight="bold", zorder=5)
ax.text(_dr_x_dsnap + 1.05, _dr_head_y, "d tablosu (anlık)", ha="center",
va="center", fontsize=8.8, color=COL_PRIMARY, weight="bold", zorder=5)
_dr_row_h = 0.95
_dr_top_row_y = 5.05
for _idx, _st in enumerate(_dr_steps):
_y_mid = _dr_top_row_y - _idx * _dr_row_h
if _idx % 2 == 1:
ax.add_patch(FancyBboxPatch(
(_dr_x_node - 0.95, _y_mid - _dr_row_h * 0.46), 10.95, _dr_row_h * 0.90,
boxstyle="round,pad=0.0,rounding_size=0.03",
fc=COL_BG, ec="none", alpha=0.55, zorder=1))
_remaining = [o[0] for o in _dr_tr["order"][_idx + 1:]]
_dr_draw_step_row(ax, _y_mid, _idx, _st["u"], _st["d_u"], _st["relaxed"],
_st["d"], _remaining,
_dr_x_node, _dr_x_relax, _dr_x_queue, _dr_x_dsnap)
_dr_note_y = _dr_top_row_y - len(_dr_steps) * _dr_row_h - 0.20
ax.text(_dr_x_node - 0.95, _dr_note_y,
"Gözlem B: her düğüm BİR kez delete_min edilir, sonra dondurulur — "
"bir daha dokunulmaz (ağırlık ≥ 0 → mesafe yol boyunca ARTAR).",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold", zorder=5)
ax.text(_dr_x_node - 0.95, _dr_note_y - 0.34,
"Çıkarılma sırası = ARTAN mesafe: s(0) → c(3) → d(5) → a(7) → b(9) "
"(motor order ASSERT). b: ∞→11→10→9 üç turda düşer, son delete_min'de 9.",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700,
style="italic", zorder=5)
fig.suptitle(
"Dijkstra adım izi: en yakını çıkar · gevşet · decrease_key — çıkarma sırası = artan mesafe",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(5.4, 8.95,
"çalışılan örnek (Ku L13 §6) · ChangeablePQ (delete_min / decrease_key, O((V+E) log V))",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.6, 11.4)
ax.set_ylim(_dr_note_y - 0.65, 9.15)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 7. Doğruluk: İki Gözlem {#sec-7-dogruluk-iki-gozlem}
**İddia:** algoritma sonunda tüm $v$ için $d(s, v) = \delta(s, v)$. İki gözleme dayanır:
- **Gözlem A:** gevşetme bir kez $d$'yi gerçek $\delta$'ya eşitlerse, sonda da öyle kalır. Çünkü gevşetme yalnız **düşürür** ve **güvenlidir** (relaxation safe, Ders 16): tahmin daima gerçek bir yolun ağırlığı veya $\infty$ — en kısa mesafenin altına inemez.
> *"relaxation is safe."* — Ku, 41:57
- **Gözlem B:** bir düğüm Q'dan **çıkarıldığında** tahmini zaten $\delta$'dır. Tüm düğümler çıkarıldığından, hepsi doğru olur.
> *"it suffices to show that my estimate equals the shortest distance when v is removed from the Q."* — Ku, 43:02
**Çalışılan Örnek — kanıt (tümevarım).** Q'dan çıkarılan ilk $k$ düğüm üzerinde tümevarım. Temel ($k = 1$): ilk çıkan $s$, $d(s) = 0 = \delta$. Adım: $v'$, $k'$. çıkan düğüm; $s \to v'$ en kısa yolunda, Q'dan henüz çıkmamış ilk düğüm $y$, öncülü $x$ ise — $x$ çıkmış olduğundan (tümevarım) $d(x) = \delta(x)$, ve $y$, $x$'in en kısa yolundaki ardılı olduğundan $d(y) = \delta(y)$. Negatif olmayan ağırlık → $\delta(y) \leq \delta(v')$. Güvenlilik → $d(v') \geq \delta(v')$. Ve $v'$ minimum çıkarıldığından $d(v') \leq d(y) = \delta(y) \leq \delta(v')$. Tüm eşitsizlikler eşitliğe sıkışır → $d(v') = \delta(v')$. ✓ (Burada **negatif olmayan ağırlık şart** — Gözlem 1'in özü.)
@fig-correctness bu zinciri görselleştirir: üstte $s \ldots x \to y \ldots v'$ en kısa yol şeması (çıkmış düğümler dolu, kuyruktakiler beyaz), altta sıkışan eşitsizlik zinciri $\delta(v') \leq d(v') \leq d(y) = \delta(y) \leq \delta(v')$ ve her bağın gerekçesi. Son bağ ($\delta(y) \leq \delta(v')$) **ağırlık $\geq 0$**'a dayanır — negatif olsaydı tam burada kırılırdı. Motor, bağımsız bir çapraz kanıt olarak Dijkstra ile Bellman-Ford'un aynı örnekte birebir aynı $\delta$'yı verdiğini doğrular.
```{python}
#| label: fig-correctness
#| fig-cap: "Dijkstra doğruluğu: SIKIŞAN eşitsizlik zinciri → d(v′) = δ(v′) (L13 §7 İMZA). ÜST ŞERİT: en kısa yol şeması s … x (çıkmış, d=δ rozeti) → y (kuyrukta İLK, d(y)=δ(y)) … v′ (şimdi çıkarılıyor); çıkmış düğümler slate DOLU, kuyruktakiler BEYAZ. ALT: eşitsizlik zinciri büyük kutu δ(v′) ≤ d(v′) ≤ d(y) = δ(y) ≤ δ(v′), her bağın altında gerekçe — güvenli gevşetme / minimum çıkarıldı / tümevarım / AĞIRLIK ≥ 0 (sonuncusu amber: negatifte tam burada çöker); sıkışma çemberi en sol ve en sağ δ(v′) aynı → HEPSİ EŞİT → d(v′) = δ(v′). ALT NOT (Ku 43:02 + 41:57): son bağ y'nin v′ yolunun ön-eki olmasına dayanır (ön-ek ≤ tam yol, ağırlık negatif değilse); negatifte δ(y) > δ(v′) olabilir → zincir KIRILIR. Bağımsız çapraz kanıt — motor iki algoritmayı da çalıştırdı: dijkstra == bellman_ford == {s:0, c:3, d:5, a:7, b:9} BİREBİR."
#| fig-width: 10.6
#| fig-height: 6.6
# fig-correctness (L13 §7 İMZA): sıkışan eşitsizlik zinciri + çapraz kanıt.
# Veri MOTORDAN (build_dijkstra_example / dijkstra / bellman_ford_classic). networkx YOK.
_CO_R = 0.30
_CO_CHAIN_TERMS = [r"$\delta(v')$", r"$d(v')$", r"$d(y)$", r"$\delta(y)$", r"$\delta(v')$"]
_CO_CHAIN_RELS = ["≤", "≤", "=", "≤"]
_CO_CHAIN_WHY = [
("güvenli gevşetme", False),
("minimum çıkarıldı", False),
("tümevarım", False),
("AĞIRLIK ≥ 0", True),
]
def _co_draw_path_node(ax, x, y, label, state, sub=None):
if state == "extracted":
fc, ec, tc, lw = COL_PRIMARY, COL_PRIMARY, COL_WHITE, 2.2
elif state == "y":
fc, ec, tc, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.8
else:
fc, ec, tc, lw = COL_WHITE, COL_SLATE_400, COL_SLATE_500, 1.8
ax.add_patch(Circle((x, y), _CO_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, label, ha="center", va="center", fontsize=12,
color=tc, weight="bold", zorder=6)
if sub is not None:
ax.text(x, y - _CO_R - 0.20, sub, ha="center", va="center",
fontsize=7.8, color=COL_SLATE_500, style="italic", zorder=6)
def _co_draw_path_strip(ax, y_strip):
xs, xx, xy, xv = 0.0, 1.7, 4.7, 6.4
def edge(x0, x1, dashed=False, col=COL_PRIMARY):
ax.add_patch(FancyArrowPatch(
(x0, y_strip), (x1, y_strip), arrowstyle="-|>", mutation_scale=14,
color=col, linewidth=2.0, shrinkA=_CO_R * 74, shrinkB=_CO_R * 74,
linestyle="--" if dashed else "-", zorder=2))
edge(xs, xx, col=COL_PRIMARY)
ax.text((xx + xy) * 0.5, y_strip, "· · ·", ha="center", va="center",
fontsize=15, color=COL_SLATE_400, weight="bold", zorder=3)
ax.add_patch(FancyArrowPatch(
(xx + _CO_R, y_strip), ((xx + xy) * 0.5 - 0.45, y_strip), arrowstyle="-",
color=COL_PRIMARY, linewidth=2.0, zorder=2))
ax.add_patch(FancyArrowPatch(
((xx + xy) * 0.5 + 0.45, y_strip), (xy - _CO_R, y_strip), arrowstyle="-|>",
mutation_scale=14, color=COL_PRIMARY, linewidth=2.0, zorder=2))
edge(xy, xv, dashed=True, col=COL_SLATE_400)
_co_draw_path_node(ax, xs, y_strip, "s", "extracted", sub="kaynak")
_co_draw_path_node(ax, xx, y_strip, "x", "extracted", sub="çıkmış · d=δ")
_co_draw_path_node(ax, xy, y_strip, "y", "y", sub="kuyrukta İLK")
_co_draw_path_node(ax, xv, y_strip, "v′", "queued", sub="şimdi çıkarılıyor")
def badge(x, txt, accent=False):
bw, bh = 1.18, 0.40
ax.add_patch(FancyBboxPatch(
(x - bw * 0.5, y_strip + _CO_R + 0.18), bw, bh,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100 if accent else COL_BG,
ec=COL_ACCENT if accent else COL_PRIMARY,
linewidth=2.0 if accent else 1.4, zorder=4))
ax.text(x, y_strip + _CO_R + 0.18 + bh * 0.5, txt, ha="center",
va="center", fontsize=8.5,
color=COL_AMBER_700 if accent else COL_TEXT, weight="bold", zorder=5)
badge(xx, "d = δ", accent=False)
badge(xy, "d(y) = δ(y)", accent=True)
ax.text(-0.55, y_strip + 0.95,
"v′ çıkarılmak üzere — v′'ye giden bir en kısa yol üzerinde, kuyrukta "
"kalan İLK düğüm = y",
ha="left", va="center", fontsize=9, color=COL_PRIMARY,
weight="bold", zorder=6)
lx = -0.55
ly = y_strip - 1.05
ax.add_patch(Circle((lx + 0.12, ly), 0.13, facecolor=COL_PRIMARY,
edgecolor=COL_PRIMARY, linewidth=1.6, zorder=5))
ax.text(lx + 0.34, ly, "çıkmış (kesinleşti)", ha="left", va="center",
fontsize=8, color=COL_SLATE_500, zorder=5)
ax.add_patch(Circle((lx + 2.85, ly), 0.13, facecolor=COL_WHITE,
edgecolor=COL_SLATE_400, linewidth=1.6, zorder=5))
ax.text(lx + 3.07, ly, "kuyrukta (henüz değil)", ha="left", va="center",
fontsize=8, color=COL_SLATE_500, zorder=5)
return xv
def _co_draw_chain(ax, x0, y0, box_w):
box_h = 1.18
ax.add_patch(FancyBboxPatch(
(x0, y0), box_w, box_h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=2))
n_terms = len(_CO_CHAIN_TERMS)
inner_l = x0 + 0.55
inner_r = x0 + box_w - 0.55
span = inner_r - inner_l
n_slots = 2 * n_terms - 1
slot_xs = [inner_l + span * i / (n_slots - 1) for i in range(n_slots)]
term_y = y0 + box_h * 0.62
term_x = []
for ti in range(n_terms):
sx = slot_xs[2 * ti]
term_x.append(sx)
ax.text(sx, term_y, _CO_CHAIN_TERMS[ti], ha="center", va="center",
fontsize=15.5, color=COL_TEXT, zorder=5)
rel_x = []
for ri in range(len(_CO_CHAIN_RELS)):
sx = slot_xs[2 * ri + 1]
rel_x.append(sx)
amber = _CO_CHAIN_WHY[ri][1]
ax.text(sx, term_y, _CO_CHAIN_RELS[ri], ha="center", va="center",
fontsize=15, color=COL_AMBER_700 if amber else COL_PRIMARY,
weight="bold", zorder=5)
why_y = y0 + box_h * 0.20
for ri, (why, amber) in enumerate(_CO_CHAIN_WHY):
sx = rel_x[ri]
ww, wh = 1.40, 0.34
ax.add_patch(FancyBboxPatch(
(sx - ww * 0.5, why_y - wh * 0.5), ww, wh,
boxstyle="round,pad=0.01,rounding_size=0.07",
fc=COL_AMBER_100 if amber else COL_WHITE,
ec=COL_ACCENT if amber else COL_SLATE_400,
linewidth=1.8 if amber else 1.1, zorder=4))
ax.text(sx, why_y, why, ha="center", va="center", fontsize=7.6,
color=COL_AMBER_700 if amber else COL_SLATE_500,
weight="bold" if amber else "normal", zorder=5)
left_x = term_x[0]
right_x = term_x[-1]
ax.add_patch(FancyArrowPatch(
(left_x, term_y + 0.28), (right_x, term_y + 0.28),
arrowstyle="-", color=COL_ACCENT, linewidth=2.4,
connectionstyle="arc3,rad=-0.42", zorder=6))
ax.text((left_x + right_x) * 0.5, y0 + box_h + 0.68,
"aynı δ(v′) → zincir SIKIŞIR", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=7)
res_y = y0 - 0.55
ax.add_patch(FancyBboxPatch(
(x0 + box_w * 0.5 - 2.35, res_y - 0.30), 4.70, 0.58,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=3))
ax.text(x0 + box_w * 0.5, res_y, r"HEPSİ EŞİT $\Rightarrow$ $d(v') = \delta(v')$",
ha="center", va="center", fontsize=12.5, color=COL_AMBER_700,
weight="bold", zorder=5)
return res_y
# ---- motor verisi + iki bağımsız algoritma eşitliği (çapraz kanıt) ----
_co_adj, _co_w = build_dijkstra_example()
_co_dij = dijkstra(_co_adj, _co_w, "s")
_co_bf = bellman_ford_classic(_co_adj, _co_w, "s")
assert _co_dij == _co_bf, (_co_dij, _co_bf) # İKİ ALGORİTMA BİREBİR
assert _co_dij == {"s": 0, "a": 7, "b": 9, "c": 3, "d": 5}, _co_dij
assert all(w >= 0 for w in _co_w.values()), _co_w
fig, ax = plt.subplots(figsize=(10.6, 6.6))
fig.patch.set_facecolor(COL_WHITE)
_co_y_strip = 4.0
_co_draw_path_strip(ax, _co_y_strip)
_co_chain_x0 = 0.10
_co_chain_w = 9.2
_co_chain_y0 = 0.95
_co_res_y = _co_draw_chain(ax, _co_chain_x0, _co_chain_y0, _co_chain_w)
ax.add_patch(FancyArrowPatch(
(_co_chain_x0 + _co_chain_w * 0.5, _co_y_strip - 1.55),
(_co_chain_x0 + _co_chain_w * 0.5, _co_chain_y0 + 1.18 + 0.78),
arrowstyle="-|>", mutation_scale=15, color=COL_AMBER_700,
linewidth=2.2, zorder=2))
_co_note_y = _co_res_y - 0.62
ax.text(_co_chain_x0, _co_note_y,
"Son bağ δ(y) ≤ δ(v′) AĞIRLIK ≥ 0'a dayanır: y, v′'ye giden yolun bir "
"ÖN-EKİ olduğundan ön-ek ≤ tam yol.",
ha="left", va="center", fontsize=8.8, color=COL_TEXT, weight="bold", zorder=5)
ax.text(_co_chain_x0, _co_note_y - 0.33,
"Ağırlık negatif olsaydı δ(y) > δ(v′) olabilir → zincir KIRILIR (Dijkstra "
"tam burada çöker). Ku 43:02 + 41:57.",
ha="left", va="center", fontsize=8.8, color=COL_AMBER_700,
style="italic", zorder=5)
ax.text(_co_chain_x0, _co_note_y - 0.66,
"Bağımsız çapraz kanıt — motor iki algoritmayı da çalıştırdı: "
"dijkstra == bellman_ford == {s:0, c:3, d:5, a:7, b:9} BİREBİR.",
ha="left", va="center", fontsize=8.8, color=COL_SLATE_500,
weight="bold", zorder=5)
fig.suptitle(
"Dijkstra doğruluğu: sıkışan eşitsizlik zinciri → d(v′) = δ(v′)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975)
ax.text(_co_chain_x0 + _co_chain_w * 0.5, _co_y_strip + 1.95,
"çıkarılma sırasına tümevarım · ağırlık ≥ 0 zincirin son bağını taşır · Ku L13 §7",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(-0.9, _co_chain_x0 + _co_chain_w + 0.6)
ax.set_ylim(_co_note_y - 1.05, _co_y_strip + 2.35)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 8. Çalışma Süresi: Öncelik Kuyruğu Seçimi {#sec-8-calisma-suresi}
Algoritma her şeyi kuyruk işlemleriyle yapar: 1 build (B), $V$ delete_min (M her biri), $E$ decrease_key (D her biri):
$$T = B + V \cdot M + E \cdot D$$
Öncelik kuyruğu seçimi sonucu belirler:
- **Array (direct access):** delete_min $O(V)$ (tüm diziyi tara), decrease_key $O(1)$ → $O(V^2)$. Yoğun çizgede ($E \sim V^2$) doğrusal — basit ve iyi.
- **Binary heap (ikili yığın):** delete_min $O(\log V)$, decrease_key $O(\log V)$ (ebeveynle yukarı swap) → $O((V+E) \log V) = O(E \log V)$. Seyrek çizgede iyi.
- **Fibonacci heap:** $O(E + V \log V)$ — hem seyrek hem yoğunda en iyi teorik sınır.
> *"This data structure is called the Fibonacci heap."* — Ku, 55:10
Pratik: Fibonacci heap karmaşıktır, nadiren implemente edilir; çizgenin seyrek/yoğun olduğu bilinirse heap/array yeter. Teori sorusunda $O(E + V \log V)$ sınırını kullan.
@fig-pq-comparison bu üç seçimi tek formül üzerinden karşılaştırır: $T = B + V \cdot \text{delete\_min} + E \cdot \text{decrease\_key}$ formülüne array / binary heap (amber: derste kullanılan) / Fibonacci heap takılır → $O(V^2)$ / $O(E \log V)$ / $O(E + V \log V)$. Seçim çizgenin yoğunluğuna bağlıdır; teori sorusunda en iyi sınır Fibonacci'nin $O(E + V \log V)$'sidir.
```{python}
#| label: fig-pq-comparison
#| fig-cap: "PQ seçimi Dijkstra'nın çalışma süresini belirler: T = B + V·delete_min + E·decrease_key (L13 §8 İMZA). ÜST: genel formül panosu (Ku) — B = kuyruğu kur, V kez delete_min, ≤ E kez decrease_key. 3 PQ satırı: (1) ARRAY (doğrudan erişim) delete_min O(V) / decrease_key O(1) → T = O(V²), yoğun çizgede iyi; (2) BINARY HEAP (amber, ★ derste kullanılan, min-heap + cross-link) ikisi de O(log V) → T = O(E log V), seyrek çizgede iyi; (3) FIBONACCI HEAP (amortize) delete_min O(log V)* / decrease_key O(1)* → T = O(E + V log V), teorik en iyi ama pratikte karmaşık nadiren implemente (Ku 55:10). ALT ŞERİT: PQ seçimi çizgenin YOĞUNLUĞUNA bağlı (yoğunda array O(V²), seyrekte binary heap O(E log V)); teori sorusunda en iyi sınır O(E + V log V) kullan. Veri MOTORDAN: dijkstra(s) = {s:0, c:3, d:5, a:7, b:9}; ChangeablePQ = binary heap is_valid_heap True; delete_min sırası ARTAN mesafe s(0) c(3) d(5) a(7) b(9) (Gözlem B)."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-pq-comparison (L13 §8 İMZA): üç PQ implementasyonu → üç asimptotik.
# Veri MOTORDAN (ChangeablePQ / dijkstra / dijkstra_trace). networkx YOK.
def _pc_draw_dense_icon(ax, ox, oy):
r = 0.085
pts = {0: (ox, oy + 0.34), 1: (ox + 0.50, oy + 0.34),
2: (ox, oy - 0.16), 3: (ox + 0.50, oy - 0.16)}
edges = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
for a, b in edges:
ax.plot([pts[a][0], pts[b][0]], [pts[a][1], pts[b][1]],
color=COL_SLATE_500, linewidth=1.2, zorder=2)
for (px, py) in pts.values():
ax.add_patch(Circle((px, py), r, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=1.3, zorder=3))
ax.text(ox + 0.25, oy - 0.36, "yoğun E ~ V²", ha="center", va="center",
fontsize=7, color=COL_SLATE_500, weight="bold", zorder=3)
def _pc_draw_sparse_icon(ax, ox, oy):
r = 0.085
pts = {0: (ox, oy + 0.12), 1: (ox + 0.30, oy + 0.30),
2: (ox + 0.60, oy + 0.12), 3: (ox + 0.30, oy - 0.18)}
edges = [(0, 1), (1, 2), (1, 3)]
for a, b in edges:
ax.plot([pts[a][0], pts[b][0]], [pts[a][1], pts[b][1]],
color=COL_ACCENT, linewidth=1.4, zorder=2)
for (px, py) in pts.values():
ax.add_patch(Circle((px, py), r, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=1.3, zorder=3))
ax.text(ox + 0.30, oy - 0.36, "seyrek E ~ V", ha="center", va="center",
fontsize=7, color=COL_AMBER_700, weight="bold", zorder=3)
def _pc_op_badge(ax, cx, cy, label, value, accent=False):
bw, bh = 1.92, 0.78
fc = COL_AMBER_100 if accent else COL_WHITE
ec = COL_ACCENT if accent else COL_PRIMARY
ax.add_patch(FancyBboxPatch(
(cx - bw * 0.5, cy - bh * 0.5), bw, bh,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=fc, ec=ec, linewidth=2.0 if accent else 1.5, zorder=4))
ax.text(cx, cy + 0.18, label, ha="center", va="center", fontsize=7.5,
color=COL_SLATE_500, zorder=5)
ax.text(cx, cy - 0.16, value, ha="center", va="center", fontsize=11,
color=COL_AMBER_700 if accent else COL_TEXT, weight="bold",
family="monospace", zorder=5)
def _pc_draw_pq_row(ax, x0, y, w, h, name, sub, dmin, dkey, total, accent, right_kind):
fc = COL_AMBER_100 if accent else COL_BG
ec = COL_ACCENT if accent else COL_PRIMARY
ax.add_patch(FancyBboxPatch(
(x0, y), w, h, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=fc, ec=ec, linewidth=2.6 if accent else 1.6, zorder=2))
name_w = 2.5
ncx = x0 + 0.20 + name_w * 0.5
ncy = y + h * 0.5
ax.add_patch(FancyBboxPatch(
(x0 + 0.20, y + 0.18), name_w, h - 0.36,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_WHITE, ec=COL_ACCENT if accent else COL_PRIMARY,
linewidth=2.2 if accent else 1.6, zorder=3))
ax.text(ncx, ncy + 0.20, name, ha="center", va="center", fontsize=11,
color=COL_AMBER_700 if accent else COL_TEXT, weight="bold", zorder=4)
ax.text(ncx, ncy - 0.22, sub, ha="center", va="center", fontsize=7.5,
color=COL_SLATE_500, style="italic", zorder=4)
if accent:
ax.text(ncx, y + h + 0.16, "★ derste kullanılan", ha="center",
va="center", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=5)
op_cx1 = x0 + 3.55
op_cx2 = x0 + 5.65
_pc_op_badge(ax, op_cx1, ncy, "delete_min (V kez)", dmin, accent=accent)
_pc_op_badge(ax, op_cx2, ncy, "decrease_key (≤ E)", dkey, accent=accent)
ax.text((x0 + 3.55 + 4.61) * 0.5, ncy, "+", ha="center", va="center",
fontsize=13, color=COL_SLATE_500, weight="bold", zorder=4)
tw, th = 2.55, 0.86
tcx = x0 + 8.35
ax.add_patch(FancyBboxPatch(
(tcx - tw * 0.5, ncy - th * 0.5), tw, th,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_700 if accent else COL_PRIMARY, ec=COL_AMBER_700,
linewidth=2.0, zorder=4))
ax.text(tcx, ncy + 0.17, "T =", ha="center", va="center", fontsize=8,
color=COL_WHITE, zorder=5)
ax.text(tcx, ncy - 0.16, total, ha="center", va="center", fontsize=12.5,
color=COL_WHITE, weight="bold", family="monospace", zorder=5)
ax.text(x0 + 6.95, ncy, "→", ha="center", va="center", fontsize=14,
color=COL_AMBER_700 if accent else COL_SLATE_500, weight="bold", zorder=4)
rx = x0 + w - 1.55
if right_kind == "dense":
_pc_draw_dense_icon(ax, rx, ncy + 0.05)
ax.text(rx + 0.25, ncy + 0.62, "yoğun çizgede iyi", ha="center",
va="center", fontsize=8, color=COL_PRIMARY, weight="bold", zorder=4)
elif right_kind == "sparse":
_pc_draw_sparse_icon(ax, rx - 0.15, ncy + 0.05)
ax.text(rx + 0.15, ncy + 0.62, "seyrek çizgede iyi", ha="center",
va="center", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=4)
else:
ntx = rx + 0.42
ax.text(ntx, ncy + 0.34, "teorik en iyi", ha="center", va="center",
fontsize=8, color=COL_PRIMARY, weight="bold", zorder=4)
ax.text(ntx, ncy + 0.04, "ama pratikte karmaşık,", ha="center",
va="center", fontsize=7.5, color=COL_SLATE_500, style="italic", zorder=4)
ax.text(ntx, ncy - 0.24, "nadiren implemente (Ku 55:10)", ha="center",
va="center", fontsize=7.5, color=COL_SLATE_500, style="italic", zorder=4)
# ---- motor bağlantısı: ChangeablePQ (binary heap) + ASSERT ----
_pc_adj, _pc_w = build_dijkstra_example()
_pc_d = dijkstra(_pc_adj, _pc_w, "s")
assert _pc_d == {"s": 0, "c": 3, "d": 5, "a": 7, "b": 9}, _pc_d
_pc_pq = ChangeablePQ((v, (0 if v == "s" else INF)) for v in _pc_adj)
assert _pc_pq.is_valid_heap(), "ChangeablePQ geçerli min-heap olmalı"
assert len(_pc_pq) == len(_pc_adj)
_pc_tr = dijkstra_trace(_pc_adj, _pc_w, "s")
_pc_order_ids = [u for (u, _) in _pc_tr["order"]]
_pc_order_keys = [k for (_, k) in _pc_tr["order"]]
assert _pc_order_ids == ["s", "c", "d", "a", "b"], _pc_order_ids
assert _pc_order_keys == [0, 3, 5, 7, 9] == sorted(_pc_order_keys), _pc_order_keys
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
_pc_x0 = 0.0
_pc_row_w = 11.5
_pc_row_h = 1.30
_pc_row_gap = 0.42
_pc_top_y = 3.0
_pc_form_y = _pc_top_y + _pc_row_h + 1.05
_pc_fw, _pc_fh = _pc_row_w, 0.96
ax.add_patch(FancyBboxPatch(
(_pc_x0, _pc_form_y), _pc_fw, _pc_fh, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=2))
ax.text(_pc_x0 + _pc_fw * 0.5, _pc_form_y + _pc_fh * 0.60,
"T = B + V · delete_min + E · decrease_key",
ha="center", va="center", fontsize=15, color=COL_TEXT,
weight="bold", family="monospace", zorder=4)
ax.text(_pc_x0 + _pc_fw * 0.5, _pc_form_y + _pc_fh * 0.18,
"B = kuyruğu kur (build) · V kez en yakını çıkar (delete_min) ·"
" ≤ E kez gevşetmede güncelle (decrease_key) — Ku L13 §8",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, zorder=4)
_pc_rows = [
("ARRAY", "(doğrudan erişim)", "O(V)", "O(1)", "O(V²)", False, "dense"),
("BINARY HEAP", "(min-heap + cross-link)", "O(log V)", "O(log V)",
"O(E log V)", True, "sparse"),
("FIBONACCI HEAP", "(amortize)", "O(log V)*", "O(1)*",
"O(E + V log V)", False, "note"),
]
for _idx, (_name, _sub, _dmin, _dkey, _total, _accent, _rk) in enumerate(_pc_rows):
_y = _pc_top_y - _idx * (_pc_row_h + _pc_row_gap)
_pc_draw_pq_row(ax, _pc_x0, _y, _pc_row_w, _pc_row_h, _name, _sub, _dmin,
_dkey, _total, _accent, _rk)
_pc_fib_y = _pc_top_y - 2 * (_pc_row_h + _pc_row_gap)
ax.text(_pc_x0 + 0.20, _pc_fib_y - 0.18,
"* Fibonacci heap: delete_min / decrease_key AMORTİZE sınırları "
"(decrease_key amortize O(1) → toplamda V·log V baskın)",
ha="left", va="center", fontsize=7.8, color=COL_SLATE_500,
style="italic", zorder=4)
_pc_note_y = _pc_fib_y - 0.70
ax.add_patch(FancyBboxPatch(
(_pc_x0, _pc_note_y - 0.50), _pc_row_w, 0.92,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
ax.text(_pc_x0 + 0.30, _pc_note_y + 0.18,
"PQ seçimi çizgenin YOĞUNLUĞUNA bağlı: yoğunda array O(V²) · "
"seyrekte binary heap O(E log V).",
ha="left", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(_pc_x0 + 0.30, _pc_note_y - 0.22,
"Teori sorusunda en iyi sınır olarak O(E + V · log V) (Fibonacci) "
"kullan — asimptotik tavan budur.",
ha="left", va="center", fontsize=8.8, color=COL_TEXT, zorder=4)
fig.suptitle(
"PQ seçimi Dijkstra'nın çalışma süresini belirler: "
"T = B + V·delete_min + E·decrease_key",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(_pc_x0 + _pc_row_w * 0.5, _pc_form_y + _pc_fh + 0.30,
"aynı algoritma, üç farklı öncelik kuyruğu → üç farklı asimptotik · "
"Ku L13 §8 (motor: ChangeablePQ = binary heap)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=4)
ax.set_xlim(-0.4, _pc_row_w + 0.7)
ax.set_ylim(_pc_note_y - 0.85, _pc_form_y + _pc_fh + 0.55)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
@fig-negative-breaks Dijkstra'nın dayandığı kabulü sentezler: ağırlık $\geq 0$ kalktığında ne olur. Örnek çizgeye negatif bir $b \to c$ ($-8$) kenarı eklenir (negatif çevrim $b \to c \to d \to b = -1$). "Kesinleştir, bir daha dokunma" Dijkstra ($c$'yi 3'te dondurur) bu kenarı görmez ve orijinal sonlu yanıtı verir — **yanlış**; oysa Bellman-Ford negatif çevrimden erişilen herkesi $-\infty$ işaretler. Bu, **Ders 20'deki PS6 (Solomon) Problem 1**'in köprüsüdür — orada bu çizge elle adım adım işlenir.
```{python}
#| label: fig-negative-breaks
#| fig-cap: "Negatif kenar Dijkstra'yı KIRAR — \"kesinleştir, bir daha dokunma\" varsayımı çöker (L13 sentez + PS6 köprüsü). SOL: örnek çizge + eklenen b→c(−8) kalın kırık amber kenar; Dijkstra işleme sırası rozetleri (#1..#5); c \"d[c]=3'te DONDURULDU (#2)\" kilit ikonu; b işlenince (#5) b→c üzerinden 9 + (−8) = 1 < 3 keşfi (kesik amber ok) ama c donmuş → dokunulamaz (YASAK işareti); negatif çevrim b→c→d→b = −8+2+5 = −1; Solomon PS6 4:49 \"zamanda donar\" notu. SAĞ: karşılaştırma tablosu düğüm / Dijkstra / Bellman-Ford (motor değerleri BİREBİR); fark hücreleri amber (s hariç tüm düğümler). ALT NOT: ağırlık ≥ 0 varsayımı kırılınca Gözlem 1 düşer → kesinleştirme yanlış; çözüm Bellman-Ford (Ders 18); PS6 Problem 1 elle işler (Ders 20 teaser). Veri MOTORDAN: dijkstra(finalize) = {s:0,a:7,b:9,c:3,d:5} (YANLIŞ), bellman_ford_classic = {s:0, a,b,c,d:−∞} (DOĞRU); fark = {a,b,c,d}; donmuş keşif 9+(−8)=1<3; çevrim = −1."
#| fig-width: 11.0
#| fig-height: 6.8
# fig-negative-breaks (L13 sentez + PS6 köprüsü): negatif kenar kabulü kırar.
# Veri MOTORDAN (build_dijkstra_example + b→c(−8) / bellman_ford_classic). networkx YOK.
_NB_POS = {
"s": (0.0, 1.0), "c": (1.0, 0.4), "a": (1.0, 1.6),
"d": (2.0, 0.4), "b": (2.6, 1.0),
}
_NB_R = 0.22
def _nb_build_neg_graph():
adj0, w0 = build_dijkstra_example()
adj = {k: list(v) for k, v in adj0.items()}
weight = dict(w0)
adj["b"].append("c")
weight[("b", "c")] = -8
return adj, weight
def _nb_dijkstra_finalize(adj, weight, s):
"""L13 §6 açgözlü Dijkstra, donmuş düğümü ATLAR — negatif kenarda çökmeden
devam eder ama YANLIŞ sonuç verir (kesinleştirme varsayımı kırıldı)."""
d = {v: INF for v in adj}
d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
finalized = set()
order = []
while len(Q):
u, ku = Q.delete_min()
finalized.add(u)
order.append(u)
for v in adj[u]:
if v in finalized:
continue
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
Q.decrease_key(v, d[v])
return d, order
def _nb_draw_lock(ax, x, y, s=0.10):
ax.add_patch(FancyBboxPatch(
(x - s, y - s), 2 * s, 1.7 * s,
boxstyle="round,pad=0.005,rounding_size=0.02",
fc=COL_AMBER_300, ec=COL_AMBER_700, linewidth=1.4, zorder=8))
arc = FancyArrowPatch(
(x - s * 0.6, y + 0.7 * s), (x + s * 0.6, y + 0.7 * s),
connectionstyle="arc3,rad=-1.0", arrowstyle="-",
mutation_scale=1, color=COL_AMBER_700, linewidth=1.6, zorder=8)
ax.add_patch(arc)
ax.plot([x], [y + 0.35 * s], marker="o", markersize=2.2,
color=COL_AMBER_700, zorder=9)
def _nb_draw_forbidden(ax, x, y, r=0.15):
ax.add_patch(Circle((x, y), r, facecolor="none", edgecolor=COL_AMBER_700,
linewidth=2.4, zorder=9))
dd = r * 0.72
ax.plot([x - dd, x + dd], [y + dd, y - dd], color=COL_AMBER_700,
linewidth=2.4, zorder=9)
def _nb_draw_graph(ax, ox, oy, adj, weight, order):
def P(v):
x, y = _NB_POS[v]
return (ox + x, oy + y)
proc_idx = {v: i + 1 for i, v in enumerate(order)}
for u in adj:
for v in adj[u]:
wt = weight[(u, v)]
ux, uy = P(u)
vx, vy = P(v)
is_neg = (u, v) == ("b", "c")
cstyle = "arc3,rad=-0.30" if is_neg else "arc3,rad=0.0"
ecol = COL_ACCENT if is_neg else COL_PRIMARY
ax.add_patch(FancyArrowPatch(
(ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=12,
color=ecol, linewidth=2.8 if is_neg else 1.6,
linestyle=(0, (4, 2)) if is_neg else "-",
shrinkA=_NB_R * 70, shrinkB=_NB_R * 70,
connectionstyle=cstyle, zorder=3 if is_neg else 2))
if is_neg:
mx, my = (ux + vx) * 0.5 - 0.30, (uy + vy) * 0.5 + 0.02
else:
mx, my = (ux + vx) * 0.5, (uy + vy) * 0.5
tcol = COL_AMBER_700 if is_neg else COL_TEXT
ax.add_patch(FancyBboxPatch(
(mx - 0.145, my - 0.115), 0.29, 0.23,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100 if is_neg else COL_WHITE,
ec=COL_ACCENT if is_neg else COL_SLATE_400,
linewidth=1.8 if is_neg else 1.0, zorder=6))
ax.text(mx, my, str(wt), ha="center", va="center",
fontsize=8.5 if is_neg else 8,
color=tcol, weight="bold", zorder=7)
for v, (x, y) in _NB_POS.items():
is_src = (v == "s")
is_frozen = (v == "c")
px, py = P(v)
if is_src:
fc, ec, tc, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.6
elif is_frozen:
fc, ec, tc, lw = COL_BG, COL_ACCENT, COL_TEXT, 2.6
else:
fc, ec, tc, lw = COL_BG, COL_PRIMARY, COL_TEXT, 1.8
ax.add_patch(Circle((px, py), _NB_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(px, py, v, ha="center", va="center", fontsize=11,
color=tc, weight="bold", zorder=6)
n = proc_idx[v]
bx, by = px - _NB_R - 0.04, py + _NB_R + 0.04
ax.add_patch(Circle((bx, by), 0.105, facecolor=COL_PRIMARY,
edgecolor=COL_WHITE, linewidth=1.2, zorder=7))
ax.text(bx, by, f"#{n}", ha="center", va="center", fontsize=6.2,
color=COL_WHITE, weight="bold", zorder=8)
sx, sy = P("s")
ax.text(sx - _NB_R - 0.14, sy, "kaynak", ha="right", va="center",
fontsize=7, color=COL_AMBER_700, weight="bold", zorder=6)
cx, cy = P("c")
_nb_draw_lock(ax, cx + _NB_R + 0.16, cy - 0.30)
ax.text(cx + _NB_R + 0.36, cy - 0.30, "d[c]=3'te\nDONDURULDU (#2)",
ha="left", va="center", fontsize=7, color=COL_AMBER_700,
weight="bold", zorder=7)
_nb_draw_forbidden(ax, cx, cy + _NB_R + 0.06, r=0.135)
ax.text(ox - 0.30, cy + 0.18, "9 + (−8) = 1 < 3", ha="center", va="center",
fontsize=7.5, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=8)
ax.text(ox - 0.30, cy - 0.04, "keşif ama c donmuş", ha="center", va="center",
fontsize=6.8, color=COL_AMBER_700, style="italic", zorder=8)
ax.text(ox - 0.30, cy - 0.24, "→ dokunulamaz", ha="center", va="center",
fontsize=6.8, color=COL_AMBER_700, style="italic", zorder=8)
ax.add_patch(FancyArrowPatch(
(ox + 0.10, cy + 0.12), (cx - _NB_R - 0.02, cy + 0.10), arrowstyle="-|>",
mutation_scale=9, color=COL_AMBER_700, linewidth=1.3,
linestyle=(0, (3, 2)), zorder=4))
ax.text(ox + 1.25, oy - 0.30,
"negatif çevrim b→c→d→b = −8+2+5 = −1", ha="center", va="center",
fontsize=7.2, color=COL_AMBER_700, style="italic", weight="bold", zorder=6)
ax.text(ox + 1.25, oy + 2.34,
"Solomon PS6 4:49 — kesinleştirilen düğüm \"zamanda donar\"",
ha="center", va="center", fontsize=7, color=COL_SLATE_500,
style="italic", zorder=6)
def _nb_draw_compare_table(ax, ox, oy, nodes, d_dij, d_bf, diff_nodes):
col_w = [0.95, 1.55, 1.55]
row_h = 0.52
x_edges = [ox]
for w in col_w:
x_edges.append(x_edges[-1] + w)
table_w = sum(col_w)
headers = ["düğüm", "Dijkstra", "Bellman-Ford"]
hy = oy
for c, htxt in enumerate(headers):
ax.add_patch(FancyBboxPatch(
(x_edges[c] + 0.02, hy - row_h), col_w[c] - 0.04, row_h,
boxstyle="square,pad=0.0", fc=COL_PRIMARY, ec=COL_PRIMARY,
linewidth=1.2, zorder=3))
ax.text(x_edges[c] + col_w[c] * 0.5, hy - row_h * 0.5, htxt,
ha="center", va="center", fontsize=9, color=COL_WHITE,
weight="bold", zorder=4)
def fmt(val):
if val == INF:
return "+∞"
if val == -INF:
return "−∞"
return str(val)
for r, v in enumerate(nodes):
ry = oy - (r + 2) * row_h
is_diff = v in diff_nodes
cells = [v, fmt(d_dij[v]), fmt(d_bf[v])]
for c, txt in enumerate(cells):
if c == 0:
fc, ec, tcol, lw = COL_BG, COL_SLATE_400, COL_TEXT, 1.0
elif is_diff:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 1.8
else:
fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_TEXT, 1.0
ax.add_patch(FancyBboxPatch(
(x_edges[c] + 0.02, ry), col_w[c] - 0.04, row_h - 0.02,
boxstyle="square,pad=0.0", fc=fc, ec=ec, linewidth=lw, zorder=3))
ax.text(x_edges[c] + col_w[c] * 0.5, ry + row_h * 0.5, txt,
ha="center", va="center", fontsize=10, color=tcol,
weight="bold" if (c > 0 and is_diff) else
("bold" if c == 0 else "normal"),
family="monospace" if c > 0 else "sans-serif", zorder=4)
ax.text(ox + table_w * 0.5, oy + 0.30,
"Aynı çizge — iki algoritma, FARKLI yanıt", ha="center", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold", zorder=4)
ly = oy - (len(nodes) + 1) * row_h - 0.20
ax.add_patch(FancyBboxPatch(
(ox + 0.05, ly - 0.10), 0.26, 0.20, boxstyle="square,pad=0.0",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.8, zorder=3))
ax.text(ox + 0.40, ly, "= fark (Dijkstra yanlış) · s hariç tüm düğümler",
ha="left", va="center", fontsize=7.8, color=COL_AMBER_700,
style="italic", zorder=4)
return table_w
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_nb_adj, _nb_w = _nb_build_neg_graph()
_nb_d_dij, _nb_order = _nb_dijkstra_finalize(_nb_adj, _nb_w, "s")
_nb_d_bf = bellman_ford_classic(_nb_adj, _nb_w, "s")
assert _nb_order == ["s", "c", "d", "a", "b"], _nb_order
assert _nb_d_dij == {"s": 0, "a": 7, "b": 9, "c": 3, "d": 5}, _nb_d_dij
assert _nb_d_bf == {"s": 0, "a": -INF, "b": -INF, "c": -INF, "d": -INF}, _nb_d_bf
_nb_diff = {v for v in _nb_adj if _nb_d_dij[v] != _nb_d_bf[v]}
assert _nb_diff == {"a", "b", "c", "d"}, _nb_diff
assert _nb_d_dij["b"] + _nb_w[("b", "c")] == 1
assert 1 < _nb_d_dij["c"]
assert _nb_w[("b", "c")] + _nb_w[("c", "d")] + _nb_w[("d", "b")] == -1
fig, ax = plt.subplots(figsize=(11.0, 6.8))
fig.patch.set_facecolor(COL_WHITE)
_nb_gx, _nb_gy = 0.0, 0.0
_nb_draw_graph(ax, _nb_gx, _nb_gy, _nb_adj, _nb_w, _nb_order)
_nb_tx, _nb_ty = 4.7, 2.55
_nb_nodes = ["s", "a", "b", "c", "d"]
_nb_draw_compare_table(ax, _nb_tx, _nb_ty, _nb_nodes, _nb_d_dij, _nb_d_bf, _nb_diff)
fig.suptitle(
"Negatif kenar Dijkstra'yı KIRAR — \"kesinleştir, bir daha dokunma\" varsayımı çöker",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(_nb_gx + 1.25, _nb_gy + 2.62,
"örnek çizgeye b→c(−8) eklendi · Ku L13 sentez + PS6 Problem 1 köprüsü",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
_nb_note_y = _nb_gy - 0.95
ax.text(_nb_gx, _nb_note_y,
"Ağırlık ≥ 0 varsayımı KIRILINCA Gözlem 1 (mesafe yol boyunca artar) "
"düşer → kesinleştirme yanlış: donmuş düğüme daha iyi yol",
ha="left", va="center", fontsize=8.6, color=COL_TEXT, weight="bold", zorder=5)
ax.text(_nb_gx, _nb_note_y - 0.32,
"sonradan bulunsa da güncellenmez. Çözüm: Bellman-Ford (Ders 18) — "
"negatif kenar + çevrimi işler. PS6 Problem 1 bunu",
ha="left", va="center", fontsize=8.6, color=COL_SLATE_500, zorder=5)
ax.text(_nb_gx, _nb_note_y - 0.62,
"elle adım adım çalıştırır (Ders 20 teaser). Motor: dijkstra(finalize) "
"≠ bellman_ford_classic, fark = {a, b, c, d}.",
ha="left", va="center", fontsize=8.6, color=COL_AMBER_700,
style="italic", weight="bold", zorder=5)
ax.set_xlim(-1.05, _nb_tx + 4.3)
ax.set_ylim(_nb_note_y - 0.95, _nb_gy + 2.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d19}
1. **Dijkstra**: negatif olmayan ağırlıklı SSSP; BFS'in genellemesi; ~doğrusal.
2. **Gözlem 1**: ağırlık $\geq 0$ → mesafe en kısa yol boyunca (zayıf) artar.
3. **Gözlem 2**: artan sıra bilinirse → DAG relaxation (0-ağırlık birleştir/çevir).
4. **Değiştirilebilir öncelik kuyruğu**: build / delete_min / decrease_key (id + key, cross-link sözlük).
5. **Algoritma**: $d = \infty$, $d(s) = 0$; en yakını çıkar, kenarları gevşet, `decrease_key` ile güncelle.
6. **Doğruluk**: gevşetme güvenli + Q'dan çıkınca $\delta$; negatif olmayan ağırlık şart.
7. **Süre**: $B + V \cdot M + E \cdot D$ → array $O(V^2)$ / heap $O(E \log V)$ / Fibonacci $O(E + V \log V)$.
::: {.callout-important title="Tek Bir Cümle"}
Dijkstra, negatif olmayan ağırlıkta "mesafe en kısa yol boyunca artar" gözlemini kullanır: düğümleri bir öncelik kuyruğundan artan mesafe sırasında çeker, kenarlarını gevşetir, böylece SSSP'yi $O(E + V \log V)$'de — BFS'in ağırlıklı genellemesi olarak — çözer.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d19}
::: {.callout-note collapse="true" title="Soru 1: Dijkstra neden negatif ağırlıklarda çalışmaz? Hangi gözlem çöker?"}
**Cevap:**
Dijkstra, **Gözlem 1**'e (ağırlık $\geq 0$ → mesafe en kısa yol boyunca artar) dayanır; bu sayede "en yakın düğümü kesinleştir, bir daha dokunma" açgözlü stratejisi doğrudur. Negatif ağırlık olsaydı, çok uzaktaki bir düğüm negatif bir kenarla beklenenden daha kısa bir yola sahip olabilirdi — yani Q'dan erken çıkarılan bir düğümün mesafesi sonradan daha da kısalabilirdi, kesinleştirme yanlış olurdu. Doğruluk kanıtındaki "$\delta(y) \leq \delta(v')$" adımı tam olarak negatif olmayan ağırlığı kullanır; negatif ağırlıkta bu eşitsizlik bozulur. (Negatif için Bellman-Ford gerekir.)
:::
::: {.callout-note collapse="true" title="Soru 2: \"Değiştirilebilir öncelik kuyruğu\" normal öncelik kuyruğundan nasıl farklı, neden gerekli?"}
**Cevap:**
Normal öncelik kuyruğu yalnız build ve delete_min sunar; bir öğenin anahtarını *sonradan* değiştiremezsin. Dijkstra'da bir düğümün mesafe tahmini gevşetmeyle düşer — bu yüzden **decrease_key(id, k)** gerekir: belirli bir düğümü (id) bulup anahtarını (key) düşürmek. İmplementasyon: normal öncelik kuyruğu + bir sözlük (id → kuyruktaki konum) cross-link; böylece id'den konumu $O(1)$ bulup yığını güncelleriz. Düğüm id'leri $0 \ldots V-1$ ise sözlük yerine direct access array → kesin $O(1)$.
:::
::: {.callout-note collapse="true" title="Soru 3: Dijkstra'nın çalışma süresi neden öncelik kuyruğu seçimine bağlı? Hangi durumda hangisi?"}
**Cevap:**
Toplam süre $T = B + V \cdot \text{delete\_min} + E \cdot \text{decrease\_key}$. delete_min ve decrease_key maliyetleri kuyruk implementasyonuna göre değişir: **Array** → delete_min $O(V)$, decrease_key $O(1)$ → $O(V^2)$, **yoğun** çizgede ($E \sim V^2$) en iyi. **Binary heap** → ikisi de $O(\log V)$ → $O(E \log V)$, **seyrek** çizgede en iyi. **Fibonacci heap** → $O(E + V \log V)$, her durumda en iyi teorik ama pratikte karmaşık. Yani "en hızlı" çizgenin yoğunluğuna bağlıdır; teori sorusunda $O(E + V \log V)$ sınırı verilir.
:::
::: {.callout-note collapse="true" title="Soru 4: Gözlem 2'de \"artan mesafe sırası bilinirse DAG relaxation\" derken 0-ağırlıklı kenarlar neden sorun, nasıl çözülür?"}
**Cevap:**
Sıralama, "geriye giden kenar atılır" mantığına dayanır; ama 0-ağırlıklı bir kenar iki düğümü **aynı** mesafede bırakır, yani sırada hangisinin önce geldiği belirsizdir ve "geriye kenar" olabilir. Çözüm: aynı mesafedeki düğümleri 0-ağırlıklı kenara göre **yeniden sırala** (kenar ileri gidecek şekilde); bir **0-ağırlıklı çevrim** varsa, o çevrimdeki tüm düğümleri tek bir düğüme **birleştir (coalesce)** — birine ulaşmak hepsine ulaşmaktır. Böylece çizge geçerli bir topolojik sıraya ve DAG'a iner.
:::
## Egzersizler {#sec-egzersizler-d19}
**Egzersiz 1.** Küçük bir pozitif-ağırlıklı çizgede Dijkstra'yı elle çalıştır: her adımda Q'dan çıkan düğümü, gevşetilen kenarları ve güncel $d$ değerlerini yaz.
**Egzersiz 2.** Değiştirilebilir öncelik kuyruğunu binary heap + direct access array ile Python'da implemente et (build / delete_min / decrease_key); decrease_key'in $O(\log V)$ olduğunu doğrula.
**Egzersiz 3.** Aynı çizgede Dijkstra'yı array, binary heap ve (kavramsal) Fibonacci heap sınırlarıyla karşılaştır; çizge seyrek/yoğun iken hangisinin kazandığını göster.
**Egzersiz 4.** Bir negatif kenarlı küçük çizge bul; Dijkstra'nın neden yanlış sonuç verdiğini, hangi düğümün erken kesinleştiğini adım adım göster.
**Egzersiz 5.** Dijkstra'ya ebeveyn işaretçisi ekle (gevşetirken $P(v) = u$); algoritma sonunda en kısa yol ağacını yeniden kur.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d19}
::: {.callout-warning title="Sonraki: Ders 21 (L14) — Tüm-Çiftler En Kısa Yollar (APSP)"}
**Ders 21 (L14): Tüm-Çiftler En Kısa Yollar (APSP)** — Jason Ku ile, tek kaynak yerine **tüm düğüm çiftleri** arasında en kısa yol. (Araya **Ders 20 = PS6** problem oturumu girer.) Naif yol: her düğümden Dijkstra/Bellman-Ford. Daha akıllısı **Johnson algoritması**: negatif ağırlıkları, bir potansiyel fonksiyonla negatif-olmayana "yeniden ağırlıklandırıp" Dijkstra'yı $V$ kez çalıştırmak.
**Ders 21 Öncesi Yapılacak:**
- Bu dersin egzersizlerini, özellikle Egzersiz 1 (elle Dijkstra) ve 2 (değiştirilebilir PQ) çöz.
- Üç çalışma süresi sınırını (array/heap/Fibonacci) ve hangi çizgede hangisi olduğunu ezberle.
- Ana cümleyi tekrar oku: *"Negatif yoksa mesafe artar; en yakını çek, gevşet, decrease_key."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d19}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **Dijkstra kapsamı** | Negatif olmayan ağırlıklı SSSP; BFS genellemesi | Böl. 1 |
| **Gözlem 1** | Ağırlık $\geq 0$ → mesafe en kısa yol boyunca artar | Böl. 2 |
| **Gözlem 2** | Artan sıra bilinirse → DAG relaxation | Böl. 3 |
| **Değiştirilebilir PQ** | build / delete_min / decrease_key (id + key) | Böl. 5 |
| **Dijkstra döngüsü** | En yakını çıkar → kenarları gevşet → decrease_key | Böl. 6 |
| **Doğruluk** | Gevşetme güvenli + Q'dan çıkınca $\delta$; negatif yok şart | Böl. 7 |
| **Array PQ** | $O(V^2)$; yoğun çizgede iyi | Böl. 8 |
| **Heap / Fibonacci** | $O(E \log V)$ / $O(E + V \log V)$ | Böl. 8 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d19}
::: {.callout-tip title="6 köprü"}
Bu ders, "negatif yoksa mesafe artar" gözlemiyle açgözlü SSSP'yi kurar ve değiştirilebilir öncelik kuyruğu ile neredeyse doğrusal süreye iner — köprülerin özeti:
1. **Dijkstra** → GPS/yönlendirme (Google Maps, Waze), ağ link-state (OSPF), oyun yol bulma.
2. **Sezgisel arama** → Dijkstra + heuristic = `A*`; robot hareket planlama, video oyunu NPC, harita rotalama.
3. **Değiştirilebilir öncelik kuyruğu** → olay simülasyonu (event queue), zamanlayıcı, Prim MST.
4. **Açgözlü + güvenli gevşetme** → açgözlü algoritma kanıt deseni (exchange argument).
5. **PQ veri yapısı seçimi** → seyrek/yoğun bilinciyle karmaşıklık ayarı; gerçek sistemde profil-temelli seçim.
6. **Fibonacci heap** → teorik optimal vs pratik basitlik; "asimptotik en iyi her zaman pratik en iyi değildir".
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
Dijkstra'nın sırrı tek bir gözlemdir — negatif ağırlık yoksa mesafe en kısa yol boyunca artar, dolayısıyla "en yakın düğümü kesinleştir, bir daha dokunma" açgözlü stratejisi doğrudur. Düğümleri bir öncelik kuyruğundan artan mesafe sırasında çekip kenarlarını gevşeterek SSSP'yi neredeyse doğrusal $O(E + V \log V)$'de çözeriz. Bu, BFS'in ağırlıklı dünyaya taşınmış hâlidir.
:::
