Cvičení 6

Úloha 6.1

Pro graf na obr. 1 nalezněte vzdálenosti do všech uzlů z uzlu u Dijkstrovým algoritmem.

Obrázek 1: Zadaný graf

Úloha 6.2

Pro graf na snímku č. 3 prezentace z přednášky sestavte matici sousednosti a zjistěte, kolik existuje sledů délky 2 a 3. Sestavte matici vzdáleností.

Úloha 6.3

Napište program, který načte ze souboru matici sousednosti, vypíše, zda je či není symetrická a vypočítá mocniny matice sousednosti A^k, k = 2,...,n-1, kde n je počet uzlů grafu. Nakonec vypíše matici vzdáleností. Program se dotáže na název souboru s maticí. Soubor je textový a má definovanou strukturu: první řádek souboru obsahuje počet uzlů grafu, na dalších řádcích následuje vlastní matice sousednosti. Pro matice alokujte dynamicky dvourozměrné pole podle počtu uzlů grafu. Napište samostatnou funkci pro test symetričnosti a samostatnou proceduru pro násobení matic; procedura bude mít čtyři parametry: ukaztele na dvě vstupní matici a na výslednou (výstupní) matici a rozměr matice.

Řešení:

Dev C++:	vzdal.dev, vzdal.c
CodeBlocks:	vzdal.cbp, vzdal.c
Soubor s maticí sousednosti (z předchozí úlohy):	graf.txt