Grafy: nejkratší cesty

Jednou z typických úloh na grafech je hledání cest mezi vrcholy. Pokud chceme v mapě najít co nekratší cestu z jednoho místa do jiného, můžeme mapu převést na graf, v němž budeme hledat nejkratší cestu po hranách. V takové situaci se často hodí k hranám (cestám mezi místy) doplnit údaje o jejich délce.

Z tohoto grafu bychom například zjistili, že nejkratší cesta z Rejšic do Jabkenic má 3 kilometry a vede přes Charvatce.

Cesty je možné kromě prostorové vzdálenosti porovnávat i podle jiných kritérií:

• Když internetový poskytovatel zajišťuje propojení svých sítí, může případná spojení porovnávat podle ceny za jejich pronájem.
• Navigace neporovnává cesty jen podle délky, ale i podle času dojezdu. Cesta po dálnici pravděpodobně bude o mnoho rychlejší, než stejně dlouhá cesta po okresní silnici.