Graph veri yapısında bir vertex’den başka bir vertex’e en az maliyetli yoldan gitmek için kullanılan algoritmalara shortest path algoritm (kısa yol algoritması) denir.
En bilinen algoritmalardan biri Dijkstra Algorithm‘dır.
Dijkstra Algorithm
İlk olarak bir başlangıç vertex’i belirlenir. O vertex’in kendine olan uzaklığı 0, graph’daki diğer tüm vertex’lere uzaklığı sonsuz kabul edilir. Sonrasında vertex’in komşularının maliyetleri ve komşularının komşularının maliyetleri güncellenerek devam eder. Yani breadth first search kullanılmış olur.
Aşağıdaki graph’da başlangıç vertex’i “A” olmak üzere, A’dan diğer vertex’lere ulaşabilmek için gerekli olan minimum maliyetleri Dijkstra algoritmasını kullanarak bulalım.
İlk olarak B’nin maliyetini inceleyelim. 0+3 < ∞ ? Evet. B’nin maliyetini 3 ile güncelleyelim.
B’nin komşuları; C, E ve G’nin maliyetlerini inceleyelim.
C için, 3+4 < ∞ ? Evet. C’nin maliyetini 7 ile güncelleyelim.
E için, 3+6 < ∞ ? Evet. E’nin maliyetini 9 ile güncelleyelim.
G için, 3+2 < ∞ ? Evet. C’nin maliyetini 5 ile güncelleyelim.
G’nin komşusu F’yi inceleyelim. 5+2 < ∞ ? Evet. F’nin maliyetini 7 ile güncelleyelim.
C’nin komşusu D’yi inceleyelim. 7+3 < ∞ ? Evet. D’nin maliyetini 10 ile güncelleyelim.
E’nin komşuları B, D ve F’yi inceleyelim.
B için, 9+6 < ∞ 3 ? Hayır. B’nin maliyeti aynı kaldı.
D için, 9+1 < 10 ? Hayır. D’nin maliyeti aynı kaldı.
F için, 9+4 < 7 ? Hayır. F’nin maliyeti aynı kaldı.
D’nin komşusu E’nin maliyetini inceleyelim. 10+1 < 9 ? Hayır. E’nin maliyeti aynı kaldı.
Ve son olarak F’nin komşusu E’yi inceleyelim. 7+4 < 9 ? Hayır. E’nin maliyeti aynı kaldı.
Bu şekilde A vertex’inden graph’daki diğer vertex’lere gidebilmek için gerekli minimum maliyetleri bulduk.