Cvičení 10 - Problém obchodního cestujícího, generování permutací

• Prostudujte si ukázkovou implementaci neorientovaného váženého grafu a funkci, která generuje permutace.
• Jedná se o modifikovanou verzi neorientovaného grafu z šestého cvičení.
• Váhy reprezentují vzdálenost mezi dvojicemi vrcholů.
• Jelikož se jedná o vážený graf, v matici sousednosti nebudou uloženy pouze jedničky a nuly, nýbrž nezáporná celá čísla.
• Pokud hrana mezi vrcholy neexistuje, na příslušných indexech je v matici uložena nula.
• V případě, že hrana existuje, je na příslušných indexech v matici sousednosti uloženo přirozené číslo reprezentující váhu hrany.
• Ve vstupních souborech musí být u každé hrany na řádku navíc třetí číslo reprezentující váhu hrany.
• Budeme hledat nejkratší cestu procházející všemi vrcholy kompletního grafu začínající a končící ve stejném vrcholu.
• Budeme hledat řešení hrubou silou, tj. vygenerujeme všechny možné cesty a z nich vybereme tu nejkratší.
• Implementujte funkci GenerateAllPaths, která vygeneruje všechny možné cesty přes všechny vrcholy, počínaje a konče jedním pevně daným vrcholem jehož číslo je předáno do funkce jako parametr.
• Využijte funkci pro generování permutací pro vygenerování permutací všech vrcholů, a vyberte z nich právě ty permutace, které začínají požadovaným vrcholem.
• Cesta začíná a končí stejným vrcholem, bude tedy potřeba na konec vygenerované permutace přidat počáteční vrchol.
• Cesty uložte do proměnné possiblePaths.
• Implementujte funkci PrintShortestPath, nalezne nejkratší cestu přes všechny vrcholy.
• Funkci předáte číslo počátečního vrcholu, vygenerujete všechny možné cesty začínající a končící v daném vrcholu funkcí GenerateAllPaths, a následně spočítáte jejich délku.
• Vyberte z cest tu nejkratší a na standardní výstup ji vypište včetně její délky.