|
|||||
|
De kortste route (2). - Floyd's Algoritme- |
|||||
| Dit is een andere
manier om de kortste route (of de lichtste gewogen route) te vinden,
maar dit algoritme werkt alleen in gerichte grafen (dat zijn grafen
waarin alle verbindingswegen éénrichtingsverkeer zijn). We nemen weer
aan dat er geen lussen of dubbele verbindingen zijn (als er lussen zijn
laten we ze weg, als er dubbele verbindingen zijn nemen we gewoon degene
met het kleinste gewicht). Begin met de gewichtsmatrix W waarvoor geldt dat wij = ∞ als er geen verbindingslijn van i naar j loopt, en als er wel zo'n verbindingslijn is, dan is wij gelijk aan het gewicht van die lijn. Daarna gaan we, beginnend met W, een serie matrices W1, W2, ...maken, met de volgende regel: |
|||||
|
© h.hofstede (h.hofstede@hogeland.nl) |
|||||