Bir lojistik ağında merkez depo olan numaralı düğümden, teslimat noktası olan numaralı düğüme en kısa mesafe üzerinden sevkiyat yapılacaktır. Düğümler arasındaki bağlantılar ve bu bağlantıların mesafeleri (birim cinsinden) aşağıda verilmiştir:
| Başlangıç Düğümü | Bitiş Düğümü | Mesafe (Birim) |
|---|---|---|
| 1 | 2 | 4 |
| 1 | 3 | 3 |
| 2 | 3 | 2 |
| 2 | 4 | 5 |
| 3 | 4 | 3 |
| 3 | 5 | 6 |
| 4 | 5 | 1 |
| 4 | 6 | 5 |
| 5 | 6 | 2 |
Buna göre, numaralı düğümden numaralı düğüme giden en kısa yolun toplam mesafesi kaç birimdir?
- A8
- 9Answer
- C11
- D12
- E14
Answer
En kısa yolun toplam mesafesi 9 birimdir.
Yapılan adım adım analizde (Dijkstra yaklaşımı), 1-3 (), 3-4 (), 4-5 () ve 5-6 () yayları takip edildiğinde toplam mesafenin birim olduğu görülür. Diğer tüm kombinasyonlar (örneğin düğüm 2 üzerinden gitmek veya 4'ten 6'ya doğrudan atlamak) daha yüksek toplam maliyet/mesafe üretmektedir.
Step-by-Step Solution
Key Concept
En kısa yol problemlerinde (Dijkstra algoritması vb.) her bir düğüm için kalıcı etiketler oluşturulurken, o düğüme gelen tüm alternatif yollar kıyaslanmalı ve en küçük değer seçilmelidir.
Hints
1
Şebeke üzerinde her düğüme ulaşmak için mümkün olan en küçük toplam değerleri not ederek ilerleyin.
2
Düğüm 4'e ulaştığınızda (toplam 6 birim), Düğüm 6'ya gitmek için 4-6 yayını mı yoksa 4-5-6 güzergahını mı kullanmanın daha kısa olacağını karşılaştırın.
3
En kısa güzergah 1-3-4-5-6 şeklindedir; bu yolun üzerindeki tüm rakamları toplayın.
Practice More
Benzer bir şebekede 'Maksimum Akış' miktarını hesaplamayı deneyerek kapasite kısıtlarını pekiştirebilirsiniz.
Alternative Method
Şebekeyi küçük bir ağ olduğu için deneme-yanılma (inspection) yöntemiyle tüm yolları listeleyerek de çözebilirsiniz: 1-2-4-6 (14), 1-2-4-5-6 (12), 1-3-4-6 (11), 1-3-5-6 (11), 1-3-4-5-6 (9).
Estimated Time:1m 30s