#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