Shortest paths

Hazırlık: Bir kenar ekledikten sonra MST’yi güncelleme

You hold the MST T of a graph G, and a new edge e = (u, v) of weight w is added. Find the MST of G + e in O(n). Adding e to T closes exactly one cycle: the tree path from u to v plus e. The new MST is T + e minus the heaviest edge on that cycle (which might be e itself, in which case nothing changes). Finding the tree path is a DFS on T, which has only n − 1 edges: O(n).

G çizgesinin MST’si T elinizde ve ağırlığı w olan yeni bir e = (u, v) kenarı ekleniyor. G + e’nin MST’sini O(n) sürede bulun. T’ye e’yi eklemek tam bir döngü kapatır: u’dan v’ye ağaç yolu ile e. Yeni MST, T + e’den bu döngüdeki en ağır kenarın çıkarılmasıyla elde edilir (en ağır kenar e’nin kendisi olabilir; bu durumda hiçbir şey değişmez). Ağaç yolunu bulmak, yalnızca n − 1 kenarı olan T üzerinde DFS yapmaktır: O(n).

En kısa yollar neden önemlidir?

Transportation: the cheapest way to travel between two places.

Ulaşım: İki yer arasında seyahat etmenin en ucuz yolu.

Motion planning: the most natural route for a game character through its environment.

Hareket planlama: Bir oyun karakterinin çevresinde izleyeceği en doğal rota.

Communications: how long a message takes between two sites; which two sites are furthest apart (the network’s diameter).

İletişim: Bir iletinin iki nokta arasında ne kadar sürede ulaştığı; hangi iki noktanın birbirinden en uzak olduğu (ağın çapı).

Sentence disambiguation: Skiena’s group reconstructed text typed on a phone keypad where each key stands for several letters. Vertices were candidate words at each position, edges joined possible neighbouring words, and edge weights reflected how likely two words are to be adjacent (“give me” is cheaper than “hive me”). The most probable sentence is the shortest path through this DAG, found by the Viterbi algorithm, which is dynamic programming. The system got over 99% of characters right.

Cümle belirsizliğini giderme: Skiena’nın grubu, her tuşun birkaç harfi temsil ettiği telefon tuş takımında yazılmış metni yeniden oluşturdu. Tepeler her konumdaki aday sözcükler, kenarlar olası komşu sözcüklerin bağlantılarıydı; kenar ağırlıkları iki sözcüğün yan yana gelme olasılığını yansıtıyordu (“give me”, “hive me”den daha ucuzdur). En olası cümle, bu DAG üzerindeki en kısa yoldur ve bir dinamik programlama yöntemi olan Viterbi algoritmasıyla bulunur. Sistem, karakterlerin %99’undan fazlasını doğru belirledi.

Ağırlıksız, ağırlıklı ve negatif

In an unweighted graph the shortest path uses the fewest edges, and BFS finds it in O(n + m) (Lecture 11). In a weighted graph the length of a path is the sum of its edge weights, and BFS is useless: a path with more edges can be shorter (1 + 1 + 1 + 1 + 1 + 1 + 1 < 10). There can be exponentially many shortest paths between two vertices, so we ask for one, not all.

Ağırlıksız çizgede en kısa yol en az sayıda kenarı kullanır ve BFS bunu O(n + m) sürede bulur (Ders 11). Ağırlıklı çizgede yolun uzunluğu, kenar ağırlıklarının toplamıdır; BFS işe yaramaz: daha fazla kenarlı bir yol daha kısa olabilir (1 + 1 + 1 + 1 + 1 + 1 + 1 < 10). İki tepe arasında üstel sayıda en kısa yol bulunabilir; bu nedenle hepsini değil, birini isteriz.

Negative weights cause trouble. A cycle whose total weight is negative makes “shortest” meaningless, since going round the cycle again always makes the path shorter. This lecture assumes all weights are positive; other algorithms (such as Bellman-Ford) cope with negative edges as long as there are no negative cycles. Minimum spanning trees, by contrast, are unaffected by negative weights.

Negatif ağırlıklar sorun yaratır. Toplam ağırlığı negatif olan bir döngü, “en kısa” kavramını anlamsızlaştırır; çünkü döngüyü bir kez daha dolaşmak yolu her zaman kısaltır. Bu derste bütün ağırlıkların pozitif olduğu varsayılır. Başka algoritmalar (Bellman–Ford gibi), negatif döngü bulunmadığı sürece negatif kenarlarla başa çıkar. Buna karşılık minimum kapsayan ağaçlar negatif ağırlıklardan etkilenmez.

Dijkstra algoritması

The principle: if s → … → x → … → t is a shortest path from s to t, then the part s → … → x must be a shortest path from s to x. (If there were a shorter way to x, splicing it in would shorten the whole path.) So shortest paths are built out of shortest paths to nearer vertices, a dynamic-programming flavour of reasoning.

