Viikon 11 aiheena on luentomateriaalin sivut 506–545. Viikon tavoitteena on oppia etsimään lyhin reitti painotetussa verkossa. Tätä varten materiaali esittelee kolme keskeistä algoritmia:
Bellman-Fordin algoritmi laskee lyhimmät reitit aloitussolmusta kaikkiin muihin solmuihin.
Algoritmi on melko hidas (O(nm)), jossa n on solmujen määrä ja m on kaarten määrä, koska se suorittaa n kierrosta ja yrittää joka kierroksella lyhentää kunkin kaaren kautta kulkevaa reittiä.
Algoritmi on kuitenkin suoraviivainen toteuttaa ja toimii millä tahansa verkolla.
Dijkstran algoritmin käyttötarkoitus on sama kuin Bellman-Fordin algoritmilla. Siinä on kuitenkin kaksi eroa:
Dijkstran algoritmi on myös vaikeampi toteuttaa, koska siinä täytyy käyttää kekoa tai vastaavaa tietorakennetta. Parempi aikavaativuus on kuitenkin merkittävä palkkio vaivasta.
Floyd-Warshallin algoritmi lähestyy ongelmaa eri suunnasta ja selvittää yhdellä kertaa lyhimmät reitit kaikkien solmuparien välillä.
Algoritmi perustuu kolmeen sisäkkäiseen for-silmukkaan, ja sen aikavaativuus on O(n3). Algoritmin etuna on, että se on helpompi toteuttaa kuin Bellman-Ford ja Dijkstra.