From ec07b19bea43ef2875a077d0c4abbff3766eece8 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 30 Jan 2011 23:26:07 +0100 Subject: [PATCH] APSP: Jeste par drobnych uprav --- 14-floyd/14-floyd.tex | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/14-floyd/14-floyd.tex b/14-floyd/14-floyd.tex index 9560c54..8703134 100644 --- a/14-floyd/14-floyd.tex +++ b/14-floyd/14-floyd.tex @@ -14,10 +14,12 @@ To je pro pomalej¹í, ne¾ je velikost výstupu. Je-li graf hustý pracují obvykle rychleji algoritmy zalo¾ené na maticích, zejména -na jejich násobení. Nìkolik algoritmù tohoto druhu si nyní pøedvedeme. Graf budeme -v¾dy popisovat maticí délek hran -- to je matice $n\times n$, její¾ øádky i sloupce -jsou indexované vrcholy a na pozici $(i,j)$ se nachází délka hrany $ij$; pøípadné -chybìjící hrany doplníme s~délkou~$+\infty$. +na jejich násobení. Nìkolik algoritmù tohoto druhu si nyní pøedvedeme, +a to jak pro výpoèet vzdáleností, tak pro dosa¾itelnost (transitivní uzávìr). + +Graf na vstupu bude v¾dy zadán maticí délek hran -- to je matice $n\times n$, +její¾ øádky i sloupce jsou indexované vrcholy a na pozici $(i,j)$ se nachází +délka hrany $ij$; pøípadné chybìjící hrany doplníme s~délkou~$+\infty$. \h{Floydùv-Warshallùv algoritmus} -- 2.39.5