chemin le plus court dans un graphe

Bonjour,

j'ai besoin de quelques conseils pour un travail en python sur un graphe.

Nous devions faire une fonction qui donner tous les chemins qui menés à 12 ( ji suis parvenue) et une autre qui donne le plus court chemin.
Est ce que vous pourriez m'aider pour cette seconde question car je n'y parviens pas.

On a :

graphe=[[1,4],[0,2,7],[3,8,1],[2],[0,5,6],[4],[4,7,10,11],[1,6,8],[2,7,9],[8,10,12],[6,9,11],[6,10,12],[9,11]]

distance=[ [5,5] , [5,2,3] , [3,1,3] , [1] , [5,6,2] , [6] , [2,6,5,9] , [2,6,4] , [3,4,2] , [2,1,5] , [5,1,4] , [9,4,2] , [5,2] ]

Je te donne un petit code pour trouver la distance entre 2 points sur un graphique.


# -*- coding: utf-8 -*-

from math import sqrt

class Point():
"""Définition d'un point mathématique.""" # à indenter d'un cran

def distance(p1,p2): # indentation : 1 cran
distance = sqrt( (p1.x-p2.x)**2 + (p1.y-p2.y)**2) #indentation : 2 crans
return distance #indentation : 2 crans


p1 = Point()
p2 = Point()
print("\nEntrez l'abcisse du point p1")
p1.x = int(input('>..... '))

print("\n\nEntrez l'ordonnée du point p1")
p1.y = int(input('>..... '))


print("\n\nEntrez l'abcisse du point p2")
p2.x = int(input('>..... '))

print("\n\nEntrez l'ordonnée du point p2")
p2.y = int(input('>..... '))

AffichDistance = Point.distance(p1,p2)
print("La distance qui sépare les deux points est de %s" % AffichDistance)