Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 19. 01. 2016 17:17 — Editoval biggest-matematik (19. 01. 2016 17:19)
- biggest-matematik
- Příspěvky: 45
- Reputace: 0
Výsledek Floyd-Warshallova Algoritmu
Umím spočítat výsledek tohoto alg, ale nevím/nepochopil jsem jak mám z toho vyčíst co je ta nejlevnější cesta apod.?
Výsledek:
(V1, V2, V3, V4) Vn=Vrchol
0 3 4 1
5 0 1 6
4 7 0 5
7 2 3 0
když se chci dostat třeba z V1 do V4, jak postupuju při čtení toho výsledku?
Jeste poddotaz: dá se Floydův nebo Dijsktrův Alg použít na zjištení souvislosti grafu nebo/a na zjistení poctu komponentů grafu?
Dík
Offline
#2 19. 01. 2016 18:24
Re: Výsledek Floyd-Warshallova Algoritmu
Floyd-Warshall ti nedá nejkratší cestu, ale pouze délku nejkratší cesty. Pokud bys chtěl nějakou tu cestu rekonstruovat, budeš si muset pamatovat nějaká data navíc.
Z té matice
V1 V2 V3 V4
V1 0 3 4 1
V2 5 0 1 6
V3 4 7 0 5
V4 7 2 3 0
zjistíš, že nejkratší orientovaná cesta z V1 do V4 má délku 1, a nejkratší cesta z V4 do V1 má délku 7. Více třeba zde nebo na Wikipedii.
Příspěvky psané červenou barvou jsou moderátorské, šedá je offtopic.
Offline
#3 19. 01. 2016 18:55
Re: Výsledek Floyd-Warshallova Algoritmu
K poddotazu, když by v matici, kterou Floyd vyplivne, bylo 
, pak je zřejmé, že 
a 
nejsou spojeny žádnou cestou, tj. musí ležet v různých komponentách, obdobně u Dijkstra. Ale přijde mi to zbytečné, protože na zjištění počtu komponent ti stačí jenom pustit prohledávání do hloubky.
Příspěvky psané červenou barvou jsou moderátorské, šedá je offtopic.
Offline