Ağ Akışları ve Tamsayı Programlama #07 | En kısa yol ve Dijkstra algoritması

Eğitmen: Dr. Süleyman Burak ÇELİK

Altı düğümlü yönlü bir ağda en kısa yolu Dijkstra algoritmasıyla buluyoruz. Her etikette geçici süreyi ve önceki düğümü tutuyor, bir düğüm kalıcılaştığında komşu etiketleri yeniden değerlendiriyoruz. Özgün örnekte A–C–B–D–E–F yolu 11 dakika sürüyor. Yolu geriye izlemeyi, doğru durma noktasını ve en küçük geçici etiketin neden güvenli olduğunu inceliyoruz. Sıfır ağırlık, negatif ağırlık ve erişilemeyen düğüm durumlarını ayırıyoruz. Bölümler: 00:00 En kısa yolu adım adım bul 01:20 Altı düğüm, on iki yönlü bağlantı 02:39 Etiket iki bilgi taşır 03:56 Seç, kalıcılaştır, gevşet 05:11 A kalıcı: ilk yolları kaydet 06:24 C kalıcı: ilk etiketler değişiyor 07:42 B kalıcı: D ve E yeniden iyileşiyor 08:56 D kalıcı: hedefe yeni bir yol 10:10 E kalıcı, ardından F kalıcı 11:28 Süreyi bulduk; yolu geri izle 12:51 En küçük geçici etiket neden güvenli? 14:11 Sık karıştırılan üç durum 15:32 Üç kısa kontrol 17:17 Etiket, önceki düğüm ve doğru durma Kaynak: Hamdy A. Taha, Operations Research: An Introduction, 10. baskı; §6.3; kitap s.251–265 (PDF s.252–266). Anlatım, örnek veriler ve görseller özgündür. AcEdumy — mühendislik derslerini adım adım öğren.