🛤️ 10.5: Dijkstra Algoritması

import heapq

def dijkstra(graph, start):
    """
    Dijkstra Algoritması - Priority Queue (Min-Heap) ile
    
    Args:
        graph: {node: [(neighbor, weight), ...], ...}
        start: Başlangıç düğümü
    
    Returns:
        distances: Her düğüme en kısa mesafe
        previous: Yol yeniden oluşturmak için önceki düğümler
    """
    # Başlangıç mesafeleri: başlangıç 0, diğerleri sonsuz
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    
    # Yolu yeniden oluşturmak için
    previous = {node: None for node in graph}
    
    # Priority queue: (mesafe, düğüm)
    pq = [(0, start)]
    visited = set()
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        # Bu düğümü zaten daha iyi bir yolla işledik mi?
        if current in visited:
            continue
            
        visited.add(current)
        print(f"İşlenen: {current} (mesafe: {current_dist})")
        
        # Komşuları kontrol et
        for neighbor, weight in graph[current]:
            if neighbor in visited:
                continue
                
            new_dist = current_dist + weight
            
            # Daha kısa bir yol bulduk mu?
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                previous[neighbor] = current
                heapq.heappush(pq, (new_dist, neighbor))
                print(f"  → {neighbor} güncellendi: {new_dist}")
    
    return distances, previous


# Graf örneği (ağırlıklı kenarlar)
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
    'D': [('B', 5), ('C', 8), ('E', 2), ('F', 6)],
    'E': [('C', 10), ('D', 2), ('F', 3)],
    'F': [('D', 6), ('E', 3)]
}

print("=== GRAF (ağırlıklı) ===")
for node, edges in graph.items():
    print(f"  {node}: {edges}")

print("\n=== DIJKSTRA - A'dan tüm düğümlere ===\n")
distances, previous = dijkstra(graph, 'A')

print("\n=== SONUÇLAR ===")
print("\nEn kısa mesafeler:")
for node, dist in sorted(distances.items()):
    print(f"  A → {node}: {dist}")

import heapq

def dijkstra_with_path(graph, start, end):
    """
    Dijkstra - Belirli bir hedefe en kısa yol
    
    Returns:
        distance: En kısa mesafe
        path: Yol listesi
    """
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    previous = {node: None for node in graph}
    
    pq = [(0, start)]
    visited = set()
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current == end:
            break  # Hedefe ulaştık!
            
        if current in visited:
            continue
            
        visited.add(current)
        
        for neighbor, weight in graph[current]:
            if neighbor not in visited:
                new_dist = current_dist + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    previous[neighbor] = current
                    heapq.heappush(pq, (new_dist, neighbor))
    
    # Yolu yeniden oluştur
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = previous[current]
    path.reverse()
    
    return distances[end], path


# Graf
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
    'D': [('B', 5), ('C', 8), ('E', 2), ('F', 6)],
    'E': [('C', 10), ('D', 2), ('F', 3)],
    'F': [('D', 6), ('E', 3)]
}

print("=== GRAF ===")
print("       4")
print("   A------B")
print("   |\\     |\\")
print("   | \\2   |1\\ 5")
print("   |  \\   |  \\")
print("   |   C--+---D")
print("   |  10\\ |8  |\\")
print("   |     \\|   |2\\ 6")
print("   |      E---+--F")
print("           3")

print("\n=== A'DAN HER DÜĞÜME EN KISA YOL ===\n")

for target in ['B', 'C', 'D', 'E', 'F']:
    dist, path = dijkstra_with_path(graph, 'A', target)
    path_str = ' → '.join(path)
    print(f"A → {target}: mesafe={dist}, yol: {path_str}")

import heapq

def dijkstra_basic(graph, start, end):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    visited = set()
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        if current in visited:
            continue
        visited.add(current)
        
        if current == end:
            break
            
        for neighbor, weight in graph[current]:
            if neighbor not in visited:
                new_dist = current_dist + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(pq, (new_dist, neighbor))
    
    return distances[end]


# Negatif ağırlıklı graf
graph_negative = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', -3)],  # ⚠️ Negatif kenar!
    'C': []
}

print("=== NEGATİF AĞIRLIKLI GRAF ===")
print("    1      -3")
print("A ----→ B ----→ C")
print("  \\           ↗")
print("   \\----→----/")
print("       4")
print()

# Dijkstra sonucu (yanlış olabilir!)
result = dijkstra_basic(graph_negative, 'A', 'C')
print(f"Dijkstra sonucu A→C: {result}")

# Doğru cevap
print(f"Doğru cevap: A→B→C = 1 + (-3) = -2")

if result != -2:
    print("\n⚠️ Dijkstra yanlış sonuç verdi!")
    print("Negatif ağırlıklar için Bellman-Ford kullanın.")