Meydan okuma 3
- Algoritmalar kursu
- İleri seviye
- Ders 55/56
- 4 dk
Dijkstra ile en kısa mesafeleri yazdırırsın.
Meydan okuma 3: Dijkstra
Bu meydan okumada Dijkstra algoritmasını bir grafta uygulayacaksın. Tek kaynak en kısa yolları bulup belirli bir hedefe olan mesafeyi döndüreceksin.
Graf: [[(1, 2), (2, 4)], [(2, 1), (3, 5)], [(3, 1)], []]. 0'dan 3'e en kısa mesafe 4'tür.
Uygulama shortest_distance fonksiyonu
shortest_distance(graph, src, dst) yaz. Dijkstra çalıştır, dist[dst]'yi döndür. print(shortest_distance([[(1, 2), (2, 4)], [(2, 1), (3, 5)], [(3, 1)], []], 0, 3)) ile 4 yazdır.
Başlangıç kodu
def shortest_distance(graph, src, dst):
# Dijkstra ile src→dst mesafesini bulÖrnek çözüm
def shortest_distance(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_distance([[(1, 2), (2, 4)], [(2, 1), (3, 5)], [(3, 1)], []], 0, 3))Beklenen çıktı
4
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Meydan okuma 3: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
0→1 |
2 |
0→2 |
3 |
1→3 |
6 |
0→3 |
4 |
2 en küçük seçim
Soru
if not visited[i] and dist[i] ____ best:
Cevap
if not visited[i] and dist[i] < best:Açıklama: < doğru.
3 0'dan 3'e en kısa yol hangisidir?
- 0→3 (direkt)
- 0→1→3
- 0→1→2→3 Doğru cevap
- 0→2→3
Açıklama: 0→1→2→3 yolu 2+1+1=4 verir.