Se conocen varios algoritmos de cálculo de la trayectoria más corta entre dos nodos de un grafo. Éste se debe a Dijkstra. Cada nodo se etiqueta con su distancia al nodo origen a través de la mejor trayectoria conocida. Inicialmente no se conocen trayectorias, por lo que todos los nodos tienen la etiqueta infinito.

A medida que avanza el algoritmo y se encuentra trayectorias, pueden cambiar las etiquetas, reflejando mejores trayectorias. Una etiqueta puede ser tentativa o permanente. Inicialmente todas las etiquetas son tentativas. Al descubrirse que una etiqueta representa la trayectoria más corta posible del origen a ese nodo, se vuelve permanente y no cambia más.