Podrías usar
Djisktra para resolverlo. Dentro de los algoritmos de encaminamiento es, en mi opinión, uno de los más sencillos de implementar.
Lo que tienes frente a tí no es más que un grafo con pesos en sus nodos. Lo que tienes que hacer es buscar el camino con peso mínimo.
Este es un clásico dentro de los algoritmos usados por los GPS para llevarte a tu destino. El peso de los nodos puede ser la distancia, la velocidad de la vía, el tiempo empleado (depende de la distancia y de la velocidad máxima de la vía), el camino con menos desnivel, ... al final todo consiste en asignar pesos a los nodos y dejar que un algoritmo de encaminamiento haga su trabajo :).
EDITO: Aunque los algoritmos de encaminamiento van encaminados a encontrar la ruta más corta con un par de cambios puedes hacer que tu algoritmo busque rutas con un peso específico... simplemente hay que ir descartando las rutas que vayas encontrando con pesos menores al deseado y quedarte con la primera (o con todas) las que cumplan el peso deseado.