Ağ Gecikme Süresi ve Yolun Yeniden Oluşturulması
Ağ gecikme süresi problemini Dijkstra ile çözün, öncül eşlemesiyle gerçek en kısa yolu yeniden oluşturun ve büyük graflar için çift yönlü BFS’yi tartışın.
Ağ Gecikme Süresi ve Yolun Yeniden Oluşturulması, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Ağ Gecikme Süresi Problemi
Ağ Gecikme Süresi (LeetCode 743): sinyalin seyahat sürelerini temsil eden yönlü ve ağırlıklı kenarlara sahip, n düğümlü bir ağ verildiğinde, k düğümünden gönderilen sinyalin tüm düğümlere ulaşması için gereken minimum süreyi bulun. Bir düğüme ulaşılamıyorsa -1 döndürün. Bu, Dijkstra'nın doğrudan bir uygulamasıdır: yanıt, tüm düğümler arasında k düğümünden olan en uzun en kısa yol mesafesidir.
Çözüm: Dijkstra + Mesafelerin Maksimumu
Kaynak k düğümünden Dijkstra'yı çalıştırarak tüm v düğümleri için dist[v] değerini bulun. Yanıt max(dist.values()) değeridir. Herhangi bir dist[v] hâlâ inf ise o düğüme ulaşılamıyordur — -1 döndürün. Sinyal tüm yollarda eşzamanlı ilerler; bu nedenle darboğaz, ulaşılması en uzun süren düğümdür.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2prev Dizisiyle Yolun Yeniden Oluşturulması
Mesafeleri hesaplarken gerçek en kısa yolu da yeniden oluşturmak için her düğümün en iyi önceki düğümünü kaydeden bir prev sözlüğü tutun. dist[v] değerini her güncellediğinizde prev[v] = u atamasını yapın. Dijkstra tamamlandıktan sonra hedeften başlayarak prev işaretçileri üzerinden kaynak düğüme ulaşana kadar geriye doğru ilerleyin, ardından ileri yönlü yolu elde etmek için yolu ters çevirin.
import heapq
from collections import defaultdict
def shortest_path_with_reconstruction(times, n, src, dst):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
prev = {i: None for i in range(1, n+1)}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct path from src to dst
path, node = [], dst
while node is not None:
path.append(node)
node = prev[node]
return dist[dst], path[::-1]Büyük Ağırlıksız Graflar için Çift Yönlü BFS
Yalnızca tek bir kaynak-hedef çifti gereken büyük ağırlıksız graflarda, Çift Yönlü BFS standart BFS'den önemli ölçüde daha hızlı olabilir. BFS'yi aynı anda hem kaynaktan hem de hedeften çalıştırır ve iki ön sınır buluştuğunda durur. Uygulamadaki hızlanma önemlidir; çünkü her ön sınırın grafın derinliğinin yalnızca yarısını keşfetmesi yeterlidir — keşfedilen düğüm sayısı, b'nin dallanma katsayısı olduğu durumda O(b^d)'den O(2 × b^(d/2))'ye düşer.
from collections import deque
def bidir_bfs(graph, src, dst):
if src == dst: return 0
front_q = deque([src]); front_visited = {src: 0}
back_q = deque([dst]); back_visited = {dst: 0}
def expand(queue, visited, other_visited):
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited[nxt] = visited[node] + 1
queue.append(nxt)
if nxt in other_visited:
return visited[nxt] + other_visited[nxt]
return -1
while front_q or back_q:
res = expand(front_q, front_visited, back_visited)
if res != -1: return res
res = expand(back_q, back_visited, front_visited)
if res != -1: return res
return -1Hangi Algoritmayı Ne Zaman Seçmeli?
Karar rehberi: Ağırlıksız graf, tek çift → BFS veya Çift Yönlü BFS. Ağırlıklı, negatif olmayan, tek kaynaklı → Dijkstra. Ağırlıklı, negatif olabilen, tek kaynaklı → Bellman-Ford. Tüm çiftler → Floyd-Warshall (küçük V) veya V × Dijkstra (seyrek). Kısıtlı atlama sayısı → sınırlı geçişli değiştirilmiş Bellman-Ford. Bu kararın gerekçesini mülakatlarda sesli olarak açıklamak algoritmik olgunluğunuzu gösterir.
En Az Ulaşılabilir Komşuya Sahip Şehri Bulma (LeetCode 1334)
Ağırlıklı yollara ve bir distanceThreshold değerine sahip şehirler verildiğinde, bu eşik içinde en az sayıda başka şehirden ulaşılabilen şehri bulun (eşitlik durumunda daha büyük şehir indeksini tercih edin). Çözüm: Floyd-Warshall ile tüm çiftler arasındaki en kısa yolları hesaplayın, ardından her şehir için eşik içinde kaç başka şehre ulaşılabildiğini sayın. En az sayıda ulaşılabilir şehre sahip şehri döndürün (eşitlikte: en büyük indeks).
def findTheCity(n, edges, distanceThreshold):
INF = float('inf')
dist = [[INF]*n for _ in range(n)]
for i in range(n): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = dist[v][u] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
best_city, best_count = -1, n
for city in range(n):
count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
if count <= best_count:
best_count = count
best_city = city
return best_city
print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4)) # 3Ağırlıklı DAG'de Yol
Yönlü Döngüsüz Graf (DAG) için en kısa (veya en uzun) yollar, O(V+E) zamanda topolojik sıralama + gevşetme ile bulunabilir; bu, Dijkstra'dan daha hızlıdır. Düğümleri topolojik sırada işleyin; u düğümünü işlerken giden tüm kenarları gevşetin. En uzun yollar için (proje planlama / kritik yol açısından kullanışlıdır) ağırlıkların negatifini alın veya min ifadesini max ile değiştirin.
from collections import deque
def dag_shortest_path(V, edges, source):
graph = [[] for _ in range(V)]
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
# Topological sort (Kahn's)
queue = deque(i for i in range(V) if in_degree[i] == 0)
topo = []
while queue:
node = queue.popleft(); topo.append(node)
for nxt, _ in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
# Relax in topological order
dist = [float('inf')] * V
dist[source] = 0
for u in topo:
if dist[u] != float('inf'):
for v, w in graph[u]:
dist[v] = min(dist[v], dist[u] + w)
return distEngeller İçeren Matriste En Kısa Yol
Yaygın bir mülakat varyantı: hücrelerin engelli olabildiği bir 2B ızgarada sol üstten sağ alta en kısa yolu bulun. Bu, her adımın maliyetinin 1 olduğu bir ağırlıksız BFS problemidir. Dört yönde hareket eden BFS kullanın ve hücreleri kuyruktan çıkarıldıklarında değil, kuyruğa eklendiklerinde ziyaret edilmiş olarak işaretleyerek tekrar ziyaret edilmelerini önleyin. Engellerden bir maliyet karşılığında geçilebiliyorsa, 2B ızgarayı ağırlıklı bir graf olarak ele alıp üzerinde Dijkstra kullanın.
from collections import deque
def shortest_path_binary_matrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
visited = {(0, 0)}
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while queue:
r, c, d = queue.popleft()
if r == n-1 and c == n-1:
return d
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
visited.add((nr,nc))
queue.append((nr, nc, d+1))
return -1
print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]])) # 4Çok Kaynaklı BFS
Birden çok başlangıç noktası olduğunda (örneğin bir ızgarada birden çok 'kapı' veya bir haritada birden çok başlangıç noktası), çok kaynaklı BFS çalıştırın: tüm kaynakları mesafe 0 ile aynı anda kuyruğa ekleyin. Bu, tek bir BFS geçişinde her hücre için en yakın kaynaktan olan en kısa mesafeyi hesaplar. Bu teknik, her kaynaktan ayrı ayrı BFS çalıştırma gereğini ortadan kaldırır ve toplamda O(V+E) zamanda çalışır.
Algoritma Seçiminin Özeti
Kısa bir karar ağacı: tek kaynak, negatif olmayan ağırlıklar → Dijkstra O((V+E) log V). Tek kaynak, negatif ağırlıklar → Bellman-Ford O(VE). Tüm çiftler, küçük V → Floyd-Warshall O(V³). DAG, her türlü ağırlık → Topolojik Sıralama + Gevşetme O(V+E). Ağırlıksız → BFS O(V+E). Izgara yolları → BFS (ağırlıksız) veya yığın kullanan Dijkstra (ağırlıklı). Bu tabloyu ezberleyin — herhangi bir en kısa yol mülakatındaki takip sorularını yanıtlamanıza yardımcı olur.
Mülakat Sorularında Yol Bulma
Birçok mülakat problemi yalnızca maliyeti değil, gerçek yolu bulmanızı ister. Her zaman netleştirin: yola mı, yoksa yalnızca mesafeye mi ihtiyacınız var? Yol gerekiyorsa başlangıçta bir prev sözlüğü oluşturun. Yaygın hatalar şunlardır: bitiş koşulu olarak prev[source] = None atamasını yapmayı unutmak ve yeniden oluşturma sırasını karıştırmak (hedeften kaynağa doğru geriye ilerleyin, ardından ters çevirin). Daha büyük problemlere uygulamadan önce 3-4 düğümlü örneklerde yolları yeniden oluşturma alıştırması yapın.
Kısa Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: Ağ Gecikme Süresi, Dijkstra'dan sonra max(dist.values()) ile yanıtlanır, yolun yeniden oluşturulmasında dist[v] her iyileştiğinde güncellenen bir prev dizisi kullanılır ve çift yönlü BFS, tek çiftli ağırlıksız en kısa yollar için arama alanını yarıya indirebilir. Sırada topolojik sıralama için Kahn Algoritması ile graf sıralamasına geçiyoruz.
Sıkça Sorulan Sorular
“Ağ Gecikme Süresi ve Yolun Yeniden Oluşturulması” dersi ücretsiz mi?
Evet — “Ağ Gecikme Süresi ve Yolun Yeniden Oluşturulması” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Ağ Gecikme Süresi ve Yolun Yeniden Oluşturulması” dersinde ne öğreneceğim?
Ağ gecikme süresi problemini Dijkstra ile çözün, öncül eşlemesiyle gerçek en kısa yolu yeniden oluşturun ve büyük graflar için çift yönlü BFS’yi tartışın. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“Ağ Gecikme Süresi ve Yolun Yeniden Oluşturulması” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Öncelik Kuyruğuyla Dijkstra Algoritması
- Bellman-Ford ve Negatif Çevrimler
- Floyd-Warshall: Tüm Çiftler İçin En Kısa Yollar
- Ağ Gecikme Süresi ve Yolun Yeniden Oluşturulması