Théorie des graphes
PCBill
Messages postés
48
Date d'inscription
lundi 25 décembre 2006
Statut
Membre
Dernière intervention
29 septembre 2009
-
4 juin 2008 à 12:32
nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 - 4 juin 2008 à 16:16
nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 - 4 juin 2008 à 16:16
1 réponse
nickydaquick
Messages postés
416
Date d'inscription
vendredi 31 janvier 2003
Statut
Membre
Dernière intervention
19 décembre 2013
3
4 juin 2008 à 16:16
4 juin 2008 à 16:16
Salut,
il n'y a qu'une seule formulation. Voici l'algorithme, a moins que je ne me trompe,
1- il faut mettre tous les noeuds a un poids positif assez grand (le nombre de noeuds est le strict minimum safe)
2 - mettre le poids du premier noeud a 0
3- a partir de ce noeud la , utiliser une file d'attente: le noeud suivant tente d'attribuer a tous les noeuds a ki il est connecte un poids = Math.min(son poids+1, le poids du noeud)
4- on enfile le noeud pour traitement ulterieur
j'espere avoir aide, verifie aussi du cote de Bellmann-Ford qui lui passe par les Aretes. La derniere fois que j'ai fais des tests chronos , celui-ci allait super plus vite.
il n'y a pas d'implementation sur le site a ce que j'ai pu voir, j'en deposerai une bientot (resolution de labyrinthes )
http://www.liveplayaz.com
je suis heureux de faire partie d'une grande famille ...!
il n'y a qu'une seule formulation. Voici l'algorithme, a moins que je ne me trompe,
1- il faut mettre tous les noeuds a un poids positif assez grand (le nombre de noeuds est le strict minimum safe)
2 - mettre le poids du premier noeud a 0
3- a partir de ce noeud la , utiliser une file d'attente: le noeud suivant tente d'attribuer a tous les noeuds a ki il est connecte un poids = Math.min(son poids+1, le poids du noeud)
4- on enfile le noeud pour traitement ulterieur
j'espere avoir aide, verifie aussi du cote de Bellmann-Ford qui lui passe par les Aretes. La derniere fois que j'ai fais des tests chronos , celui-ci allait super plus vite.
il n'y a pas d'implementation sur le site a ce que j'ai pu voir, j'en deposerai une bientot (resolution de labyrinthes )
http://www.liveplayaz.com
je suis heureux de faire partie d'une grande famille ...!