İlke şudur: s → … → x → … → t, s’ten t’ye en kısa yolsa s → … → x kısmı da s’ten x’e en kısa yol olmalıdır. (x’e daha kısa bir yol olsaydı onu araya koymak bütün yolu kısaltırdı.) Dolayısıyla en kısa yollar, daha yakın tepelere giden en kısa yollardan oluşur; bu, dinamik programlama türünde bir akıl yürütmedir.

Start with d(s, s) = 0. With positive weights, the cheapest edge out of s, say (s, x), gives d(s, x) exactly. Whenever the shortest distance to a new vertex x becomes known, look along each edge (x, y) to see whether going through x offers a shorter way to y.

d(s, s) = 0 ile başlayın. Pozitif ağırlıklarda s’ten çıkan en ucuz kenar, örneğin (s, x), d(s, x)’i tam olarak verir. Yeni bir x tepesine en kısa uzaklık bilinir hâle geldiğinde, x üzerinden gitmenin y’ye daha kısa bir yol sağlayıp sağlamadığını görmek için her (x, y) kenarına bakın.

Dijkstra(G, s, t):
    known = {s}; dist[i] = ∞ for all i; dist[s] = 0
    for each edge (s, v): dist[v] = w(s, v)
    last = s
    while last != t:
        v = the unknown vertex with the smallest dist[]
        for each edge (v, x): dist[x] = min(dist[x], dist[v] + w(v, x))
        last = v; known = known ∪ {v}

Dijkstra(G, s, t):
    known = {s}; her i için dist[i] = ∞; dist[s] = 0
    for her (s, v) kenarı: dist[v] = w(s, v)
    last = s
    while last != t:
        v = dist[] değeri en küçük olan bilinmeyen tepe
        for her (v, x) kenarı:
            dist[x] = min(dist[x], dist[v] + w(v, x))
        last = v; known = known ∪ {v}

This is essentially Prim’s algorithm. In the code, only three lines differ: Prim updates distance[w] with the weight of the single edge (v, w); Dijkstra updates it with distance[v] + weight(v, w), the length of the whole path through v. Run on the slides’ 7-vertex example from vertex A, it produces a shortest-path tree in which the tree path from A to each vertex is a shortest path.

Bu, özünde Prim algoritmasıdır. Kodda yalnızca üç satır farklıdır: Prim, distance[w] değerini tek (v, w) kenarının ağırlığıyla günceller; Dijkstra ise v’den geçen bütün yolun uzunluğu olan distance[v] + weight(v, w) ile günceller. Slaytlardaki 7 tepeli örnekte A’dan başlatıldığında, A’dan her tepeye giden ağaç yolunun en kısa yol olduğu bir en kısa yol ağacı üretir.

Cost. Exactly as for Prim: n rounds, each with an O(n) scan for the minimum and O(n) worth of updates, so O(n²). That is optimal for dense graphs.

Maliyet. Prim’dekiyle aynıdır: her birinde minimum için O(n) tarama ve O(n) güncelleme bulunan n tur, yani O(n²). Bu, yoğun çizgeler için optimaldir.

Faster with better data structures. Keep the fringe vertices in a heap ordered by distance; each of the m edge relaxations may lower a key, costing O(log n), and each of the n extractions costs O(log n): O(m log n), better on sparse graphs. Fibonacci heaps, which lower a key in O(1) amortised time, give O(n log n + m), the best known bound.

Daha iyi veri yapılarıyla daha hızlı. Sınırdaki tepeleri uzaklığa göre sıralanmış bir öbekte tutun. m kenar gevşetmesinin her biri bir anahtarı azaltabilir; bunun maliyeti O(log n)’dir. n çıkarma işleminin her biri de O(log n) sürer: O(m log n), seyrek çizgelerde daha iyidir. Bir anahtarı amortize O(1) sürede azaltan Fibonacci öbekleri, bilinen en iyi sınır olan O(n log n + m)’yi verir.

Hazırlık 2: Her kenara bir sabit ekleme

If every edge weight in G goes up by the same constant k, is the shortest-path tree from v still a shortest-path tree? No. A path with more edges pays k more times. A 3-edge path of length 3 beats a 1-edge path of length 4, but after adding k = 10 to every edge the 3-edge path costs 33 and the 1-edge path 14.

G’deki her kenarın ağırlığı aynı k sabiti kadar artarsa, v’den başlayan en kısa yol ağacı hâlâ bir en kısa yol ağacı mıdır? Hayır. Daha fazla kenarlı bir yol, k maliyetini daha çok kez öder. Uzunluğu 3 olan 3 kenarlı yol, uzunluğu 4 olan 1 kenarlı yoldan iyidir; fakat her kenara k = 10 eklenince 3 kenarlı yol 33, 1 kenarlı yol 14 maliyetli olur.

