Ara durak
Kısalan çiftler
İncelenen çift

  • Şu anki ara durak
  • Ara durak olmuş
  • Kısalan çift
  • Yol
Tıklamayla belirlenen

Floyd–Warshall algoritması hakkında daha fazla

Floyd–Warshall algoritması

Her şehirden diğer her şehre ne kadar yol var? Floyd–Warshall bunu tek seferde, bir tablo ve iç içe üç döngüyle yanıtlar. Her tur, yolda ara durak olarak bir düğüme daha izin verir ve her çift için o düğümden dolaşmanın daha kısa olup olmadığını sorar. Tablonun dolmasını ve uzaklıkların düşmesini görmek için adım adım ilerleyin. Tablonun dolmasını izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Tablo, her düğüm çifti arasında şimdiye kadar bulunan en kısa uzaklığı tutar; her kenardaki sayı o kenarın uzunluğudur. Her tur, yolda ara durak olarak bir düğüme daha izin verir ve her adım, bu durak sayesinde kısalan bir çifti gösterir. Bir düğümü başlangıç yapmak için ona tıklayın; sonunda ikisi arasındaki en kısa yolu görmek için tıklamayı Hedef'e çevirin ve başka bir düğüme tıklayın. Yeni graf başka bir graf oluşturur; kaç düğüm ve kenar olacağını seçin. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.

Nasıl çalışır

  1. Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
  2. Tabloyu izleyin: şu anki ara durağın satırı ve sütunu renklidir, her adım da daha kısa bir uzaklık yazar.
  3. Sonunda aralarındaki en kısa yolu görmek için bir başlangıç ve bir hedef seçin. Yeni graf, denemeniz için başka bir graf oluşturur.

Floyd–Warshall nasıl çalışır

Her düğüm için bir satırı ve bir sütunu olan bir tablo yapın. Köşegene 0, iki düğümün bağlı olduğu yere kenarın uzunluğunu, diğer her yere sonsuz yazın. Sonra her k düğümünü sırayla olası ara durak olarak alın. Her i, j çifti için tablodaki i'den j'ye uzaklığı, i'den k'ye uzaklık ile k'den j'ye uzaklığın toplamıyla karşılaştırın ve küçük olanı tutun. Son düğümden sonra her hücre, iki düğümü arasındaki en kısa uzaklıktır.

Neden çalışır

k'nin turundan sonra tablo, her çift için ara duraklarının hepsi o ana kadar ele alınan düğümlerden olan en kısa yolu tutar. Sonraki düğümün turu yalnızca o düğümün işe yarayıp yaramadığına karar verir: onun üzerinden geçen en kısa yol, ona giden en kısa yol ile ondan çıkan en kısa yolun toplamıdır ve ikisi de zaten tablodadır. Büyük bir yanıtı önceden bulunmuş küçük yanıtlardan bu şekilde kurmaya dinamik programlama denir. Negatif kenarlarla da çalışır; köşegendeki negatif bir sayı negatif bir döngüyü ele verir.

Sık sorulan sorular

Floyd–Warshall algoritması nedir?

Ağırlıklı bir grafta her düğüm çifti arasındaki en kısa uzaklığı bulan bir algoritma. Bir uzaklık tablosu tutar ve sırayla her düğüm için, o düğümden geçmenin bir çifti kısaltıp kısaltmadığına bakar.

Floyd–Warshall ne kadar hızlıdır?

n düğüm üzerinde iç içe üç döngüsü vardır, yani iş n³ ile artar ve tablo n² hücre gerektirir. Bu, birkaç yüz düğümlü graflar için sorun değildir. Büyük seyrek graflarda Dijkstra algoritmasını her düğümden çalıştırmak daha hızlıdır.

Floyd–Warshall negatif kenarlarla çalışır mı?

Evet, negatif döngü olmadığı sürece. Varsa köşegendeki bir hücre negatif olur; Floyd–Warshall döngüyü böyle fark eder.

Yalnızca uzaklıkları değil, yolları nasıl elde ederim?

i'den j'ye giden yoldaki bir sonraki düğümü tutan ikinci bir tablo kullanın. Bir çift k üzerinden kısaldığında, i'den k'ye doğru giden yoldaki bir sonraki düğümü kopyalayın. Bu tabloyu i'den j'ye izlediğinizde yol ortaya çıkar.

Grafım bir yere gönderiliyor mu?

Hayır. Graf tarayıcınızda oluşturulur ve tablo orada doldurulur, son ayarlarınız da bu tarayıcının yerel depolamasında kalır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git