chemin le plus court dans un graphe

Question

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] ]

PlugnPlay666 · Answer

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("
Entrez l'abcisse du point p1")
p1.x = int(input('>..... '))

print("

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

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

Entrez 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)

Chemin le plus court dans un graphe

1 réponse

Votre réponse

Discussions similaires