Asi to jde udělat jinak i lépe, četl jsem o postupu kdy se to zvládne pouze během jednoho průchodu DFS, ale úplně mi to nešlo do hlavy, tak prezentuju svoje řešení, je to také 10/10:

Nejdříve zjištění, jestli automat přijímá FINITE nebo INFINITE jazyk

• DFS z počátečního stavu (explicitní zásobník a while smyčka)
• Pokud narazím na cyklus, zapíšu si u všech stavů v tom cyklu, že jsou součástí cyklu (pro připomenutí - stavy cyklu se nachází na zásobníku v části odshora až do výskytu toho stavu, na který jsme narazili a je OPEN)
• Pokud narazím na konečný stav:
  • ke všem stavům na zásobníku zapíšu, že vedou do konečného stavu (pozor - když narazím na stav, který již vede do konečného, přestanu se zapisováním, protože všechny stavy předtím to mají již nastavené někdy odminula)
• pokud je aktuální stav součástí cyklu a zároveň vede do konečného stavu, přeruším DFS a jdu hledat nejkratší slovo, protože mám INFINITE jazyk
• pokud DFS doběhne bez přerušení, mám FINITE jazyk a jdu hledat nejkratší slovo

Nejkratší slovo (INFINITE jazyk):

• BFS z počátečního stavu
• U stavů si pamatuju, jakým terminálem jsem do nich přišel (a odkud) nebo jakým slovem se do nich dá dostat
• Když dojdu do konečného stavu, skončím (nemá smysl pokračovat a hledat cestu do dalších konečných stavů, protože do nich nutně vede delší cesta /slovo/ než do tohohle)

Nejdelší slovo (FINITE jazyk):

• DFS z počátečního stavu
• Nechodím do stavů, které jsou součástí cyklu
• U každého stavu si pamatuju příchozí vzdálenost od počátečního + to samé jako v INFINITE jazyku
• Do stavu jdu jen v tom případě, že bych mu zvětšil příchozí vzdálenost nebo pokud je stejná, tak terminál/slovo
• DFS nechám doběhnout celý, nijak nepřerušuju
  • po skončení vezmu slova vedoucí z finálových stavů (vedou do počátečního stavu) a vyberu nejdelší

Přidám testovací data, která mi pomohla odladit vytváření slov:

6 3 1

0 1 2 1 1 1 3

1 0 1 4 0

2 0 0 1 4

3 1 4 0 0

4 1 5 0 0

5 1 4 0 0

1 4

Výstup: INFINITE ac

10 2 1

0 2 2 3 1 1

1 1 4 0

2 1 5 0

3 0 1 6

4 0 1 7

5 0 1 7

6 1 7 0

7 0 1 8

8 1 9 0

9 0 1 8

3 1 3 7

Výstup: FINITE bab