Eng qisqa yo'l - Dijkstra algoritmi

def dijkstra_sodda(graf, boshlanish):
    """Dijkstra algoritmi. O(V^2) - kichik graflar uchun."""
    masofalar = {vershina: float("inf") for vershina in graf}
    masofalar[boshlanish] = 0
    qayerdan = {boshlanish: None}
    tayyor = set()

    while len(tayyor) < len(graf):
        # Eng yaqin qayta ishlanmagan vershinani topamiz
        joriy = None
        eng_kichik = float("inf")
        for vershina in graf:
            if vershina not in tayyor and masofalar[vershina] < eng_kichik:
                eng_kichik = masofalar[vershina]
                joriy = vershina

        if joriy is None:            # qolganlari erishib bo'lmaydigan
            break

        tayyor.add(joriy)

        # Qo'shnilar uchun masofani yangilaymiz
        for qoshni, vazn in graf[joriy].items():
            yangi_masofa = masofalar[joriy] + vazn
            if yangi_masofa < masofalar[qoshni]:
                masofalar[qoshni] = yangi_masofa
                qayerdan[qoshni] = joriy

    return masofalar, qayerdan

shaharlar = {
    "Toshkent":  {"Samarqand": 280, "Namangan": 290, "Guliston": 110},
    "Guliston":  {"Toshkent": 110, "Jizzax": 90},
    "Jizzax":    {"Guliston": 90, "Samarqand": 160},
    "Samarqand": {"Toshkent": 280, "Jizzax": 160, "Buxoro": 270, "Qarshi": 140},
    "Qarshi":    {"Samarqand": 140, "Buxoro": 200, "Termiz": 260},
    "Buxoro":    {"Samarqand": 270, "Qarshi": 200, "Xiva": 440},
    "Xiva":      {"Buxoro": 440, "Nukus": 180},
    "Nukus":     {"Xiva": 180},
    "Namangan":  {"Toshkent": 290, "Andijon": 60},
    "Andijon":   {"Namangan": 60},
    "Termiz":    {"Qarshi": 260},
}


def yolni_tikla(qayerdan, manzil):
    """qayerdan jadvalidan to'liq yo'lni tiklaydi."""
    yol = []
    joriy = manzil
    while joriy is not None:
        yol.append(joriy)
        joriy = qayerdan.get(joriy)
    return yol[::-1]


masofalar, qayerdan = dijkstra_sodda(shaharlar, "Toshkent")

print(f"{'Shahar':<12}{'Masofa':>10}   Yo'l")
print("-" * 62)
for shahar, masofa in sorted(masofalar.items(), key=lambda j: j[1]):
    yol = " -> ".join(yolni_tikla(qayerdan, shahar))
    print(f"{shahar:<12}{masofa:>8} km   {yol}")

import heapq


def dijkstra(graf, boshlanish):
    """Uyum bilan Dijkstra. O((V + E) log V)."""
    masofalar = {vershina: float("inf") for vershina in graf}
    masofalar[boshlanish] = 0
    qayerdan = {boshlanish: None}
    tayyor = set()

    uyum = [(0, boshlanish)]

    while uyum:
        joriy_masofa, joriy = heapq.heappop(uyum)

        if joriy in tayyor:            # eskirgan yozuv - o'tkazib yuboramiz
            continue
        tayyor.add(joriy)

        for qoshni, vazn in graf[joriy].items():
            if qoshni in tayyor:
                continue

            yangi_masofa = joriy_masofa + vazn
            if yangi_masofa < masofalar[qoshni]:
                masofalar[qoshni] = yangi_masofa
                qayerdan[qoshni] = joriy
                heapq.heappush(uyum, (yangi_masofa, qoshni))

    return masofalar, qayerdan


def eng_qisqa_yol(graf, boshlanish, manzil):
    """Ikki nuqta orasidagi eng qisqa yo'l va uning uzunligi."""
    masofalar, qayerdan = dijkstra(graf, boshlanish)

    if masofalar[manzil] == float("inf"):
        return None, None

    yol = []
    joriy = manzil
    while joriy is not None:
        yol.append(joriy)
        joriy = qayerdan.get(joriy)

    return yol[::-1], masofalar[manzil]


