En kısa yol problemi - Shortest path problem

Ağırlıklı yönlendirilmiş grafikte A ve F köşeleri arasındaki en kısa yol (A, C, E, D, F)

İçinde grafik teorisi, en kısa yol problemi bulmanın problemi yol ikisi arasında köşeler (veya düğümler) bir grafik öyle ki toplamı ağırlıklar kurucu kenarlarının oranı en aza indirilmiştir.

Bir yol haritasında iki kavşak arasındaki en kısa yolu bulma problemi, grafiklerdeki en kısa yol probleminin özel bir durumu olarak modellenebilir; burada köşeler kavşaklara karşılık gelir ve kenarlar, her biri yolun uzunluğuna göre ağırlıklandırılmış yol segmentlerine karşılık gelir. segment.

Tanım

En kısa yol problemi için tanımlanabilir grafikler olup olmadığı yönsüz, yönetilen veya karışık Yönlendirilmemiş grafikler için burada tanımlanmıştır; Yönlendirilmiş grafikler için yol tanımı, ardışık köşelerin uygun bir yönlendirilmiş kenar ile bağlanmasını gerektirir.

Her ikisi de ortak bir kenara denk geldiklerinde iki köşe bitişiktir. yol yönsüz bir grafikte sıra köşelerin ${ displaystyle P = (v_ {1}, v_ {2}, ldots, v_ {n}) in V times V times cdots times V}$ öyle ki ${ displaystyle v_ {i}}$ bitişik ${ displaystyle v_ {i + 1}}$ için ${ displaystyle 1 leq i$ Böyle bir yol ${ displaystyle P}$ uzunluk yolu denir ${ displaystyle n-1}$ itibaren ${ displaystyle v_ {1}}$ -e ${ displaystyle v_ {n}}$ . (The ${ displaystyle v_ {i}}$ değişkenlerdir; buradaki numaralandırmaları, sıradaki konumlarıyla ilgilidir ve köşelerin herhangi bir kanonik etiketlemesiyle ilgili olması gerekmez.)

İzin Vermek ${ displaystyle e_ {i, j}}$ ikisine de uç olay olmak ${ displaystyle v_ {i}}$ ve ${ displaystyle v_ {j}}$ . Verilen bir gerçek değerli ağırlık fonksiyonu ${ displaystyle f: E rightarrow mathbb {R}}$ ve yönlendirilmemiş (basit) bir grafik ${ displaystyle G}$ en kısa yol ${ displaystyle v}$ -e ${ displaystyle v '}$ yol ${ displaystyle P = (v_ {1}, v_ {2}, ldots, v_ {n})}$ (nerede ${ displaystyle v_ {1} = v}$ ve ${ displaystyle v_ {n} = v '}$ ) her şeyin ötesinde ${ displaystyle n}$ toplamı en aza indirir ${ displaystyle toplamı _ {i = 1} ^ {n-1} f (e_ {i, i + 1}).}$ Grafikteki her kenar birim ağırlığa sahip olduğunda veya ${ displaystyle f: E rightarrow {1 }}$ , bu en az kenarı olan yolu bulmaya eşdeğerdir.

Sorun aynı zamanda bazen tek çift en kısa yol problemi, aşağıdaki varyasyonlardan ayırt etmek için:

tek kaynaklı en kısa yol problemi, bir kaynak tepe noktasından en kısa yolları bulmamız gereken v grafikteki diğer tüm köşelere.
tek hedef en kısa yol problemi, yönlendirilen grafikteki tüm köşelerden tek bir hedef köşeye en kısa yolları bulmamız gereken v. Bu, yönlendirilmiş grafikteki yayları ters çevirerek tek kaynaklı en kısa yol problemine indirgenebilir.
tüm çiftler en kısa yol problemi, her köşe çifti arasında en kısa yolları bulmamız gereken v, v ' grafikte.

Bu genellemeler, ilgili tüm köşe çiftleri üzerinde tek çift en kısa yol algoritması çalıştırmanın basit yaklaşımından önemli ölçüde daha verimli algoritmalara sahiptir.

Algoritmalar

Bu sorunu çözmek için en önemli algoritmalar şunlardır:

Dijkstra algoritması Negatif olmayan kenar ağırlığı ile tek kaynaklı en kısa yol problemini çözer.
Bellman-Ford algoritması Kenar ağırlıkları negatifse tek kaynaklı sorunu çözer.
A * arama algoritması Aramayı hızlandırmaya çalışmak için buluşsal yöntemleri kullanarak tek çift en kısa yolu çözer.
Floyd – Warshall algoritması tüm çiftleri en kısa yolları çözer.
Johnson'ın algoritması tüm çiftleri en kısa yolları çözer ve Floyd – Warshall'dan daha hızlı olabilir seyrek grafikler.
Viterbi algoritması Her düğümde ek bir olasılık ağırlığı ile en kısa stokastik yol problemini çözer.

Ek algoritmalar ve ilgili değerlendirmeler şurada bulunabilir: Cherkassky, Goldberg ve Radzik (1996).

Tek kaynaklı en kısa yollar

Yönlendirilmemiş grafikler

