algorisme de Dijkstra
algorisme de Dijkstra
- ca algorisme de Dijkstra, n m
- es algoritmo de Dijkstra
- en Dijkstra'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 calculant la ruta òptima acumulada entre el node inicial del recorregut i els nodes adjacents, establint el node adjacent de ruta òptima acumulada en cada iteració i repetint el càlcul a partir d'aquest node per a la resta de nodes pendents fins que troba la ruta òptima acumulada per al node final del recorregut.
Nota
-
1. L'algorisme de Dijkstra és un algorisme exacte que garanteix la solució òptima.
2. L'algorisme de Dijkstra requereix informació topològica de connectivitat entre els nodes i de cost associat als arcs, i resol de manera eficient el problema de la ruta òptima entre dos nodes, per al qual no resulten apropiats els algorismes de càlcul de la ruta òptima entre tots els nodes d'una xarxa.
3. L'algorisme de Dijkstra va ser formulat per l'informàtic holandès Edsger Dijkstra. -
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
