Kesinleşen
Kuyrukta
İncelenen kenar

  • Şu anki
  • Kuyrukta
  • Kesinleşen
  • Yol
Tıklamayla belirlenen

Dijkstra algoritması hakkında daha fazla

Dijkstra algoritması

Dijkstra algoritması, şehirler arasındaki yollar gibi kenarların uzunlukları olduğunda, başlangıçtan diğer her düğüme en kısa rotayı bulur. Başlangıçtan dışarı doğru büyür ve her zaman henüz bitirmediği en yakın düğümü alır. Bir düğümden başlamak için ona tıklayın, isterseniz bir hedef seçin ve kuyruğu, daha kısa yollar çıktıkça her uzaklığın düşüşünü ve en kısa yolun belirişini görmek için adım adım ilerleyin. Aramayı 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. Bir düğümü başlangıç yapmak için ona tıklayın; tıklamayı Hedef'e çevirip başka bir düğüme tıklayarak oraya giden en kısa yolu arayın. Her kenardaki sayı o kenarın uzunluğu, her düğümdeki sayı ise şimdiye kadarki en kısa uzaklığıdır; grafın altındaki satır, en yakını başta olmak üzere kuyruktur. 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. Bir düğümü başlangıç yapmak için ona tıklayın. Yol aramak için tıklamayı Hedef'e çevirin ve başka bir düğüme tıklayın.
  2. Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Aramada herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
  3. Grafın altındaki kuyruğu ve her düğümdeki uzaklığı izleyin. Yeni graf, denemeniz için başka bir graf oluşturur.

Dijkstra algoritması nasıl çalışır

Başlangıca uzaklık 0, diğer her düğüme sonsuz verin ve başlangıcı bir kuyruğa koyun. Sonra tekrarlayın: kuyruktaki en küçük uzaklığa sahip düğümü alın ve bu uzaklığı kesin olarak işaretleyin. Kesinleşmemiş her komşusu için kenarın uzunluğunu düğümün uzaklığına ekleyin. Toplam, komşunun şimdiye kadarki uzaklığından küçükse yeni uzaklık olur, düğüm oraya giden yol olarak hatırlanır ve komşu kuyrukta değilse kuyruğa eklenir. Kuyruk boşaldığında ulaşılabilen her düğümün en kısa uzaklığı belli olur.

En yakın düğüm neden kesindir

Bir düğüm kuyruktaki en yakın düğüm olduğunda, ona giden başka her yol grafın bitmiş kısmından kuyruktaki bir düğüm üzerinden çıkmak zorundadır; bu düğüm en az onun kadar uzaktır ve ardından eklenen kenarlar negatif olamaz. Yani başka hiçbir yol daha kısa olamaz. Bu yüzden bir hedef, ilk ulaşıldığında değil, ancak kuyruktan alındığında kesinleşir; Dijkstra algoritmasının negatif kenarlarda başarısız olmasının nedeni de budur: orada Bellman–Ford algoritması gerekir. Her kenarın uzunluğu 1 olduğunda Dijkstra algoritması genişlik öncelikli aramayla aynı şeyi yapar.

Sık sorulan sorular

Dijkstra algoritması nedir?

Kenar uzunlukları sıfır ya da daha büyük olan bir grafta, bir başlangıç düğümünden diğer tüm düğümlere en kısa yolları bulma yöntemidir. Tekrar tekrar bitmemiş en yakın düğümü alır, uzaklığını kesinleştirir ve kenarlarını kullanarak komşularının uzaklıklarını kısaltır.

Dijkstra algoritması neden negatif kenarlarla çalışmaz?

Bir düğüm kuyruktaki en yakın düğüm olur olmaz uzaklığını kesinleştirir. Daha sonra bulunan negatif bir kenar, o düğüme daha kısa bir yoldan geri götürebilir; bu yüzden kesin uzaklık yanlış olabilir. Bellman–Ford algoritması, toplamı negatif olan bir döngü olmadığı sürece negatif kenarlarla başa çıkar.

Dijkstra ile BFS arasındaki fark nedir?

Genişlik öncelikli arama kenarları sayar ve sıradan bir kuyruk kullanır. Dijkstra algoritması kenar uzunluklarını toplar ve her zaman en yakın düğümü veren bir öncelik kuyruğu kullanır. Her kenarın uzunluğu 1 olduğunda ikisi de aynı uzaklıkları bulur.

Dijkstra algoritması ne kadar hızlıdır?

Öncelik kuyruğu olarak ikili yığın kullanıldığında iş, V düğüm ve E kenar için (V + E) log V ile artar. Fibonacci yığınıyla E + V log V olur. Uygulama kuyruğu sıralı bir liste olarak tutar; bu, göstermesi kolaydır ve küçük graflar için yeterlidir.

Grafım bir yere gönderiliyor mu?

Hayır. Graf tarayıcınızda oluşturulur ve aranır, 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