O conceito mais simples de caminho mais curto é medir o comprimento do caminho através do número de hops. Uma outra medida é a distância geográfica em quilômetros. Entretanto, muitas outras unidades métricas são possíveis, por exemplo, o retardo médio de enfileiramento e de transmissão referente a um pacote de teste padrão, de acordo com as especificações de teste executados a cada hora. Nesse grafo, o caminho mais curto é o caminho mais rápido, e não o caminho com menor número de arcos ou quilômetros.

Existem vários algoritmos para se calcular o caminho mais curto entre dois nós de um grafo. O algoritmo de Dijkstra (1959) é um dos mais estudados. Nesse algoritmo cada nó é identificado (entre parênteses na figura) por sua distância a partir do nó de origem ao longo do melhor caminho conhecido. Inicialmente, nenhum caminho é conhecido; portanto, todos os nós são rotulados com infinito. À medida que o algoritmo prossegue e os caminhos são encontrados, os rótulos podem mudar, refletindo melhores caminhos. Um rótulo pode ser provisório ou permanente. No início, todos são provisórios. Quando se descobre que um rótulo representa o caminho mais curto possível até a a origem desse nó, ele se torna permanente e nunca mais é alterado daí em diante.

A figura acima mostra um grafo ponderado não-ponderado, onde os pesos representam a distância. Para encontrar o caminho mais curto de A até D, marca-se o nó A como permanente, o que é indicado por um círculo preenchido. Depois examina-se separadamente cada um dos nós adjacentes a A (o nó ativo), alterando-se o rótulo de cada um deles para indicar a distância até A. Sempre que um nó é rotulado novamente, ele também é rotulado com o nó a partir do qual o teste foi feito; assim, pode-se reconstruir o caminho final mais tarde. Após examinar cada um dos nós adjacentes a A, verifica-se todos os nós provisoriamente rotulados no grafo inteiro e torna-se permanente o nó que tem o menor rótulo. Esse nó passa a ser o novo nó ativo.

A partir de B pode-se examinar todos os nós adjacentes a ele. Se a soma do rótulo de B e a distância entre B e o nó que está sendo considerado for menor que o rótulo desse nó, define-se como o caminho mais curto; portanto, o nó será rotulado novamente. A figura acima mostra as cinco primeiras etapas do algoritmo.