Özet - Dijkstra

Küçük graph'ta Dijkstra uygulayıp mesafeleri yazdıran mini görev yaparsın.

Özet - Dijkstra

Bu grupta tek kaynaktan tüm düğümlere en kısa yolu bulan Dijkstra algoritmasını öğrendin. Komşuluk listesi, mesafe dizisi ve gevşetme birleşince çözüm oluşur.

Şimdi tüm parçaları bir araya getiren bir sorgu fonksiyonu yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.

Uygulama shortest_path fonksiyonu

shortest_path(graph, src, dst) yaz. Dijkstra çalıştır, dist[dst]'yi döndür. print(shortest_path(init_graph(), 0, 3)) ile 4 yazdır.

Örnek çözümü göster

def shortest_path(graph, src, dst):
    # Dijkstra ile src→dst mesafesini bul
    n = len(graph)
    dist = [float('inf')] * n
    dist[src] = 0
    visited = [False] * n
    for _ in range(n):
        u = -1
        best = float('inf')
        for i in range(n):
            if not visited[i] and dist[i] < best:
                best = dist[i]
                u = i
        if u == -1:
            break
        visited[u] = True
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist[dst]
print(shortest_path(init_graph(), 0, 3))

Kendini test et

Dijkstra'nın çıktısı nedir?
- Ziyaret dizisi
- Tek bir yol
- Kenar listesi
- Mesafe dizisi
Cevabı göster

Mesafe dizisi — Çıktı kaynaktan tüm düğümlere mesafe dizisidir.
n ataması
```
n = len(____)
```
Cevabı göster
```
n = len(graph)
```
Özet - Dijkstra: kavramları eşleştir

init_graph

Graf
init_dist

Mesafe
dijkstra

Algoritma
dist

Çıktı

Sıradaki ders: Negatif ağırlık

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler