algorisme de Floyd
algorisme de Floyd
- ca algorisme de Floyd, n m
- es algoritmo de Floyd
- en Floyd's algorithm
Sistemes d'informació geogràfica > Ciències de la informació geogràfica > Geomàtica > Anàlisi de xarxes
Definició
Algorisme que determina la ruta òptima entre tots els nodes d'una xarxa, cercant sistemàticament si entre cada parell de nodes i, j existeix un node k que faci que el cost acumulat de i a j passant per k sigui menor que el cost acumulat ja conegut de i a j fins al moment.
Nota
- El resultat de l'algorisme de Floyd és la matriu completa de camins mínims entre tots els nodes de la xarxa. És un algorisme de càlcul computacional intensiu, ja que calen n x n x n comparacions per a una xarxa de n nodes. Es pot accelerar substancialment quan es pot assumir que la matriu de camins mínims es simètrica (cost de i a j igual a la de j a i).
-
La informació d'aquesta fitxa procedeix de l'obra següent:
NUNES, Joan. Diccionari terminològic de sistemes d'informació geogràfica. Barcelona: Institut Cartogràfic de Catalunya: Enciclopèdia Catalana, 2012. 551 p. (Diccionaris Terminològics)
ISBN 978-84-393-8863-0; 978-84-412-2188-8
