Nakon guglanja o tome kaže li se putovi ili putevi, još uvijek nisam siguran što je ovdje ispravno. Kažu da su putovi konkretni, a putevi apstraktni. Za putove u našem smislu, tj. u smislu teorije grafova, može se reći i jedno i drugo. Sigurno su apstraktniji od šumskih putova, ali i konkretniji od, recimo, puteva mudrosti. Odlučio sam se za “konkretnu” varijantu: putovi. (Za one koji se zgražaju nad ovim jezičnim pseudoproblemima: nevažno je, naravno, ali je zabavno, i stvar estetike – shvatite to kao formatiranje teksta.) Dakle: putovi.

Floyd-Warshallov algoritam jedan je od najljepših algoritama koje znam jer u svojih samo 5-6 redaka koda krije mnogo mudrosti (puteva mudrosti, jel). Kao što učinak samog algoritma nije nimalo očit, tako možda nije očito ni da se algoritam može jednostavno nadopuniti tako da izračuna i koliko ima najkraćih putova između svakih dvaju vrhova.

Probajte to sami smisliti. Nije teško, ali je malo tricky. Recimo, prvi odgovor (označen zelenom kvačicom) na Stack Overflowu nije ispravan. Točno rješenje dano je u odgovoru ispod njega (kod počinje s procedure FloydWarshallWithCount ()).

Naravno, mana Floyd-Warshalla je složenost od i zato, osim za guste grafove, prednost ipak ima Dijkstrin algoritam koji se također može nadopuniti tako da računa i broj najkraćih putova.

Evo zadatka gdje to možete isprobati: Šetnja2 (IBT 2010.).

Korišteni bridovi koji se nalaze na najkraćim putovima iz nekog fiksnog vrha čine tzv. Dijkstrin DAG. (Ako su najkraći putovi jedinstveni, riječ je o stablu.) On ima glavnu ulogu u zadatku Najkraći (zadatak dana!) s HONI-ja 2008. (Ako vam je dosad promaklo, rješenja svih HONI-ja možete pronaći ovdje.) Update: još dva zadatka predložio je Marin u komentaru dolje.