A Figura 1 abaixo representa a rede de estradas conectando as cidades de A a G. As distâncias em quilômetros entre duas cidades estão representadas nos pesos atribuídos às arestas.
Figura 1 Rede de estradas conectando as cidades de A a G
Neste caso, a aplicação do algoritmo de Dijkstra é capaz de determinar a rota mais curta entre duas cidades quaisquer.
Levando-se em consideração o procedimento de Dijkstra, pode-se afirmar que o número total de rotas de menor comprimento conectando as cidades A e G é igual a: