Algoritme Leenknegt-Floyd-Warshall

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.

9 Responses to Algoritme Leenknegt-Floyd-Warshall

  1. Glenn zegt:

    Knap hier zocht ik al achter ,heb morge ook dat examen :)

    weet ge welke functies er nog moete gemaakt worde in scilab en waar ge die erges kunt vinde? in de cursus staan ze volges mij toch nergens :)

  2. stijn1989 zegt:

    @Glenn: als toekomstige informaticus moete dat zelf kunnen hé anders zijde geen echte. Je moet de pivoteer kunnen implementeren en die Floyd-Warshall (die kan je vinden op wikipedia).

  3. Glenn zegt:

    ma der is e stuk cursus voor die dinge geweest in de les en die heb ek dus gemist :p wa wel balen is, zeker als ge zo ne krak zij in scilab “ahum”

  4. stijn1989 zegt:

    Volgens mij heb je hoofdstuk 5 nog niet bekeken want dat is over Scilab. En als je het manueel kan uitvoeren die algoritmes, dan kan je ze ook programmeren. Lastig is dat niet.

  5. Glenn zegt:

    jah heb het bekeken, maarja ben niet zo goed in scilab int algemeen,zal wel zien wat het geeft

  6. stijn1989 zegt:

    Mensen die me code gebruiken. Dit is niet Floyd maar Leenknegt-Floyd! In het algoritme van Floyd overlopen we alle knooppunten!

  7. Knops Ignace zegt:

    Zo herken je een echte programmeur die doorgaat waar anderen stoppen ;)

  8. jeroen zegt:

    zou het kunnen dat je in nieuwe versies van SciLab de 2 inf (van infinite) moet veranderen door %inf
    want net je code getest en werkte niet maar wel met %inf

Geef een reactie

Vul je gegevens in of klik op een icoon om in te loggen.

WordPress.com logo

Je reageert onder je WordPress.com account. Log uit / Bijwerken )

Twitter-afbeelding

Je reageert onder je Twitter account. Log uit / Bijwerken )

Facebook foto

Je reageert onder je Facebook account. Log uit / Bijwerken )

Google+ photo

Je reageert onder je Google+ account. Log uit / Bijwerken )

Verbinden met %s

%d bloggers op de volgende wijze: