theorie des graphes

Question

bonjour, s'il vous plais pouvez vous m'aider à resoudre se problème de graphe en C++ ou de preference en ruby problème: 1.entées/sorties écrire un programme permettant de lire le fichier de description d'un graphe puis de réécrire le fichier aprés avoir symétriser le graphe. le poid d'une arête est la sommet des poidsq des arcs initiaux. 2. plus court chemin écrire un algorithme permettant de trouver le plus court chemin du'un sommet à un autre. sachons que un graphe est décrit dans un fichier texte, organiser comme suite: -une ligne composée uniquement d'espaces ou commançant par #est un commantaire -chaque arc partant de ce sommet est décroit sur sur une ligne de la forme: << nom_ou_numero_du_sommet poids >> merci boucoup. wael gaaloul je serais trés hereux de resevoir des livres blancs, des invitations salons gratuites, des sondages software/hardware. et c'est trés jentille de vous pour nous interroge à travailler et à aimer le domaine d'informatique

nickydaquick · Answer

Salut, 
  Pour faire un graphe il te faut creer 2 structures et 1 tableaux recensant chacune de ces strutures: la premiere est une Arete la seconde est un Noeud.
 ensuite chaque Arete et chaque Noeud a un poids attribue, les noeuds ont des poids variables (ce sont eux qui determinent le plus court ou le plus long chemin) et les Aretes ont un poids fixe.

ensuite utilise l'agorithme de Bellman-Ford ( plus rapide et fiable que Djikstra) pour retrouver ton plus court chemin (listage de toutes les Aretes et reaffectation des poids des Noeuds)

 si tu veux un exemple en profondeur je peux t'en poster un en C/C++, tres simple et qui fonctionne : resoudre les labyrinthes a l'aide des graphes.

      J'espere avoir aider, salut
 je suis heureux de faire partie d'une grande famille ...!

Theorie des graphes

1 réponse

Votre réponse

Discussions similaires