Het algoritme van Floyd-Warshall berekent het kortste pad tussen punten. We moeten dit algoritme kunnen voor het examen Wiskunde voor informatici komende donderdag. Ik heb algoritme eens bekeken en vond dat dit op sommige punten sneller kon.
Punt 1
Stel ik wil weten of het pad van punt 2 naar 3 via 1 korter is dan het huidige pad maar het pad van punt 2 naar punt 1 is oneindig. Dat betekent dat alle punten van 2 naar eender welk punt via punt 1 nooit kan want er is geen verbinding tussen punt 2 en 1.
Punt2
Als je wilt kijken of het pad korter is van punt 2 naar punt 2 via 1 is ook totaal nutteloos, want dit is altijd 0.
Punt 3
Als je van punt 2 naar punt 3 via punt 3 wilt, is ook zinloos want je gaat naar punt 3.
Punt 4
Als je wil kijken of de punten van punt 2 naar punt n via punt 2 korter kunnen is ook nutteloos.
Punt 5
Een gevolg van punt 1. Stel ik wil weten of het pad van punt 2 naar 3 via 1 korter is dan het huidige pad maar het pad van punt 1 naar punt 3 is oneindig. Dat betekent dat alle punten van 2 naar punt 3 via punt 1 nooit kan want er is geen verbinding tussen punt 1 en 3.
Dit zijn vijf kleine verbeteringen aan dit algoritme. Ik heb dit meteen in Scilab code geplaatst en dit klopt. Voor paden tussen kleine aantal punten maakt dit waarschijnlijk niet zoveel uit maar stel dat je paden hebt tussen 5000 punten. Dan heeft je algoritme 5000³ iteraties uitgevoerd, terwijl het mijne minder uitgevoerd wordt. Het algoritme wordt alvast minder dan 5000³ – 3 * 5000 keer uitgevoerd, dat is de worst-case O notatie. Als punt 1 of punt 5 voorkomt dan kan je nog eens 5000 iteraties wegnemen. Voor punt 1/5 zou ik dit nog eens moeten narekenen.
De Scilab code (oud, zonder punt 5): http://pastebin.com/f71d588af
De Scilab code: http://pastebin.com/f4d0add16
Na een test uit het boek van 5 punten, wordt er dus 125 keer doorlopen normaal en met mijn versie erbij komt dit neer op 48 keer.
update
Na een tweede blik op de verbeteringen, heb ik een vijfde puntje gevonden. Het algoritme ging van 48 stappen naar 31 stappen. Ik had in één klap +10% winst gemaakt.
Opgelet!
De graaf moet gesloten zijn en er moet dus een weg zijn voor ieder punt in de graaf. Dit is ook de voorwaarde van de originele Floyd-Warshall algoritme. Anders krijg je bv een punt x dat niet met een ander punt y kan verbonden worden via andere punten.