Calcul itineraire routier

Bonjour a tous!

Je viens de me lancer dans la création d'un programme pour calculer un itinéraire routier (résultat sous forme d'un fichier texte contenant les villes étapes et les distances entre chaque ville).
Pour le moment je me contente de faire ca avec seulement quelques villes mais je voudrais bien le faire pour toutes les communes francaises (36000 ca sera déjà bien mdr).
Je me base sur l'algorithme de Dijkstra pour le commencement mais avec les 36000 communes le tableau de données devient trop grand (36000*36000) et cela devient trop couteux.
Si quelqu'un avait une solution...

Merci d'avance (meme si a mon avis j'ai pas été trés clair)

N'hésitez pas à me poser des questions.