Bütün çiftler arasında en kısa yollar ve Floyd algoritması

Finding the shortest path between one pair (s, t) already requires, in the worst case, finding shortest paths from s to everything. Many applications, such as the centre or diameter of a network, need the distance between every pair. Running Dijkstra from each of the n vertices costs n × O(n²) = O(n³). Can we do better? Not asymptotically, but Floyd’s algorithm is simpler and faster in practice.

Tek bir (s, t) çifti arasındaki en kısa yolu bulmak bile, en kötü durumda s’ten bütün tepelere en kısa yolları bulmayı gerektirir. Ağın merkezi veya çapı gibi birçok uygulama, her çift arasındaki uzaklığa ihtiyaç duyar. Dijkstra’yı n tepenin her birinden çalıştırmak n × O(n²) = O(n³) sürer. Daha iyisini yapabilir miyiz? Asimptotik olarak hayır; ancak Floyd algoritması daha basittir ve uygulamada daha hızlıdır.

It is an instance of the four-step dynamic programming recipe that Lecture 16 develops in full:

Bu, Ders 16’da ayrıntılı olarak geliştirilen dört adımlı dinamik programlama tarifinin bir örneğidir:

Characterise the structure of an optimal solution.

Optimal çözümün yapısını karakterize edin.

Define the value of an optimal solution recursively.

Optimal çözümün değerini özyinelemeli olarak tanımlayın.

Compute the recurrence bottom-up.

Yineleme bağıntısını aşağıdan yukarıya hesaplayın.

Extract the solution from the computed table.

Çözümü hesaplanan tablodan çıkarın.

The set-up. Start from a distance matrix D with D[i, j] = w(i, j) if (i, j) is an edge, 0 if i = j, and ∞ otherwise. This gives shortest paths that use no intermediate vertices.

Kurulum. (i, j) bir kenarsa D[i, j] = w(i, j), i = j ise 0, diğer durumlarda ∞ olan bir D uzaklık matrisiyle başlayın. Bu, hiçbir ara tepe kullanmayan en kısa yolları verir.

The recurrence. Number the vertices 1 to n. Let d[i, j]ᵏ be the length of the shortest path from i to j whose intermediate vertices all come from {1, 2, …, k}. Such a path either avoids vertex k, in which case it was already the best using {1, …, k − 1}, or it goes through k exactly once, in which case it is a best path from i to k followed by a best path from k to j, both using only {1, …, k − 1}:

Yineleme bağıntısı. Tepeleri 1’den n’ye numaralandırın. d[i, j]ᵏ, bütün ara tepeleri {1, 2, …, k} kümesinden seçilen, i’den j’ye en kısa yolun uzunluğu olsun. Böyle bir yol ya k tepesini kullanmaz; bu durumda {1, …, k − 1} ile zaten en iyi olan yoldur. Ya da k’den tam bir kez geçer; bu durumda yalnızca {1, …, k − 1} kullanan en iyi i–k yoluyla en iyi k–j yolunun birleşimidir:

The algorithm is just this recurrence computed for k = 1, 2, …, n, updating the matrix in place:

Algoritma, matrisi yerinde güncelleyerek bu bağıntıyı k = 1, 2, …, n için hesaplamaktan ibarettir:

floyd(D):
    for k from 1 to n:
        for i from 1 to n:
            for j from 1 to n:
                D[i, j] = min(D[i, j], D[i, k] + D[k, j])

floyd(D):
    for k from 1 to n:
        for i from 1 to n:
            for j from 1 to n:
                D[i, j] = min(D[i, j], D[i, k] + D[k, j])

Three nested loops of n: Θ(n³), the same as n runs of Dijkstra, but the loop body is one addition and one comparison, so it wins by a constant factor. Note that k, the “allowed intermediate vertex”, must be the outer loop.

n uzunluklu üç iç içe döngü: Θ(n³), yani Dijkstra’nın n kez çalıştırılmasıyla aynı. Ancak döngü gövdesi bir toplama ve bir karşılaştırmadan oluştuğundan sabit çarpan avantajı sağlar. “İzin verilen ara tepe” olan k’nin en dış döngü olması gerektiğine dikkat edin.

Transitive closure. Replace “min and plus” with “or and and”, and the same algorithm computes which pairs (i, j) are joined by some path: the transitive closure of the graph. This is how a database propagates consequences of facts, as in “is x related to y?”.

Geçişli kapanış. “Minimum ve toplama” yerine “veya ve ve” işlemlerini koyarsanız aynı algoritma, hangi (i, j) çiftlerinin bir yolla bağlı olduğunu, yani çizgenin geçişli kapanışını hesaplar. Bir veri tabanı, “x, y ile ilişkili mi?” örneğinde olduğu gibi olgulardan doğan sonuçları bu şekilde yayar.