Zastanów się, na podstawie czego podejmiesz decyzję, jaką drogą dojść na miejsce spotkania z kolegą lub koleżanką, czy do kina. Być może jednym z kryteriów będzie to, by odcinek do przejścia był jak najkrótszy. O ile łatwo zaplanować taką drogę, gdy odległość jest niewielka, o tyle sytuacja się komplikuje, gdy w taki sposób zaplanować masz podróż z miasta do miasta.

Problem, który się pojawia, w algorytmice znany jest jako problem szukania najkrótszej ścieżki. Należy do jednych z najbardziej znanych problemów grafowych. Istnieje konkretny algorytm, który może zostać wykorzystany do jego rozwiązania. Omawiamy go w tym e‑materiale: jest to algorytm Dijkstry.

W tym rozdziale przyjrzymy się, jak działa mechanizm wyszukiwania najkrótszej ścieżki, dlaczego jego pomysłowość przetrwała dekady oraz jak wykorzystuje go współczesna technologia - od nawigacji GPS po optymalizację sieci komputerowych. Zrozumienie jego działania otworzy ci drogę do bardziej zaawansowanych zagadnień algorytmicznych i pokaże, jak teoria grafów realnie wspiera technologie, z których korzystasz na co dzień.

Ćwiczenie na rozgrzewkę