D IJKSTR UV ALGORITMUS ˚
Animace N´apovˇeda O projektuv1
v2
v3
v4
v5
v6
v7
v8
v9
v10
5
1
2
1 5
3 4 6
1 5
6 2
1 1
1 2
3
I
Mˇejme graf
Gna 10 vrcholech.
N ´ APOV EDA ˇ
Animace N´apovˇeda O projektuAnimace slouˇz´ı jako ilustrace l´atky kapitoly4.4modulu ´Uvod do teorie graf ˚u.
Dijkstr ˚uv algoritmus
Dijkstr ˚uv algoritmus se pouˇz´ıv´a pro hled´an´ı nejkratˇs´ı cesty mezi vrcholy kladnˇe ohodnocen´eho grafu.
1. Je variantou proch´azen´ı grafu do ˇs´ıˇrky (pro kaˇzd´y nalezen´y vrcholvm´ame promˇennou ud´avaj´ıc´ı vzd´alenost - d´elku nejkratˇs´ıho sleduuvdo v´ychoz´ıho vrcholuu).
2. Z ´uschovy nalezen´ych vrchol ˚u vˇzdy vyb´ır´ame ten vrcholvs nejmenˇs´ı vzd´alenost´ı odu(kratˇs´ı cesta dovneexistuje).
3. Na konci zpracov´an´ı dostaneme vektor promˇenn´ych, kter´y ud´av´a nejkratˇs´ı vzd´alenost z poˇc´ateˇcn´ıho vrcholu do vˇsech ostatn´ıch vrchol ˚u.
I Vstup: GrafGnanvrcholech (zadan´y napˇr. seznamem soused ˚u, vizReprezentace grafu v poˇc´ıtaˇci), vrcholu, ze kter´eho hled´ame vzd´alenosti do vˇsech ostatn´ıch vrchol ˚u.
I V´ystup: Vektor vzd´alenost´ı z vrcholuudo vˇsech vrchol ˚u.
Dijkstr ˚uv algoritmus je pops´an v kapitole4.4modulu ´Uvod do teorie graf ˚u a na konkr´etn´ım pˇr´ıkladˇe zn´azornˇen ve vlastn´ı animaci. Kroky algoritmu jsou zapisov´any do tabulky.
O PROJEKTU Animace N´apovˇeda O projektu
Matematika pro inˇzen´yry 21. stolet´ı– inovace v´yuky matematiky na technick´ych ˇskol´ach v nov´ych podm´ın- k´ach rychle se vyv´ıjej´ıc´ı informaˇcn´ı a technick´e spoleˇcnosti
Doba realizace: 1.9.2009 – 30.8.2012 Pˇr´ıjemce: VˇSB - TU Ostrava Partner projektu: Z ˇCU v Plzni
C´ılem projektuje inovace matematick´ych a nˇekter´ych odborn´ych kurz ˚u na technick´ych VˇS s c´ılem z´ıskat z´ajem student ˚u, zv´yˇsit efektivnost v´yuky, zpˇr´ıstupnit prakticky aplikovateln´e v´ysledky modern´ı matematiky a vytvoˇrit pˇredpoklady pro efektivn´ı v´yuku inˇzen´yrsk´ych pˇredmˇet ˚u.
Zkvalitnˇen´ı v´yuky matematiky budouc´ıch inˇzen´yr ˚u chceme dos´ahnout po str´ance form´aln´ı vyuˇzit´ım nov´ych informaˇcn´ıch technologi´ı pˇr´ıpravy elektronick´ych studijn´ıch materi´al ˚u a po str´ance vˇecn´e peˇcliv´ym v´ybˇerem vyuˇcovan´e l´atky s d ˚usledn´ym vyuˇz´ıv´an´ım zaveden´ych pojm ˚u v cel´em kurzu matematiky s promyˇslenou integrac´ı modern´ıho matematick´eho apar´atu do vybran´ych inˇzen´yrsk´ych pˇredmˇet ˚u.
Metodiku v´yuky matematiky a jej´ı atraktivnost pro studenty chceme zlepˇsit d ˚urazem na motivaci a d ˚usled- n´ym pouˇz´ıv´an´ım postupu ”od probl´emu k ˇreˇsen´ı“.
