algorisme de Ford
algorisme de Ford
- ca algorisme de Ford, n m
- es algoritmo de Ford
- en Ford'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 dos nodes qualssevol d'una xarxa de forma sistemàtica sense necessitat de progressar a través dels nodes adjacents de mínim cost acumulat.
Nota
-
1. L'algorisme de Ford actua de manera semblant a l'algorisme de Dijkstra, però no requereix el marcatge dels nodes amb etiquetes binàries d'estat (pendent/resolt), gràcies al fet que a cada iteració comprova sistemàticament per a tot node j si existeix un arc (i, j) tal que la impedància acumulada des del node inici fins al node i més la impedància de l'arc (i, j) sigui menor que la impedància acumulada des de l'inici fins al node j, sense limitar la comprovació només als nodes pendents ni utilitzar només nodes intermedis resolts.
2. L'algorisme de Ford té l'avantatge addicional d'admetre l'assignació de costos negatius als arcs de la xarxa. -
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
