Hola.
Yo estoy usando la Api de Google Map para calcular la distancia a pie entre dos puntos. De manera similar se puede usar para que te calcule la mejor ruta, indicando los puntos de origen y destino, el tipo de ruta (pie, vehículo, etc), si se ha de transitar por determinados puntos intermedios y otros tantos parámetros opcionales.
Aquí tienes documentación oficial al respecto de esta Api. Como resultado obtendrás un archivo en XML o JSON con las coordenadas de cada cambio en el trazado de la ruta. Entiendo que lo que has de hacer con ese archivo es interpretarlo, extraer las coordenadas de cada "waypoint" y usando la polilínea que te indicaba en un mensaje anterior dibujar la ruta en tu mapa.
Yo empezaría por leer la documentación de google que te he referido antes para entender todo el procedimiento. El siguiente paso sería aprender a trabajar con el JSON y extraer la información importante.
Saludos.