Ağırlıklar	Zaman karmaşıklığı	Yazar
ℝ₊	Ö(V²)	Dijkstra 1959
ℝ₊	Ö((E + V) günlükV)	Johnson 1977 (ikili yığın )
ℝ₊	Ö(E + V günlükV)	Fredman ve Tarjan 1984 (Fibonacci yığını )
ℕ	Ö(E)	Thorup 1999 (sabit zamanlı çarpma gerektirir)

Ağırlıksız grafikler

Algoritma	Zaman karmaşıklığı	Yazar
Kapsamlı arama	Ö(E + V)

Yönlendirilmiş çevrimsiz grafikler (DAG'ler)

Kullanan bir algoritma topolojik sıralama tek kaynaklı en kısa yol problemini zamanında çözebilir $Θ (E + V)$ keyfi ağırlıklı DAG'lerde.^[1]

Negatif olmayan ağırlıklara sahip yönlendirilmiş grafikler

Aşağıdaki tablo, Schrijver (2004), bazı düzeltmeler ve eklemelerle. Yeşil bir arka plan, tablodaki asimptotik olarak en iyi sınırı gösterir; L tamsayı kenar ağırlıkları varsayılarak, tüm kenarlar arasındaki maksimum uzunluk (veya ağırlık).

Ağırlıklar	Algoritma	Zaman karmaşıklığı	Yazar
ℝ		Ö(V²EL)	Ford 1956
ℝ	Bellman-Ford algoritması	Ö(VE)	Shimbel 1955, Bellman 1958, Moore 1959
ℝ		Ö(V² günlükV)	Dantzig 1960
ℝ	Dijkstra algoritması liste ile	Ö(V²)	Leyzorek vd. 1957, Dijkstra 1959, Darphane (bkz. Pollack ve Wiebenson 1960 ), Mezgit ve Hillier 1960
ℝ	Dijkstra algoritması ile ikili yığın	Ö((E + V) günlükV)	Johnson 1977
ℝ	Dijkstra algoritması ile Fibonacci yığını	Ö(E + V günlükV)	Fredman ve Tarjan 1984, Fredman ve Tarjan 1987
ℕ	Dial'ın algoritması^[2] (Dijkstra algoritması kullanarak kova sırası ile L kovalar)	Ö(E + LV)	1969'u çevir
		Ö(E günlük günlüğüL)	Johnson 1981, Karlsson ve Poblete 1983
	Gabow algoritması	Ö(E günlük_E/V L)	Gabow 1983, Gabow 1985
		Ö(E + V √günlük L)	Ahuja vd. 1990
	Thorup	Ö(E + V günlük günlüğüV)	Thorup 2004

Negatif döngüleri olmayan keyfi ağırlıklara sahip yönlendirilmiş grafikler

Ağırlıklar	Algoritma	Zaman karmaşıklığı	Yazar
ℝ		Ö(V²EL)	Ford 1956
ℝ	Bellman-Ford algoritması	Ö(VE)	Shimbel 1955, Bellman 1958, Moore 1959
ℝ	Johnson-Dijkstra ile ikili yığın	Ö(V (E + günlükV))	Johnson 1977
ℝ	Johnson-Dijkstra ile Fibonacci yığını	Ö(V (E + günlükV))	Fredman ve Tarjan 1984, Fredman ve Tarjan 1987, sonra uyarlandı Johnson 1977
ℕ	Johnson'ın tekniği Dial'ın algoritmasına uygulandı^[2]	Ö(V (E + L))	1969'u çevir, sonra uyarlandı Johnson 1977

Rasgele ağırlıklara sahip düzlemsel yönelimli grafikler

Tüm çiftler en kısa yollar

Tüm çiftler en kısa yol problemi, her köşe çifti arasındaki en kısa yolları bulur $v$ , $v '$ grafikte. Ağırlıksız yönlendirilmiş grafikler için tüm çiftler en kısa yollar problemi, Shimbel (1953), toplam süre alan doğrusal sayıda matris çarpımı ile çözülebileceğini gözlemleyen $Ö (V 4)$ .

Yönsüz grafik

Ağırlıklar	Zaman karmaşıklığı	Algoritma
ℝ₊	$Ö (V 3)$	Floyd – Warshall algoritması
${ displaystyle {1, infty }}$	${ displaystyle O (V ^ { omega} log V)}$	Seidel algoritması (beklenen çalışma süresi)
ℕ	${ displaystyle O (V ^ {3} / 2 ^ { Omega ( log n) ^ {1/2}})}$	Williams 2014
ℝ₊	$Ö (EV log α (E, V))$	Pettie ve Ramachandran 2002
ℕ	$Ö (EV)$	Thorup 1999 her köşe noktasına uygulanır (sabit zamanlı çarpma gerektirir).

Yönlendirilmiş grafik

Ağırlıklar	Zaman karmaşıklığı	Algoritma
ℝ (negatif döngü yok)	$Ö (V 3)$	Floyd – Warshall algoritması
ℕ	${ displaystyle O (V ^ {3} / 2 ^ { Omega ( log n) ^ {1/2}})}$	Williams 2014
ℝ (negatif döngü yok)	$Ö (EV + V 2 günlük V)$	Johnson – Dijkstra
ℝ (negatif döngü yok)	$Ö (EV + V 2 günlük günlüğü V)$	Pettie 2004
ℕ	$Ö (EV + V 2 günlük günlüğü V)$	Hagerup 2000

Başvurular

En kısa yol algoritmaları, fiziksel konumlar arasındaki yol tariflerini otomatik olarak bulmak için uygulanır. web haritası gibi web siteleri MapQuest veya Google Maps. Bu uygulama için hızlı özel algoritmalar mevcuttur.^[3]

Biri kesin olmayan bir soyut makine Köşelerin durumları ve kenarların olası geçişleri tanımladığı bir grafik olarak, en kısa yol algoritmaları, belirli bir hedef durumuna ulaşmak için en uygun seçim dizisini bulmak veya belirli bir duruma ulaşmak için gereken zamanda daha düşük sınırlar oluşturmak için kullanılabilir. Örneğin, köşeler bir bulmacanın durumlarını bir Rubik küp ve her yönlendirilmiş kenar tek bir hareket veya dönüşe karşılık gelir, mümkün olan minimum sayıda hareket kullanan bir çözüm bulmak için en kısa yol algoritmaları kullanılabilir.

İçinde ağ oluşturma veya telekomünikasyon zihniyet, bu en kısa yol problemine bazen minimum gecikme yolu problemi denir ve genellikle bir en geniş yol problemi. Örneğin, algoritma en kısa (minimum gecikme) en geniş yolu veya en geniş kısa (minimum gecikme) yolu arayabilir.

Daha gönülsüz bir uygulama, "altı derece ayrılık "aynı filmde görünen film yıldızları gibi grafiklerde en kısa yolu bulmaya çalışan.

Genellikle üzerinde çalışılan diğer uygulamalar yöneylem araştırması fabrika ve tesis yerleşimini içerir, robotik, ulaşım, ve VLSI tasarım.^[4]

Yol ağları

Bir yol ağı, pozitif ağırlıklara sahip bir grafik olarak düşünülebilir. Düğümler, yol kavşaklarını temsil eder ve grafiğin her kenarı, iki kavşak arasındaki bir yol segmentiyle ilişkilendirilir. Bir kenarın ağırlığı, ilişkili yol bölümünün uzunluğuna, bölümü geçmek için gereken süreye ya da bölümü geçmenin maliyetine karşılık gelebilir. Yönlendirilmiş kenarları kullanarak tek yönlü caddeleri modellemek de mümkündür. Bu tür grafikler, uzun mesafeli yolculuklar için (örneğin otoyollar) bazı kenarların diğerlerinden daha önemli olması açısından özeldir. Bu özellik, otoyol boyutu kavramı kullanılarak resmileştirilmiştir.^[5] Bu özelliği kullanan ve bu nedenle en kısa yolu genel grafiklerde mümkün olandan çok daha hızlı hesaplayabilen çok sayıda algoritma vardır.

Bu algoritmaların tümü iki aşamada çalışır. İlk aşamada, kaynak veya hedef düğüm bilinmeden grafik ön işlemden geçirilir. İkinci aşama, sorgu aşamasıdır. Bu aşamada kaynak ve hedef düğüm bilinir. Buradaki fikir, yol ağının statik olmasıdır, bu nedenle ön işleme aşaması bir kez yapılabilir ve aynı yol ağında çok sayıda sorgu için kullanılabilir.

Bilinen en hızlı sorgu süresine sahip algoritma, hub etiketleme olarak adlandırılır ve bir mikrosaniyenin çok küçük bir bölümünde Avrupa veya ABD'nin karayolu ağlarında en kısa yolu hesaplayabilir.^[6] Kullanılan diğer teknikler şunlardır:

ALT (Arama, önemli noktalar ve üçgen eşitsizliği )
Ark bayrakları
Kasılma hiyerarşileri
Transit düğüm yönlendirme
Erişim tabanlı budama
Etiketleme
Hub etiketleri

İlgili sorunlar

En kısa yol problemleri için hesaplamalı geometri, görmek Öklid'in en kısa yolu.

seyyar satıcı sorunu her tepe noktasından tam olarak bir kez geçen ve başlangıca dönen en kısa yolu bulma sorunudur. Negatif döngüleri olmayan grafiklerde polinom zamanda çözülebilen en kısa yol probleminin aksine, seyyar satıcı problemi NP tamamlandı ve bu nedenle, büyük veri kümeleri için verimli bir şekilde çözülemeyeceğine inanılmaktadır (bkz. P = NP sorunu ). Sorunu en uzun yolu bulmak bir grafikte de NP-tamamlandı.

Kanadalı gezgin sorunu ve stokastik en kısa yol problemi, grafiğin hareket ettiren tarafından tamamen bilinmediği, zaman içindeki değişimlerin veya eylemlerin (geçişlerin) olasılıksal olduğu genellemelerdir.

En kısa birden çok bağlantısı kesilmiş yol ^[7] çerçevesindeki ilkel yol ağının bir temsilidir Reptasyon teorisi.

en geniş yol problemi Herhangi bir kenarın minimum etiketinin mümkün olduğu kadar büyük olması için bir yol arar.

Stratejik en kısa yollar

Bazen bir grafikteki kenarların kişilikleri vardır: her kenarın kendi bencil ilgisi vardır. Bir örnek, her kenarın muhtemelen farklı bir kişiye ait olan bir bilgisayar olduğu bir iletişim ağıdır. Farklı bilgisayarların farklı iletim hızları vardır, bu nedenle ağdaki her kenarın bir mesajı iletmek için gereken milisaniye sayısına eşit bir sayısal ağırlığı vardır. Amacımız, ağdaki iki nokta arasında mümkün olan en kısa sürede mesaj göndermektir. Her bilgisayarın iletim süresini (her kenarın ağırlığı) biliyorsak, standart bir en kısa yol algoritması kullanabiliriz. İletim sürelerini bilmiyorsak, her bilgisayardan bize aktarım zamanını söylemesini istemeliyiz. Ancak bilgisayarlar bencil olabilir: bir bilgisayar bize iletim süresinin çok uzun olduğunu söyleyebilir, böylece onu mesajlarımızla rahatsız etmeyeceğiz. Bu soruna olası bir çözüm kullanmaktır VCG mekanizmasının bir çeşidi, bu da bilgisayarlara gerçek ağırlıklarını ortaya çıkarmaları için bir teşvik veriyor.

Doğrusal programlama formülasyonu

Doğal bir doğrusal programlama en kısa yol problemi için formülasyon aşağıda verilmiştir. Doğrusal programların diğer çoğu kullanımıyla karşılaştırıldığında çok basittir. ayrık optimizasyon ancak diğer kavramlarla bağlantıları göstermektedir.

Yönlendirilmiş bir grafik verildiğinde (V, Bir) kaynak düğüm ile s, hedef düğüm tve maliyet w_ij her kenar için (ben, j) içinde Birprogramı değişkenlerle düşünün x_ij

küçültmek

{ displaystyle sum _ {ij in A} w_ {ij} x_ {ij}}

tabi

{ displaystyle x geq 0}

ve herkes için ben,

{ displaystyle sum _ {j} x_ {ij} - sum _ {j} x_ {ji} = { başla {vakalar} 1, & { text {if}} i = s; - 1, & { text {if}} i = t; 0, & { text {aksi halde.}} end {vakalar}}}

Bunun arkasındaki sezgi şudur: ${ displaystyle x_ {ij}}$ kenarın (ben, j) en kısa yolun parçasıdır: Olduğunda 1, değilse 0. Bu setin bir yol oluşturduğu kısıtlamaya tabi olarak minimum ağırlıklı kenar setini seçmek istiyoruz. s -e t (eşitlik kısıtlamasıyla temsil edilir: hariç tüm köşeler için s ve t yolun parçası olan gelen ve giden kenarların sayısı aynı olmalıdır (yani, s'den t'ye bir yol olmalıdır).

Bu DP, ayrılmaz bir özelliğe sahiptir; daha spesifik olarak her temel optimal çözüm (biri mevcut olduğunda) tüm değişkenler 0 veya 1'e eşittir ve değişkenleri 1'e eşit olan kenarlar kümesi bir s-t dipat. Ahuja ve ark.^[8] bir kanıt için, bu yaklaşımın kökeni 20. yüzyılın ortalarına kadar uzanıyor.

Bu doğrusal programın ikili

maksimize etmek y_t − y_s herkese tabi ij, y_j − y_ben ≤ w_ij

ve uygulanabilir ikili, bir kavramına karşılık gelir tutarlı sezgisel için A * algoritması en kısa yollar için. Olası herhangi bir ikili için y düşük maliyetler ${ displaystyle w '_ {ij} = w_ {ij} -y_ {j} + y_ {i}}$ negatif değildir ve A * esasen çalışır Dijkstra algoritması bu azaltılmış maliyetler üzerinde.

Yarı işlerde genel cebirsel çerçeve: cebirsel yol problemi

Pek çok sorun, bir yol boyunca uygun şekilde ikame edilmiş bazı ekleme kavramları için en kısa yolun bir biçimi olarak çerçevelendirilebilir ve en aza indirilebilir. Bunlara genel yaklaşım, iki operasyonu bir operasyonun operasyonları olarak düşünmektir. yarı tesisat. Semiring çarpma yol boyunca yapılır ve toplama yollar arasındadır. Bu genel çerçeve, cebirsel yol problemi.^[9]^[10]^[11]

Klasik en kısa yol algoritmalarının (ve yenilerinin) çoğu, bu tür cebirsel yapılar üzerinde doğrusal sistemleri çözecek şekilde formüle edilebilir.^[12]

Daha yakın zamanlarda, bunları (ve çok daha az açık bir şekilde ilgili sorunları) çözmek için daha genel bir çerçeve geliştirilmiştir. değerleme cebirleri.^[13]

Stokastik zamana bağlı ağlarda en kısa yol

Gerçek yaşam koşullarında, ulaşım ağı genellikle stokastiktir ve zamana bağlıdır. Aslında, her gün bir bağlantı üzerinden geçen bir yolcu, yalnızca seyahat talebindeki dalgalanmalar (başlangıç-varış noktası matrisi) nedeniyle değil, aynı zamanda çalışma bölgeleri, kötü hava koşulları, kazalar ve araç arızaları gibi olaylar nedeniyle bu bağlantıda farklı seyahat süreleri yaşayabilir. . Sonuç olarak, stokastik zamana bağlı (STD) bir ağ, deterministik ağa kıyasla gerçek bir yol ağının daha gerçekçi bir temsilidir.^[14]^[15]

Geçtiğimiz on yıl boyunca kaydedilen önemli ilerlemeye rağmen, stokastik yol ağlarında optimal bir yolun nasıl tanımlanması ve belirlenmesi gerektiği tartışmalı bir soru olmaya devam etmektedir. Başka bir deyişle, belirsizlik altında optimal bir yolun benzersiz bir tanımı yoktur. Bu soruya verilebilecek olası ve yaygın bir cevap, beklenen minimum seyahat süresine sahip bir yol bulmaktır. Bu yaklaşımı kullanmanın temel avantajı, deterministik ağlar için tanıtılan verimli en kısa yol algoritmalarının, yolu stokastik bir ağda minimum beklenen seyahat süresiyle tanımlamak için kolayca kullanılabilmesidir. Bununla birlikte, bu yaklaşımla belirlenen sonuçta ortaya çıkan optimal yol güvenilir olmayabilir, çünkü bu yaklaşım seyahat süresi değişkenliğini ele almakta başarısız olur. Bu sorunu çözmek için bazı araştırmacılar, beklenen değer yerine seyahat süresi dağılımını kullanırlar, böylece toplam seyahat süresinin olasılık dağılımını aşağıdaki gibi farklı optimizasyon yöntemleri kullanarak bulurlar. dinamik program ve Dijkstra algoritması .^[16] Bu yöntemler kullanır stokastik optimizasyon, özellikle olasılıklı yay uzunluğuna sahip ağlarda en kısa yolu bulmak için stokastik dinamik programlama.^[17] Seyahat süresi güvenilirliği kavramı, ulaşım araştırma literatüründe seyahat süresi değişkenliği ile birbirinin yerine kullanılmaktadır, böylece genel olarak, seyahat süresindeki değişkenlik ne kadar yüksek olursa güvenilirliğin o kadar düşük olacağı ve bunun tersi de söylenebilir.

Seyahat süresi güvenilirliğini daha doğru bir şekilde hesaba katmak için, belirsizlik altında en uygun yol için iki ortak alternatif tanım önerilmiştir. Bazıları, belirli bir seyahat süresi bütçesinden daha önce veya zamanında varma olasılığını en üst düzeye çıkarmayı amaçlayan en güvenilir yol kavramını tanıttı. Diğerleri, alternatif olarak, önceden belirlenmiş bir zamanında varış olasılığını sağlamak için gereken seyahat süresi bütçesini en aza indirmeyi amaçladıkları bir a-güvenilir yol kavramını öne sürmüşlerdir.

Ayrıca bakınız

Çift yönlü arama Yönlendirilmiş bir grafikte iki köşe arasındaki en kısa yolu bulan bir algoritma
Öklid'in en kısa yolu
Akış ağı
K en kısa yol yönlendirme
Min artı matris çarpımı
Yol bulma
En Kısa Yol Köprüleme
En kısa yol ağacı

Referanslar

Notlar

^ Cormen vd. 2001, s. 655
^ ^a ^b Kadran, Robert B. (1969), "Algorithm 360: Topolojik Sıralama [H] ile En Kısa Yol Ormanı", ACM'nin iletişimi, 12 (11): 632–633, doi:10.1145/363269.363610
^ Sanders, Peter (23 Mart 2009). "Hızlı rota planlama". Google Tech Talk. Alıntı dergisi gerektirir | günlük = (Yardım)
^ Chen, Danny Z. (Aralık 1996). "Geometrik yol planlama problemleri için algoritma ve yazılım geliştirme". ACM Hesaplama Anketleri. 28 (4es). Madde 18 doi:10.1145/242224.242246. S2CID 11761485.
^ Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. "Karayolu Boyutu, En Kısa Yollar ve Yeterli Verimli Algoritmalar". Ayrık Algoritmalar hakkında ACM-SIAM Sempozyumu, sayfalar 782–793, 2010.
^ Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf "Yol Ağlarında En Kısa Yollar için Merkez Tabanlı Bir Etiketleme Algoritması". Deneysel Algoritmalar Sempozyumu, sayfalar 230–241, 2011.
^ Kroger, Martin (2005). "İki ve üç boyutlu polimerik sistemlerde dolanma analizi için en kısa çoklu bağlantısız yol". Bilgisayar Fiziği İletişimi. 168 (3): 209–232. Bibcode:2005CoPhC.168..209K. doi:10.1016 / j.cpc.2005.01.020.
^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Ağ Akışları: Teori, Algoritmalar ve Uygulamalar. Prentice Hall. ISBN 978-0-13-617549-0.
^ Pair, Claude (1967), Rosentiehl (ed.), "Sur des algoritthmes pour des problèmes de cheminement dans les graphes finis (On algoritmalar on sonlu graphs in path problem for)", Théorie des graphes (journées internationales d'études) - Theory of Graphs (uluslararası sempozyum), Roma (İtalya), Temmuz 1966: Dunod (Paris) et Gordon and Breach (New York), s. 271CS1 Maint: konum (bağlantı)
^ Derniame, Jean Claude; Çift, Claude (1971), Problèmes de cheminement dans les graphes (Grafiklerdeki Yol Problemleri), Dunod (Paris)
^ Baras, John; Theodorakopoulos, George (4 Nisan 2010). Ağlarda Yol Problemleri. Morgan & Claypool Yayıncıları. s. 9–. ISBN 978-1-59829-924-3.
^ Gondran, Michel; Minoux Michel (2008). Grafikler, Dioidler ve Yarı Halkalar: Yeni Modeller ve Algoritmalar. Springer Science & Business Media. Bölüm 4. ISBN 978-0-387-75450-5.
^ Pouly, Marc; Kohlas, Jürg (2011). Genel Çıkarım: Otomatikleştirilmiş Akıl Yürütme İçin Birleştirici Bir Teori. John Wiley & Sons. Bölüm 6. Yol Problemleri için Değerleme Cebirleri. ISBN 978-1-118-01086-0.
^ Loui, R.P., 1983. Stokastik veya çok boyutlu ağırlıklara sahip grafiklerde optimum yollar. ACM'nin İletişimi, 26 (9), s.670-676.
^ Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Baskın olmayan sıralama genetik algoritması kullanarak stokastik zamana bağlı yol ağlarında çok amaçlı yol bulma". Uygulamalarla uzmanlık sistmeleri. 42 (12): 5056–5064. doi:10.1016 / j.eswa.2015.02.046.
^ Olya, Mohammad Hessam (2014). "Birleşik üstel - gama olasılık dağılım yay uzunluğunda en kısa yolu bulma". Uluslararası Yöneylem Araştırması Dergisi. 21 (1): 25–37. doi:10.1504 / IJOR.2014.064020.
^ Olya, Mohammad Hessam (2014). "Dijkstra algoritmasının normal olasılık dağılımlı yay uzunluğu ile genel en kısa yol problemi için uygulanması". Uluslararası Yöneylem Araştırması Dergisi. 21 (2): 143–154. doi:10.1504 / IJOR.2014.064541.

Kaynakça

Ahuja, Ravindra K .; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (Nisan 1990). "En kısa yol problemi için daha hızlı algoritmalar". ACM Dergisi. ACM. 37 (2): 213–223. doi:10.1145/77600.77615. hdl:1721.1/47994. S2CID 5499589.
Bellman, Richard (1958). "Bir yönlendirme probleminde". Üç Aylık Uygulamalı Matematik. 16: 87–90. doi:10.1090 / qam / 102435. BAY 0102435.
Cherkassky, Boris V .; Goldberg, Andrew V.; Radzik, Tomasz (1996). "En kısa yol algoritmaları: teori ve deneysel değerlendirme". Matematiksel Programlama. Ser. A. 73 (2): 129–174. doi:10.1016/0025-5610(95)00021-6. BAY 1392160.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Tek Kaynaklı En Kısa Yollar ve Tüm Çiftler En Kısa Yollar". Algoritmalara Giriş (2. baskı). MIT Press ve McGraw-Hill. s. 580–642. ISBN 0-262-03293-7.
Dantzig, G. B. (Ocak 1960). "Bir Ağ Üzerindeki En Kısa Rotada". Yönetim Bilimi. 6 (2): 187–190. doi:10.1287 / mnsc.6.2.187.
Derniame, Jean Claude; Çift, Claude (1971), Problèmes de cheminement dans les graphes (Grafiklerdeki Yol Problemleri), Dunod (Paris)
Dijkstra, E.W. (1959). "Grafiklerle bağlantılı iki problem üzerine bir not". Numerische Mathematik. 1: 269–271. doi:10.1007 / BF01386390. S2CID 123284777.
Ford, L.R. (1956). "Ağ Akış Teorisi". Rand Corporation. P-923. Alıntı dergisi gerektirir | günlük = (Yardım)
Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacci yığınları ve gelişmiş ağ optimizasyon algoritmalarındaki kullanımları. 25. Yıllık Bilgisayar Biliminin Temelleri Sempozyumu. IEEE. s. 338–346. doi:10.1109 / SFCS.1984.715934. ISBN 0-8186-0591-X.
Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci yığınları ve bunların geliştirilmiş ağ optimizasyon algoritmalarında kullanımı". Bilgisayar Makineleri Derneği Dergisi. 34 (3): 596–615. doi:10.1145/28869.28874. S2CID 7904683.
Gabow, H.N. (1983). "Ağ sorunları için ölçeklendirme algoritmaları". 24.Yıllık Bilgisayar Biliminin Temelleri Sempozyumu Bildirileri (FOCS 1983) (PDF). sayfa 248–258. doi:10.1109 / SFCS.1983.68.
Gabow, Harold N. (1985). "Ağ sorunları için ölçeklendirme algoritmaları". Bilgisayar ve Sistem Bilimleri Dergisi. 31 (2): 148–168. doi:10.1016 / 0022-0000 (85) 90039-X. BAY 0828519.
Hagerup, Torben (2000). Montanari, Ugo; Rolim, José D. P .; Welzl, Emo (editörler). Word RAM'de Geliştirilmiş En Kısa Yollar. 27. Uluslararası Otomata, Diller ve Programlama Kolokyumu Bildirileri. sayfa 61–72. ISBN 978-3-540-67715-4.
Johnson, Donald B. (1977). "Seyrek ağlarda en kısa yollar için verimli algoritmalar". ACM Dergisi. 24 (1): 1–13. doi:10.1145/321992.321993. S2CID 207678246.
Johnson, Donald B. (Aralık 1981). "Başlatma ve kuyruk işlemlerinin gerçekleştirildiği öncelikli bir kuyruk $Ö (günlük günlüğü D)$ zaman". Matematiksel Sistemler Teorisi. 15 (1): 295–309. doi:10.1007 / BF01786986. BAY 0683047. S2CID 35703411.
Karlsson, Rolf G .; Poblete, Patricio V. (1983). "Bir $Ö (m günlük günlüğü D)$ en kısa yollar için algoritma ". Ayrık Uygulamalı Matematik. 6 (1): 91–93. doi:10.1016 / 0166-218X (83) 90104-X. BAY 0700028.
Leyzorek, M .; Gray, R. S .; Johnson, A. A .; Ladew, W. C .; Meaker, S.R., Jr.; Petry, R. M .; Seitz, R.N. (1957). Model Tekniklerinin İncelenmesi - İlk Yıllık Rapor - 6 Haziran 1956 - 1 Temmuz 1957 - Haberleşme Sistemleri için Model Teknikler Üzerine Bir Çalışma. Cleveland, Ohio: Case Institute of Technology.
Moore, E.F. (1959). "Bir labirentteki en kısa yol". Uluslararası Geçiş Teorisi Sempozyumu Bildirileri (Cambridge, Massachusetts, 2-5 Nisan 1957). Cambridge: Harvard Üniversitesi Yayınları. s. 285–292.
Pettie, Seth; Ramachandran, Vijaya (2002). Karşılaştırmalar ve eklemelerle en kısa yolları hesaplama. Ayrık Algoritmalar On Üçüncü Yıllık ACM-SIAM Sempozyumu Bildirileri. pp.267–276. ISBN 978-0-89871-513-2.
Pettie Seth (26 Ocak 2004). "Gerçek ağırlıklı grafiklerde tüm çiftler için en kısa yollara yeni bir yaklaşım". Teorik Bilgisayar Bilimleri. 312 (1): 47–74. doi:10.1016 / s0304-3975 (03) 00402-x.
Pollack, Maurice; Wiebenson, Walter (Mart-Nisan 1960). "En Kısa Rota Probleminin Çözümü - Bir Gözden Geçirme". Oper. Res. 8 (2): 224–230. doi:10.1287 / opre.8.2.224. Dijkstra'nın algoritmasını Minty'ye ("özel iletişim") s. 225.
Schrijver, Alexander (2004). Kombinatoryal Optimizasyon - Polyhedra ve Verimlilik. Algoritmalar ve Kombinatorikler. 24. Springer. ISBN 978-3-540-20456-5. Burada: cilt A, bölüm 7.5b, s. 103
Shimbel, Alfonso (1953). "İletişim ağlarının yapısal parametreleri". Matematiksel Biyofizik Bülteni. 15 (4): 501–507. doi:10.1007 / BF02476438.
Shimbel, A. (1955). İletişim ağlarında yapı. Bilgi Ağları Sempozyumu Bildirileri. New York, NY: Polytechnic Institute of Brooklyn Polytechnic Press. s. 199–203.
Thorup, Mikkel (1999). "Doğrusal zamanda pozitif tamsayı ağırlıkları ile yönlendirilmemiş tek kaynaklı en kısa yollar". ACM Dergisi. 46 (3): 362–394. doi:10.1145/316542.316548. S2CID 207654795.
Thorup, Mikkel (2004). "Sabit zamanda azaltma anahtarlı tamsayı öncelikli kuyruklar ve tek kaynaklı en kısa yollar sorunu". Bilgisayar ve Sistem Bilimleri Dergisi. 69 (3): 330–353. doi:10.1016 / j.jcss.2004.04.003.
Mezgit, P. D .; Hillier, J. A. (Mart-Haziran 1960). "Bir Yol Ağı Üzerinden En Kısa Rotayı Bulmak İçin Bir Yöntem". Üç Aylık Yöneylem Araştırması. 11 (1/2): 37–40. doi:10.1057 / jors.1960.32.
Williams, Ryan (2014). "Devre karmaşıklığı yoluyla daha hızlı tüm çiftler en kısa yollar". Bilgi İşlem Teorisi üzerine 46. Yıllık ACM Sempozyumu Bildirileri (STOC '14). New York: ACM. s. 664–673. arXiv:1312.6680. doi:10.1145/2591796.2591811. BAY 3238994.

daha fazla okuma

Frigioni, D .; Marchetti-Spaccamela, A .; Nanni, U. (1998). "Tamamen dinamik çıktı sınırlı tek kaynak en kısa yol problemi". Proc. 7. Annu. ACM-SIAM Symp. Ayrık Algoritmalar. Atlanta, GA. s. 212–221. CiteSeerX 10.1.1.32.9856.
Dreyfus, S. E. (Ekim 1967). Bazı En Kısa Yol Algoritmalarının Değerlendirilmesi (PDF) (Bildiri). Proje Rand. Birleşik Devletler Hava Kuvvetleri. RM-5433-PR. DTIC AD-661265.

[1] Cormen vd. 2001, s. 655

[dial69-2] Kadran, Robert B. (1969), "Algorithm 360: Topolojik Sıralama [H] ile En Kısa Yol Ormanı", ACM'nin iletişimi, 12 (11): 632–633, doi:10.1145/363269.363610

[3] Sanders, Peter (23 Mart 2009). "Hızlı rota planlama". Google Tech Talk. Alıntı dergisi gerektirir | günlük = (Yardım)

[4] Chen, Danny Z. (Aralık 1996). "Geometrik yol planlama problemleri için algoritma ve yazılım geliştirme". ACM Hesaplama Anketleri. 28 (4es). Madde 18 doi:10.1145/242224.242246. S2CID 11761485.

[5] Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. "Karayolu Boyutu, En Kısa Yollar ve Yeterli Verimli Algoritmalar". Ayrık Algoritmalar hakkında ACM-SIAM Sempozyumu, sayfalar 782–793, 2010.

[6] Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf "Yol Ağlarında En Kısa Yollar için Merkez Tabanlı Bir Etiketleme Algoritması". Deneysel Algoritmalar Sempozyumu, sayfalar 230–241, 2011.

[7] Kroger, Martin (2005). "İki ve üç boyutlu polimerik sistemlerde dolanma analizi için en kısa çoklu bağlantısız yol". Bilgisayar Fiziği İletişimi. 168 (3): 209–232. Bibcode:2005CoPhC.168..209K. doi:10.1016 / j.cpc.2005.01.020.

[8] Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Ağ Akışları: Teori, Algoritmalar ve Uygulamalar. Prentice Hall. ISBN 978-0-13-617549-0.

[Pair1966-9] Pair, Claude (1967), Rosentiehl (ed.), "Sur des algoritthmes pour des problèmes de cheminement dans les graphes finis (On algoritmalar on sonlu graphs in path problem for)", Théorie des graphes (journées internationales d'études) - Theory of Graphs (uluslararası sempozyum), Roma (İtalya), Temmuz 1966: Dunod (Paris) et Gordon and Breach (New York), s. 271CS1 Maint: konum (bağlantı)

[10] Derniame, Jean Claude; Çift, Claude (1971), Problèmes de cheminement dans les graphes (Grafiklerdeki Yol Problemleri), Dunod (Paris)

[BarasTheodorakopoulos2010-11] Baras, John; Theodorakopoulos, George (4 Nisan 2010). Ağlarda Yol Problemleri. Morgan & Claypool Yayıncıları. s. 9–. ISBN 978-1-59829-924-3.

[GondranMinoux2008-12] Gondran, Michel; Minoux Michel (2008). Grafikler, Dioidler ve Yarı Halkalar: Yeni Modeller ve Algoritmalar. Springer Science & Business Media. Bölüm 4. ISBN 978-0-387-75450-5.

[PoulyKohlas2012-13] Pouly, Marc; Kohlas, Jürg (2011). Genel Çıkarım: Otomatikleştirilmiş Akıl Yürütme İçin Birleştirici Bir Teori. John Wiley & Sons. Bölüm 6. Yol Problemleri için Değerleme Cebirleri. ISBN 978-1-118-01086-0.

[14] Loui, R.P., 1983. Stokastik veya çok boyutlu ağırlıklara sahip grafiklerde optimum yollar. ACM'nin İletişimi, 26 (9), s.670-676.

[15] Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Baskın olmayan sıralama genetik algoritması kullanarak stokastik zamana bağlı yol ağlarında çok amaçlı yol bulma". Uygulamalarla uzmanlık sistmeleri. 42 (12): 5056–5064. doi:10.1016 / j.eswa.2015.02.046.

[16] Olya, Mohammad Hessam (2014). "Birleşik üstel - gama olasılık dağılım yay uzunluğunda en kısa yolu bulma". Uluslararası Yöneylem Araştırması Dergisi. 21 (1): 25–37. doi:10.1504 / IJOR.2014.064020.

[17] Olya, Mohammad Hessam (2014). "Dijkstra algoritmasının normal olasılık dağılımlı yay uzunluğu ile genel en kısa yol problemi için uygulanması". Uluslararası Yöneylem Araştırması Dergisi. 21 (2): 143–154. doi:10.1504 / IJOR.2014.064541.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]