grafy ważone

Gdy mówimy o grafach i rozwiązywaniu problemów za ich pomocą, w kontekście algorytmiki pierwszą rzeczą, która wielu przychodzi na myśl, jest wyszukiwanie najkrótszych ścieżek. Co prawda omówiliśmy już to dla grafów nieważonych, ale powiedzmy sobie szczerze — zwykle musimy to robić w ważonych. Opiszę tutaj trzy klasyczne algorytmy rozwiązujące ten problem.

Grafy to jedna z najważniejszych koncepcji matematycznych, które na stałe weszły do świata informatyki. Wielu programistów może nie dostrzegać tego na pierwszy rzut oka, ale znajdziemy je niemal wszędzie. Warto wiedzieć, czym one są i jak działają, niezależnie od tego, czym w świecie IT się zajmujemy. Jest to też temat dość mi bliski, bo zawodowo mam do czynienia z praktycznym zastosowaniem grafów od dłuższego czasu. W tym wpisie opisuję je od strony teoretycznej, aby przedstawić, czym są, skąd się wzięły i przede wszystkim, jakie znalazły zastosowania. Na początku nie przedstawię całej teorii grafów, tylko moim zdaniem jej najważniejsze elementy.