yol, masofa = eng_qisqa_yol(shaharlar, "Andijon", "Nukus")

print("Andijondan Nukusgacha eng qisqa yo'l:\n")
jami = 0
for i in range(len(yol) - 1):
    bosqich = shaharlar[yol[i]][yol[i + 1]]
    jami += bosqich
    print(f"  {yol[i]:<12} -> {yol[i + 1]:<12}{bosqich:>6} km  (jami {jami} km)")

print(f"\nUmumiy masofa: {masofa} km")

import heapq


def dijkstra_izohli(graf, boshlanish, manzil=None):
    masofalar = {v: float("inf") for v in graf}
    masofalar[boshlanish] = 0
    tayyor = set()
    uyum = [(0, boshlanish)]
    qadam = 0

    while uyum:
        joriy_masofa, joriy = heapq.heappop(uyum)
        if joriy in tayyor:
            continue

        tayyor.add(joriy)
        qadam += 1
        print(f"{qadam}-qadam: {joriy} tanlandi (masofa {joriy_masofa} km)")

        for qoshni, vazn in graf[joriy].items():
            if qoshni in tayyor:
                continue
            yangi = joriy_masofa + vazn
            if yangi < masofalar[qoshni]:
                eski = masofalar[qoshni]
                eski_matn = "inf" if eski == float("inf") else str(eski)
                print(f"         {qoshni}: {eski_matn} -> {yangi} km yangilandi")
                masofalar[qoshni] = yangi
                heapq.heappush(uyum, (yangi, qoshni))

        if joriy == manzil:
            print(f"\nManzilga yetildi: {masofalar[manzil]} km")
            break

    return masofalar


dijkstra_izohli(shaharlar, "Toshkent", "Jizzax")

import heapq


def a_yulduz(graf, koordinatalar, boshlanish, manzil):
    """A* algoritmi - to'g'ri chiziqli masofani evristika sifatida ishlatadi."""

    def evristika(shahar):
        """Manzilgacha bo'lgan taxminiy (to'g'ri chiziqli) masofa."""
        x1, y1 = koordinatalar[shahar]
        x2, y2 = koordinatalar[manzil]
        return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


    masofalar = {v: float("inf") for v in graf}
    masofalar[boshlanish] = 0
    qayerdan = {boshlanish: None}
    tayyor = set()

    uyum = [(evristika(boshlanish), 0, boshlanish)]

    while uyum:
        _, joriy_masofa, joriy = heapq.heappop(uyum)

        if joriy in tayyor:
            continue
        tayyor.add(joriy)

        if joriy == manzil:
            break

        for qoshni, vazn in graf[joriy].items():
            yangi = joriy_masofa + vazn
            if yangi < masofalar[qoshni]:
                masofalar[qoshni] = yangi
                qayerdan[qoshni] = joriy
                heapq.heappush(uyum, (yangi + evristika(qoshni), yangi, qoshni))

    yol = []
    joriy = manzil
    while joriy is not None:
        yol.append(joriy)
        joriy = qayerdan.get(joriy)

    return yol[::-1], masofalar[manzil], len(tayyor)


# Taxminiy koordinatalar (km, shartli)
koordinatalar = {
    "Toshkent": (690, 410),  "Guliston": (680, 330),  "Jizzax": (670, 300),
    "Samarqand": (670, 250), "Qarshi": (650, 150),    "Buxoro": (640, 200),
    "Xiva": (600, 260),      "Nukus": (590, 420),     "Namangan": (710, 410),
    "Andijon": (720, 400),   "Termiz": (670, 40),
}

yol, masofa, korilgan = a_yulduz(shaharlar, koordinatalar, "Toshkent", "Termiz")
print(f"A*:       {' -> '.join(yol)}")
print(f"Masofa:   {masofa} km, ko'rilgan vershinalar: {korilgan}")

masofalar_d, qayerdan_d = dijkstra(shaharlar, "Toshkent")
print(f"\nDijkstra bir xil natija berdi: {masofalar_d['Termiz'] == masofa}")