Diskuse:Dijkstrův algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Nejspíš je zde malá nesrovnalost v písmenkách v Pseudokódu oproti Popis algoritmu.

Podle následujícího řádku usuzuji, že E je množina obsahující HRANY.

Řekněme, že V je množina všech vrcholů grafu G a množina E obsahuje všechny hrany grafu G.

Avšak v pseudokódu je řádek

6     N := E                            // Všechny dosud nenavštívené vrcholy

Z čehož chápu že by měl obsahovat VRCHOLY. Tudíž správně by to asi mělo být takto (G místo E).

6     N := G                            // Všechny dosud nenavštívené vrcholy

Také by nemuselo být špatné zmínit (i když to z tohoto řádku vyplývá), že i počáteční vrchol (např. s) je zpracováván tímto alg. A protože má d[s]=0 je prvním vybraným. Ale to už jen tak jako zjednodušení pro pochopení.

Queria 11:08, 10. 12. 2007 (UTC)

Editujte s odvahou! Honza Záruba 11:10, 10. 12. 2007 (UTC)

Dovolím si jen trochu zašťourat, v odstavci Pseudokód je na konci zmíněna "relaxační" podmínka, míněno bylo patrně "relační". Ale relaxaci se asi nikdo nebrání :-) -- Tento nepodepsaný komentář přidal(a) uživatel(ka) 194.228.23.10 (diskuse)

Editujte s odvahou. --Postrach 11:46, 25. 1. 2008 (UTC)
Pokud si někdo není úpravou jistý, tak dobře, že needituje! Stačí rychlé mrknutí do anglické wiki a zjistíte, že se opravdu proces jmenuje relaxace - jde o náhradu delší cesty nějakou kratší. --Zbytovsky 29. 5. 2010, 19:37 (UTC)

Komentář pseudokódu není pravdivý[editovat zdroj]

Řádek 10 pseudokódu momentálně říká:

   10             alt = d[u] + l(u, v)           // pozor v 1. smyčce cyklu - d[u] je ještě nekonečno

to ale není pravda, protože při prvním průchodu tělem cyklu while je za u vždy vybrán počáteční uzel s, takže d[u] = d[s] = 0.

Děkujeme Vám, že se snažíte Wikipedii pomoci. Pokud máte dojem, že článek je potřeba vylepšit, nebojte se učinit v něm libovolné změny, které považujete za vhodné. Nováčci jsou vždy vítáni! --Mormegil 6. 5. 2011, 21:56 (UTC)
Upravil jsem to. Snad je to teď správné a jasné. Zagothal 16. 5. 2011, 07:53 (UTC)

Odkud měříme vzdálenost?[editovat zdroj]

"že si pro každý vrchol v z V pamatuje délku nejkratší cesty, kterou se k němu dá dostat." - není zde jasně řečeno, odkud se ona cesta měří. O kus dále je sice zmíněn vrchol s, ale to už může být zvídavý čtenář zmaten. 94.112.227.38 25. 4. 2013, 20:20 (UTC)

Vzdálenost nenavštívených uzlů[editovat zdroj]

V popisu algoritmu se uvádí "takový, který má nejmenší hodnotu d [v] ze všech vrcholů v z N." Pokud N obsahuje nenavštívené uzly, odkud je známa jejich vzdálenost? 160.216.17.159 9. 10. 2019, 11:23 (CEST)

Na začátku mají všechny vrcholy hodnotu , kromě počátečního vrcholu , který má . Nekonečno symbolizuje, že neznáme cestu k vrcholu.

--Mormegil 9. 10. 2019, 17:37 (CEST)