#2 21. 06. 2010 15:25
Re: Matice vzdálenosti z grafu
↑ Benny.RxT:Podle toho, co je vrchol a co jen křížení, bude matice řádu 7 nebo 6.
V i-tém řádku a j-tém slouci bude vzdálenost mezi vrcholy i a j.
Jak se najde? Graf je malý, tak ručně. Pro obecný graf například opakování Dijkstrova algoritmu.
Offline
#3 21. 06. 2010 15:39
Re: Matice vzdálenosti z grafu
↑ petrkovar:
Vrcholů je 7, takže si je označím od (a) do (g), ale jak pak budu určovat vzdálenost mezi
např. vrcholem (a) a (b), když hodnoty hran nejsou zadaný?
Nebo bude jen psát nejkratší počet cest z jednoho vrcholu do druhýho?
Offline
#4 21. 06. 2010 15:48
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Matice vzdálenosti z grafu
↑ Benny.RxT: Když hodnoty nejsou zadané, měly by být všechny 1. Odpověď na 2. otázku je pak ano.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#5 21. 06. 2010 16:33
Re: Matice vzdálenosti z grafu
Přiřadím každé hraně hodnotu 1 a vypočítám matici vzdálenosti:
(značení začíná u vrcholu co je nejvíc vlevo (a) a proti směru HR)
a b c d e f g
a 0 1 2 3 4 3 1
b 1 0 1 2 3 2 1
c 2 1 0 1 2 1 1
d 3 2 1 0 1 1 2
e 4 3 2 1 0 1 3
f 3 2 1 1 1 0 2
g 1 1 1 2 3 2 0
Když bych měl použít Dijkstrův algoritmus, tak bych ho musel použít na
každou pozici v matici. Takže např. pro nejkratší cestu z (a) do (e):
a b g c f d e
0 inf inf inf inf inf inf 0(a)
0 1 1 inf inf inf inf 1(b)
0 1 1 2 inf inf inf 1(g)
0 1 1 2 inf inf inf 2(c)
0 1 1 2 3 3 inf 3(f)
0 1 1 2 3 3 4 3(d)
0 1 1 2 3 3 4 4(e)
Vidím že nejkratší cesta z (a) do (e) má vzdálenost 4.
Je to takhle správně?
Offline