Karar Modelleri Deneme Sınavı Sorusu #1345654

Yukarıda yer alan çizgenin en kısa yolunu veren rota aşağıdakilerden hangisidir?


1-4-5

1-2-3-5

1-2-4-5

1-2-4-3-5

1-2-3-4-5


Yanıt Açıklaması:

Başlagıç düğümü olan 1 nolu düğüme bağlı olan düğümlerden en yakın düğüm 7 birime sahip 4 nolu düğümdür. Bu nedenle bu düğüme [4,1] kalıcı etiketi atanır. Düğüm 4'e doğrudan bağlı olan düğümler 2, 3 ve 5 nolu düğümlerdir. 2 nolu düğüm için en kısa uzaklık değeri 9 olup 2 nolu düğüme [9,1] kalıcı etiketi verilir. 3 nolu düğüme 2 ve 4 nolu düğümlerden bağlantı olmaktadır. 2 nolu düğüm dikkate alınırsa uzaklık (15,2) ve 4 nolu düğüm dikkate alındığında ise uzaklık (10,4) olmaktadır. Bunlar arasında en kısa uzaklık değeri olan [10,4] kalıcı etiket değeri seçilir. 5 nolu düğüm için 3 ve 4 nolu düğümlerden bağlantı olmaktadır. 3 nolu düğüm dikkate alınırsa (14,3) ve 4 nolu düğüm dikkate alınırsa (12,4) uzaklık değerleri bulunur. Bunlar arasında ise en kısa uzaklık değeri olan [12,4] kalıcı etiket değeri seçilir. Böylece 1 ile 5 arasında en kısa yolu veren rota 1-4-5 şeklinde olup 12 birimdir.

Yorumlar
  • 0 Yorum