1-) VERİYAPILARI - Bellman Ford Algoritması

Bu algoritmanın amacı, bir şekil (graph) üzerindeki, bir kaynaktan (source) bir hedefe(target veya sink) giden en kısa yolu bulmaktır. Her nokta ile komşuları arasındaki Cost belirlenir ve birer matris olarak yazılır. Daha sonra bu matrisler arasında yapılan karşılaştırma sonucunda en kısa yollar hesaplanır.

Eğer graf negatif maliyetli çember içeriyorsa, en az maliyetli yol tanımlanamaz.

Ana mantık:  (güncelleme olmayana kadar tüm kenarları gez)

• Her düğüm için bir uzaklık tahmini oluşturulur. 
• Başlangıç olarak maliyet(s)=0 diğer düğümler için maliyet(u)= ∞ olarak atanır.
•  En az maliyetli yol hesaplanana kadar tüm kenarlar üzerinden güncelleme yapılır. 

Algoritma ayrıca grafın negatif maliyetli kenarının olup olmadığını da bulur. 

Dijkstra’nın algoritmasına göre daha yavaş çalışır.  (Dijkstra algoritması negatif kenarlarda kullanılmaz.)

Kaba Kod:

ÖRN 1:

ÖRN 2 :

A-B

A-C

A-C-D

A-B-E

A-C-F