{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "k00",
   "metadata": {},
   "source": [
    "# Drzewa i grafy\n",
    "\n",
    "*Wersja notatnika: 2026-10-16 · przygotowanie: dr inż. Szczepan Górtowski*\n",
    "\n",
    "Lista z dowiązaniami (zajęcia 6) to węzły połączone w łańcuch. Gdy węzeł ma **dwa** wskaźniki — powstaje drzewo.\n",
    "Gdy połączenia mogą biec w dowolną stronę — graf. Dziś zbudujesz drzewo binarne poszukiwań, przejdziesz drzewo na\n",
    "cztery sposoby i znajdziesz najkrótszą drogę algorytmem Dijkstry na kopcu z zajęć 4.\n",
    "\n",
    "### Jak korzystać\n",
    "1. Uruchamiaj komórki po kolei: `Ctrl + Enter` albo `Shift + Enter`.\n",
    "2. Przy ramkach **Przewidź, zanim uruchomisz** najpierw zgadnij, potem uruchom, na końcu rozwiń odpowiedź.\n",
    "3. W zadaniach zamień `pass` i `TODO` na swój kod i uruchom komórkę **Sprawdź**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k01",
   "metadata": {},
   "source": [
    "## Spis treści\n",
    "1. Drzewo: pojęcia\n",
    "2. Drzewo binarne poszukiwań (BST)\n",
    "3. Pułapka: BST z posortowanych danych to lista\n",
    "4. Przechodzenie drzewa: preorder, inorder, postorder, wszerz\n",
    "5. Graf: pojęcia, mosty Królewca i reprezentacja\n",
    "6. BFS i DFS: kolejka kontra stos\n",
    "7. Najkrótsza droga: algorytm Dijkstry\n",
    "8. Zadania 10.0–10.3 i zadanie 10.4 dla chętnych"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k02",
   "metadata": {},
   "source": [
    "## 1) Drzewo: pojęcia\n",
    "\n",
    "- **korzeń** — węzeł na samej górze, bez rodzica,\n",
    "- **rodzic** i **dziecko** — węzeł i węzły, na które wskazuje,\n",
    "- **liść** — węzeł bez dzieci,\n",
    "- **wysokość** — liczba poziomów od korzenia do najgłębszego liścia.\n",
    "\n",
    "Drzewo **binarne**: każdy węzeł ma najwyżej dwoje dzieci — lewe i prawe. Kopiec z zajęć 4 był takim drzewem zapisanym\n",
    "w liście. Dziś każdy węzeł to obiekt z dwoma wskaźnikami, jak węzeł listy z zajęć 6."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k03",
   "metadata": {},
   "source": [
    "## 2) Drzewo binarne poszukiwań (BST)\n",
    "\n",
    "Reguła BST: w **lewym** poddrzewie są wartości mniejsze od węzła, w **prawym** — większe. Szukając wartości, w każdym\n",
    "węźle wybierasz jedną stronę, jak w wyszukiwaniu binarnym z zajęć 8. Dla wyważonego drzewa to O(log n)."
   ]
  },
  {
   "cell_type": "code",
   "id": "k04",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class Wezel:\n",
    "    def __init__(self, wartosc):\n",
    "        self.wartosc = wartosc\n",
    "        self.lewy = None\n",
    "        self.prawy = None\n",
    "\n",
    "\n",
    "def wstaw(korzen, wartosc):\n",
    "    \"\"\"Wstawia wartość do BST i zwraca korzeń.\"\"\"\n",
    "    if korzen is None:\n",
    "        return Wezel(wartosc)\n",
    "    if wartosc < korzen.wartosc:\n",
    "        korzen.lewy = wstaw(korzen.lewy, wartosc)\n",
    "    else:\n",
    "        korzen.prawy = wstaw(korzen.prawy, wartosc)\n",
    "    return korzen\n",
    "\n",
    "\n",
    "def zawiera(korzen, wartosc):\n",
    "    kroki = 0\n",
    "    while korzen is not None:\n",
    "        kroki += 1\n",
    "        if wartosc == korzen.wartosc:\n",
    "            return True, kroki\n",
    "        korzen = korzen.lewy if wartosc < korzen.wartosc else korzen.prawy\n",
    "    return False, kroki\n",
    "\n",
    "\n",
    "drzewo = None\n",
    "for k in [50, 30, 70, 20, 40, 60, 80, 35]:\n",
    "    drzewo = wstaw(drzewo, k)\n",
    "print(\"korzeń:\", drzewo.wartosc, \"| lewe dziecko:\", drzewo.lewy.wartosc,\n",
    "      \"| prawe dziecko:\", drzewo.prawy.wartosc)\n",
    "print(\"szukam 35:\", zawiera(drzewo, 35), \"| szukam 65:\", zawiera(drzewo, 65))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k05",
   "metadata": {},
   "source": [
    "## 3) Pułapka: BST z posortowanych danych to lista\n",
    "\n",
    "Kształt BST zależy od **kolejności** wstawiania. Losowa kolejność daje drzewo niskie. Posortowana — każdy nowy\n",
    "element idzie w prawo i drzewo staje się listą z dowiązaniami: szukanie wraca do O(n). Drzewa **samowyważające**\n",
    "(np. AVL, czerwono-czarne) przebudowują się po wstawieniu, żeby tego uniknąć."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k06",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** jaką wysokość będzie miało drzewo z 500 liczb wstawionych losowo, a jaką — z tych samych liczb po kolei?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> Losowo: kilkanaście–dwadzieścia kilka poziomów (log₂ 500 ≈ 9, losowe drzewo jest ok. 2–3 razy wyższe). Po kolei: 500 — każdy węzeł ma tylko prawe dziecko.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k07",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def wysokosc_iter(korzen):\n",
    "    \"\"\"Wysokość bez rekurencji: przejście poziom po poziomie.\"\"\"\n",
    "    poziom, wys = [korzen] if korzen else [], 0\n",
    "    while poziom:\n",
    "        wys += 1\n",
    "        poziom = [d for w in poziom for d in (w.lewy, w.prawy) if d]\n",
    "    return wys\n",
    "\n",
    "liczby = list(range(500))\n",
    "random.seed(2026)\n",
    "losowe = random.sample(liczby, len(liczby))\n",
    "\n",
    "drzewo_losowe = None\n",
    "for x in losowe:\n",
    "    drzewo_losowe = wstaw(drzewo_losowe, x)\n",
    "drzewo_po_kolei = None\n",
    "for x in liczby:\n",
    "    drzewo_po_kolei = wstaw(drzewo_po_kolei, x)\n",
    "\n",
    "print(\"wysokość, losowo: \", wysokosc_iter(drzewo_losowe))\n",
    "print(\"wysokość, po kolei:\", wysokosc_iter(drzewo_po_kolei))\n",
    "print(\"szukam 499, losowo: \", zawiera(drzewo_losowe, 499))\n",
    "print(\"szukam 499, po kolei:\", zawiera(drzewo_po_kolei, 499))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k08",
   "metadata": {},
   "source": [
    "## 4) Przechodzenie drzewa: preorder, inorder, postorder, wszerz\n",
    "\n",
    "Trzy sposoby rekurencyjne różnią się tylko tym, **kiedy** odwiedzasz węzeł względem dzieci:\n",
    "- **preorder** — węzeł, lewe, prawe (kopiowanie drzewa),\n",
    "- **inorder** — lewe, węzeł, prawe — **dla BST daje wartości posortowane**,\n",
    "- **postorder** — lewe, prawe, węzeł (usuwanie drzewa, liczenie wyrażeń).\n",
    "\n",
    "Czwarty — **wszerz** (poziomami) — używa kolejki `deque` (zajęcia 4)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k09",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** co wypisze `inorder` dla drzewa z sekcji 2?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> Wartości posortowane: `[20, 30, 35, 40, 50, 60, 70, 80]`. Sortowanie przez BST: wstaw wszystko, odczytaj inorder.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k10",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def preorder(w):\n",
    "    return [w.wartosc] + preorder(w.lewy) + preorder(w.prawy) if w else []\n",
    "\n",
    "def inorder_(w):\n",
    "    return inorder_(w.lewy) + [w.wartosc] + inorder_(w.prawy) if w else []\n",
    "\n",
    "def postorder(w):\n",
    "    return postorder(w.lewy) + postorder(w.prawy) + [w.wartosc] if w else []\n",
    "\n",
    "def wszerz(korzen):\n",
    "    wynik, kolejka = [], deque([korzen])\n",
    "    while kolejka:\n",
    "        w = kolejka.popleft()\n",
    "        if w:\n",
    "            wynik.append(w.wartosc)\n",
    "            kolejka.extend([w.lewy, w.prawy])\n",
    "    return wynik\n",
    "\n",
    "for f in (preorder, inorder_, postorder, wszerz):\n",
    "    print(f\"{f.__name__:<10}\", f(drzewo))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k11",
   "metadata": {},
   "source": [
    "## 5) Graf: pojęcia, mosty Królewca i reprezentacja\n",
    "\n",
    "**Graf** to wierzchołki i krawędzie między nimi: sieć przystanków, znajomości, linków. Krawędź może mieć **kierunek**\n",
    "(graf skierowany) i **wagę** (np. czas przejazdu). **Stopień** wierzchołka to liczba krawędzi, które z niego wychodzą.\n",
    "\n",
    "Teoria grafów zaczęła się od zagadki: czy da się przejść przez siedem mostów Królewca, każdym dokładnie raz? W 1736 r.\n",
    "Leonhard Euler udowodnił, że **nie**. Spacer po każdej krawędzi dokładnie raz istnieje tylko wtedy, gdy wierzchołków\n",
    "o **nieparzystym** stopniu jest 0 albo 2 — a w Królewcu były cztery.\n",
    "\n",
    "Graf zapiszesz na dwa sposoby:\n",
    "- **słownik list sąsiadów** — mało pamięci, gdy krawędzi jest niewiele (tak zwykle w Pythonie),\n",
    "- **macierz sąsiedztwa** — tabela n × n z 1 tam, gdzie jest krawędź; szybkie pytanie „czy A łączy się z B?”."
   ]
  },
  {
   "cell_type": "code",
   "id": "k12",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Królewiec: A — wyspa Kneiphof, B i C — brzegi rzeki, D — druga wyspa.\n",
    "# Siedem mostów; każdy most to jedna pozycja na liście sąsiadów.\n",
    "krolewiec = {\n",
    "    \"A\": [\"B\", \"B\", \"C\", \"C\", \"D\"],\n",
    "    \"B\": [\"A\", \"A\", \"D\"],\n",
    "    \"C\": [\"A\", \"A\", \"D\"],\n",
    "    \"D\": [\"A\", \"B\", \"C\"],\n",
    "}\n",
    "stopnie_k = {w: len(s) for w, s in krolewiec.items()}\n",
    "nieparzyste = [w for w, st in stopnie_k.items() if st % 2 == 1]\n",
    "print(\"stopnie:\", stopnie_k)\n",
    "print(\"wierzchołków o nieparzystym stopniu:\", len(nieparzyste))\n",
    "print(\"spacer po każdym moście raz możliwy?\", len(nieparzyste) in (0, 2))\n",
    "\n",
    "wierzcholki = list(krolewiec)\n",
    "macierz = [[krolewiec[a].count(b) for b in wierzcholki] for a in wierzcholki]\n",
    "for w, wiersz in zip(wierzcholki, macierz):\n",
    "    print(w, wiersz)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k13",
   "metadata": {},
   "source": [
    "## 6) BFS i DFS: kolejka kontra stos\n",
    "\n",
    "- **BFS** (wszerz) bierze wierzchołki z **kolejki**: najpierw wszyscy sąsiedzi, potem sąsiedzi sąsiadów. Daje najkrótszą\n",
    "  drogę w liczbie krawędzi (zajęcia 4).\n",
    "- **DFS** (w głąb) bierze z **stosu** (albo rekurencji): idzie jak najdalej jedną drogą, potem się cofa. Przydaje się\n",
    "  do szukania wyjścia z labiryntu i sprawdzania, czy graf jest spójny.\n",
    "\n",
    "Ta sama zamiana `popleft()` na `pop()` zmienia BFS w DFS — to odpowiedź na pytanie z końca notatnika 04."
   ]
  },
  {
   "cell_type": "code",
   "id": "k14",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "graf = {\n",
    "    \"A\": [\"B\", \"C\"],\n",
    "    \"B\": [\"A\", \"D\", \"E\"],\n",
    "    \"C\": [\"A\", \"F\"],\n",
    "    \"D\": [\"B\"],\n",
    "    \"E\": [\"B\", \"F\"],\n",
    "    \"F\": [\"C\", \"E\"],\n",
    "}\n",
    "\n",
    "def bfs(graf, start):\n",
    "    odwiedzone, kolejka = [start], deque([start])\n",
    "    while kolejka:\n",
    "        w = kolejka.popleft()\n",
    "        for s in graf[w]:\n",
    "            if s not in odwiedzone:\n",
    "                odwiedzone.append(s)\n",
    "                kolejka.append(s)\n",
    "    return odwiedzone\n",
    "\n",
    "def dfs_rek(graf, w, odwiedzone=None):\n",
    "    if odwiedzone is None:\n",
    "        odwiedzone = []\n",
    "    odwiedzone.append(w)\n",
    "    for s in graf[w]:\n",
    "        if s not in odwiedzone:\n",
    "            dfs_rek(graf, s, odwiedzone)\n",
    "    return odwiedzone\n",
    "\n",
    "print(\"BFS z A:\", bfs(graf, \"A\"))\n",
    "print(\"DFS z A:\", dfs_rek(graf, \"A\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k15",
   "metadata": {},
   "source": [
    "## 7) Najkrótsza droga: algorytm Dijkstry\n",
    "\n",
    "Gdy krawędzie mają **wagi** (czas, odległość, koszt), BFS nie wystarcza. Edsger Dijkstra wymyślił w 1956 r. — jak\n",
    "wspominał, w ok. 20 minut na tarasie kawiarni w Amsterdamie — algorytm, który zawsze rozwija wierzchołek o najmniejszej\n",
    "znanej odległości. Opublikował go w 1959 r. Najmniejszą odległość podaje kopiec `heapq` z zajęć 4.\n",
    "\n",
    "Mapa poniżej jest fikcyjna: wagi to minuty przejazdu między punktami A–F."
   ]
  },
  {
   "cell_type": "code",
   "id": "k16",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "mapa = {\n",
    "    \"A\": {\"B\": 4, \"C\": 2},\n",
    "    \"B\": {\"A\": 4, \"C\": 1, \"D\": 5},\n",
    "    \"C\": {\"A\": 2, \"B\": 1, \"D\": 8, \"E\": 10},\n",
    "    \"D\": {\"B\": 5, \"C\": 8, \"E\": 2, \"F\": 6},\n",
    "    \"E\": {\"C\": 10, \"D\": 2, \"F\": 3},\n",
    "    \"F\": {\"D\": 6, \"E\": 3},\n",
    "}\n",
    "\n",
    "import heapq\n",
    "\n",
    "def dijkstra_slad(graf, start):\n",
    "    odleglosc = {w: float(\"inf\") for w in graf}\n",
    "    odleglosc[start] = 0\n",
    "    kopiec = [(0, start)]\n",
    "    kolejnosc = []\n",
    "    while kopiec:\n",
    "        d, w = heapq.heappop(kopiec)\n",
    "        if d > odleglosc[w]:\n",
    "            continue                      # nieaktualny wpis w kopcu\n",
    "        kolejnosc.append((w, d))\n",
    "        for sasiad, waga in graf[w].items():\n",
    "            if d + waga < odleglosc[sasiad]:\n",
    "                odleglosc[sasiad] = d + waga\n",
    "                heapq.heappush(kopiec, (d + waga, sasiad))\n",
    "    return odleglosc, kolejnosc\n",
    "\n",
    "odl, kolejnosc = dijkstra_slad(mapa, \"A\")\n",
    "print(\"kolejność zamykania:\", kolejnosc)\n",
    "print(\"odległości z A:     \", odl)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k17",
   "metadata": {},
   "source": [
    "## 8) Zadanie 10.0 — wysokość drzewa\n",
    "\n",
    "Napisz rekurencyjną `wysokosc(wezel)`: puste drzewo (`None`) ma wysokość 0, a każdy węzeł to 1 + wysokość wyższego\n",
    "z poddrzew."
   ]
  },
  {
   "cell_type": "code",
   "id": "k18",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def wysokosc(wezel) -> int:\n",
    "    \"\"\"Liczba poziomów drzewa; puste drzewo ma wysokość 0.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k19",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert wysokosc(None) == 0\n",
    "    assert wysokosc(Wezel(1)) == 1\n",
    "    assert wysokosc(drzewo) == 4\n",
    "    assert wysokosc(drzewo_losowe) == wysokosc_iter(drzewo_losowe)\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 10.0 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k20",
   "metadata": {},
   "source": [
    "## Zadanie 10.1 — inorder\n",
    "\n",
    "Napisz rekurencyjną `inorder(wezel)`, która zwraca listę wartości: lewe poddrzewo, węzeł, prawe poddrzewo.\n",
    "Dla BST wynik ma być posortowany."
   ]
  },
  {
   "cell_type": "code",
   "id": "k21",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def inorder(wezel) -> list:\n",
    "    \"\"\"Wartości w kolejności: lewe poddrzewo, węzeł, prawe poddrzewo.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k22",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert inorder(None) == []\n",
    "    assert inorder(drzewo) == [20, 30, 35, 40, 50, 60, 70, 80]\n",
    "    assert inorder(drzewo_losowe) == list(range(500))\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 10.1 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k23",
   "metadata": {},
   "source": [
    "## Zadanie 10.2 — stopnie wierzchołków\n",
    "\n",
    "Napisz `stopnie(graf)`: słownik `wierzchołek → liczba sąsiadów` dla grafu zapisanego słownikiem list. Sprawdź nim\n",
    "Królewiec z sekcji 5."
   ]
  },
  {
   "cell_type": "code",
   "id": "k24",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def stopnie(graf: dict) -> dict:\n",
    "    \"\"\"Stopień każdego wierzchołka grafu nieskierowanego.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k25",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert stopnie(krolewiec) == {'A': 5, 'B': 3, 'C': 3, 'D': 3}\n",
    "    assert stopnie(graf)['B'] == 3 and stopnie({}) == {}\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 10.2 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k26",
   "metadata": {},
   "source": [
    "## Zadanie 10.3 — DFS bez rekurencji\n",
    "\n",
    "Napisz `dfs(graf, start)` ze **stosem** (lista z `append` i `pop`). Kolejność ma być taka sama jak w `dfs_rek`\n",
    "z sekcji 6, czyli sąsiedzi w kolejności z listy. Wskazówka: na stos kładź sąsiadów **od końca** (`reversed`)."
   ]
  },
  {
   "cell_type": "code",
   "id": "k27",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def dfs(graf: dict, start) -> list:\n",
    "    \"\"\"Kolejność odwiedzin w głąb, sąsiedzi w kolejności z listy.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k28",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert dfs(graf, 'A') == dfs_rek(graf, 'A')\n",
    "    assert dfs(graf, 'F') == dfs_rek(graf, 'F')\n",
    "    assert dfs({'X': []}, 'X') == ['X']\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 10.3 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k29",
   "metadata": {},
   "source": [
    "## Zadanie 10.4 dla chętnych — Dijkstra ze ścieżką\n",
    "\n",
    "Napisz `dijkstra(graf, start, cel)`, która zwraca krotkę `(długość, ścieżka)`, np. `(9, ['A', 'C', 'B', 'D', 'E'])`.\n",
    "Zapamiętuj **poprzednika** każdego wierzchołka (jak w BFS z zajęć 4) i odtwórz ścieżkę od celu do startu."
   ]
  },
  {
   "cell_type": "code",
   "id": "k30",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "\n",
    "def dijkstra(graf: dict, start, cel) -> tuple:\n",
    "    \"\"\"(długość, ścieżka) najkrótszej drogi w grafie z wagami.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k31",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    dl, sc = dijkstra(mapa, 'A', 'F')\n",
    "    assert dl == odl['F'] and sc[0] == 'A' and sc[-1] == 'F'\n",
    "    assert sum(mapa[a][b] for a, b in zip(sc, sc[1:])) == dl\n",
    "    assert dijkstra(mapa, 'A', 'A') == (0, ['A'])\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 10.4 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k32",
   "metadata": {},
   "source": [
    "## Zapamiętaj\n",
    "\n",
    "- **BST**: lewo mniejsze, prawo większe; szukanie O(wysokość). Z posortowanych danych drzewo staje się listą.\n",
    "- **Inorder** BST daje wartości posortowane. Przechodzenie wszerz używa kolejki.\n",
    "- **Graf** zapisujesz słownikiem list sąsiadów (albo macierzą). BFS — kolejka, DFS — stos albo rekurencja.\n",
    "- **Dijkstra**: zawsze rozwijaj najbliższy wierzchołek — kopiec daje go w O(log n).\n",
    "\n",
    "## Zadania dodatkowe\n",
    "\n",
    "1. Wstaw do BST liczby 1–7 w takiej kolejności, żeby wysokość była najmniejsza. Ile wynosi?\n",
    "2. Dodaj do Królewca jeden most tak, żeby spacer po każdym moście raz stał się możliwy.\n",
    "3. Dlaczego Dijkstra nie działa poprawnie, gdy wagi mogą być ujemne?"
   ]
  }
 ],
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  }
 }
}