sidus graaf. [2] o Teoreem. Kui sidusas graafis ei leidu ühtegi silda, siis saab graafi servadele määrata suunad nii, et tekkinud graaf on tugevalt sidus. o Tõestuse idee. Leiame graafis tsükli ja lisame sellele järk-järgult juurde ülejäänud tippe ühendavaid ahelaid. o Järeldus. Sildade olemasolu korral saame tugevalt sidusa graafi, kui sillad asendada kahe kaarega (mõlemas suunas). 53. Lühima tee leidmise ülesanne suunatud graafis. Floyd-Warshalli algoritm. [2] Lühima tee leidmise ülesanne suunatud graafis o Antud on suunatud graaf, mille igale kaarele on omistatud kaal (mittenegatiivne reaalarv). Leida kahe antud tipu vahel suunatud ahel, millesse kuuluvate servade kaalude summa on vähim võimalik. o Lahendusmeetod on dünaamiline planeerimine, kus lahend leitakse samm-sammult üha pikemaid ahelaid vaadeldes. o Floyd-Warshalli algoritm (1962). Floyd-Warshalli algoritm
Seega 1) kehtib pärast sammu + 1. Olgu nüüd tipp, mis on pärast etappi + 1 väljaspool hulka . Kui lühim ilma väljaspool olevate tippudeta tee tipust tippu ei sisalda viimati valitud tippu , siis tema pikkus on induktsiooni eelduse järgi [] . Kui sisaldab, siis tema pikkus on +1[] = [] + . Seega kehtib vastavalt väärtustamise eeskirjale ka 2) ja teoreem on tõestatud Lühima tee leidmine Floyd-Warshalli algoritmiga: o Olgu kaalutud suunatud graaf, mille tipud on nummerdatud naturaalarvudega 1, 2, ... , , kaalud 0 on kaarte pikkused o Moodustame kaks × -maatriksit ja o Maatriksi elemendid näitavad seni leitud lühima tee pikkust tipust tippu . Maatriksi elemendid näitavad lühima tee esimest vahetippu (kuhu tuleb tipust esimesena minna) o Algväärtused: = (või , kui kaart ei ole) =
O(n log n) Worst case time complexity of quicksort is Järjestamise kiirmeetodi halvima juhu ajaline keerukus on Vali üks: O (n2) Leaves of a tree are Puu lehed on nodes without children / alluvateta tipud Dijkstra algorithm on graphs is for finding Dijkstra algoritmiga arvutatakse graafis shortest paths from a given vertex to all reachable vertices antud tipust algavaid lühimaid teid kõigisse saavutatavatesse tippudesse Floyd-Warshall algorithm on graphs is for finding Floyd-Warshalli algoritmiga arvutatakse graafis lengths of shortest paths between all pairs of vertices lühimate teede pikkusi kõigi tipupaaride vahel Kruskal algorithm on graphs is for finding Kruskali algoritmiga arvutatakse graafis minimal spanning tree minimaalset toesepuud Prim algorithm on graphs is for finding Primi algoritmiga arvutatakse graafis minimal spanning tree minimaalset toesepuud Which algorithm uses cyclic hash functions for pattern matching
php?id=107318 lk 80. 51) a. Lühima tee leidmise ülesanne a.i. Antud on suunatud graaf, mille igale kaarele on omistatud kaal (mittenegatiivne reaalarv). a.ii. Leida kahe antud tipu vahel suunatud ahel, millesse kuuluvate servade kaalude summa on vähim võimalik. a.iii. Lahendusmeetod on dünaamiline planeerimine, kus lahend leitakse samm-sammult üha pikemaid ahelaid vaadeldes. b. Floyd-Warshalli algoritm. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 83 84. 52) a. **Floyd-Warshalli algoritmi keerukuse hinnang ja korrektsuse tõestus. https://moodle.ut.ee/mod/resource/view.php?id=114409 lk 24 26.
annaabi.ee 
