Java, du tableau au graphe oriente.

[Résolu/Fermé]
Signaler
Messages postés
445
Date d'inscription
vendredi 25 novembre 2005
Statut
Membre
Dernière intervention
3 février 2013
-
Messages postés
445
Date d'inscription
vendredi 25 novembre 2005
Statut
Membre
Dernière intervention
3 février 2013
-
Bonjour tout le monde,

Je dispose d'une matrice d'entiers de taille n. Je dois calculer le plus court chemin du somment c'est a dire de la position d'entrée matrice[0][0] a la sortie, matrice[n-1][n-1]. Au préalable je dois transformer cette matrice en un graphe oriente et ensuite application le fameux Djistra pour calculer le plus cout chemin. A noter que le calcul du plus court chemin sera fait sur les valeurs de chaque élément de la matrice.
Quelqu'un aurait - il déjà fait quelque chose de ce genre?
Comment je pourrais effectivement effectuer cette transformation du tableau en graphe oriente?
Merci pour votre aide.



1 réponse

Messages postés
16410
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 octobre 2021
2 903
Tu peux utiliser des bibliothèques de manipulation de graphes comme GraphStream
Messages postés
445
Date d'inscription
vendredi 25 novembre 2005
Statut
Membre
Dernière intervention
3 février 2013
57
Merci KX,
Comment je peux faire pour une implémentation moi même sans utiliser une telle librairie?
Messages postés
16410
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 octobre 2021
2 903
En refaisant comme eux, créer des objets noeuds, des objets arêtes, les lier les uns aux autres, rajouter tes poids, et lancer ton algorithme de Dijkstra sur ce que tu obtiens.
Messages postés
445
Date d'inscription
vendredi 25 novembre 2005
Statut
Membre
Dernière intervention
3 février 2013
57
Bah la je suis encore coince et je sais ce qui ce passe j'ai pourtant lu la doc. compilation ok
Javac -classpath Path_to\gs-core-1.1.1.jar Myprog.java
. il compile bien mais a l'execution
Exception in thread "main" java.lang.NoClassDefFoundError: org/graphstream/graph/Graph
. Y a t-il autre chose que j'ignore?
Messages postés
16410
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 octobre 2021
2 903
Lorsque tu utilises -classpath tu dois penser à conserver le répertoire courant avec le point

javac -classpath D:\gs-core-1.1.1.jar;. Myprog.java

Petit exemple pour tester :

import org.graphstream.graph.implementations.SingleGraph;

public class Test
{
	public static void main(String...args)
	{
		SingleGraph g = new SingleGraph("Test",false,true);

		g.addEdge("AB", "A", "B").setAttribute("label","AB");
		g.addEdge("BC", "B", "C").setAttribute("label","BC");
		g.addEdge("CA", "C", "A").setAttribute("label","CA");
		
		g.display();
	}
}
Messages postés
445
Date d'inscription
vendredi 25 novembre 2005
Statut
Membre
Dernière intervention
3 février 2013
57
Merci bien KX,
sa marche . j'avais toujours une erreur a l'execution, une exception classNotFound... et ce bout de code m'a permis de l'excute correctement.
java -classpath Path_to\gs-core.jar;. Myprog

Merci encore