Discussion :

[Mus54Ep]

Bonjour à tous,
Et bien, j'ai vraiment besoin d'une idée sur l'exploration de tous les chemins dans un graphe orienté. J'en ai besoin pour terminer mon tp (Plus court chemin).
J'ai défini un tableau de poids pour tous les arcs. Est-ce que je doit définir encore la matrice d’adjacence ou non ?
En fait, je sais comment définir la matrice d'adjacence. Cependant, ce que je voudrais savoir c'est une petite idée pour l'exploration.
Si vous voulez voir le code que j'ai écrit, je le déposerai plus tard.
Merci d'avance.

[ternel]

Bien sûr qu'on veut voir ton code.

Par contre, tu as regardé du coté de dijsktra (ortographe incertaine)?

[Mus54Ep]

Merci pour votre réponse
Contrairement a l'algorithme de Dijkstra (ou Ford-Bellman), le principe de l'optimisation est de parcourir tous les chemins possibles.
Voila donc le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
 
 
struct Arc{
	int pd; //point de départ
	int pf; // point d'arrivée
	double poid;
 
	//Définir le poid de l'arc
	void setPoid(double pp)
	{
		poid = pp;
	}
 
	//Définir les 2 sommets
	void setSommets(int a, int b)
	{
		pd = a;
		pf = b;
	}
};

/*************************************************************************/

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
struct  Chemin{
	int sommet;
	double distance;
	Chemin*arcSuivant;
	//Définir la distance
	void setDistance(double x)
	{
		distance += x;
	}
};

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
int main()
{
 
	cout << "Combien de sommet? ";
	int n;
	cin >> n;
	int i = 0, j = 0, k = 0;
	double poidtemp;
	vector <Arc> arc;
	arc.resize(n*n);
	while (i<n)
	{
		while ((k<n*n) && (j<n))
		{
			arc[k].setSommets(i + 1, j + 1);
			cout << endl << "poid[" << i + 1 << "," << j + 1 << "] = ";
			cin >> poidtemp;
			arc[k].setPoid(poidtemp);
			j++;
			k++;
 
 
		}
		j = 0;
		i++;
	}
	for (int i = 0; i<n*n; i++)
	{
		arc[i].Afficher();
	}
}

[bacelar]

Actuellement, vos classes Arc et Chemin ne proposent rien d'utile.
Vous pouvez rendre votre code bien plus simple en remplaçant Arc par un simple int dans un std::vector<unsigned int> de taille n*n représentant le poids de l'arc.
Et en remplaçant Chemin par un std::vector<int> correspondant à la liste des sommets du chemins, sa valeur distance pourra facilement se calculer avec le std::vector<unsigned int> représentant les arc.
Pour avoir l'ensemble des chemins d'un graphe partant d'un sommet, un simple parcours en profondeur ou en largeur devrait faire l'affaire (à faire sur chaque sommet).

[Mus54Ep]

bacelar

Merci,
Donc, je doit définir la matrice d'adjacence?

[bacelar]

Sauf erreur de ma part, on vous donne les poids des arcs dans un tableau N*N.
Si le poids ne peut être null ou négatif, le plus simple, c'est de mettre ces valeurs interdites dans le tableau.
Ainsi, il n'y a pas de redondance dans les données.
Pour savoir si un sommet est accessible depuis un autre, il suffira de voir si le poids de l'arc dans le tableau a une valeur valide ou pas.

[Mus54Ep]

J'ai défini la matrice et j'ai déjà traité les cas de nullité (je ne vais pas prendre en considération les cas de négativité).

voici le code de la matrice des poids:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void main()
{
	vector<unsigned int> arc;
	cout << endl << "Combien des sommet vous avez? ";
	int nbrSommets;
	cin >> nbrSommets;
	double**MatPoids;
	MatPoids = new double*[nbrSommets];
	for (int i = 0; i < nbrSommets; i++)
	{
		MatPoids[i] = new double[nbrSommets];
		for (int j = 0; j < nbrSommets; j++)
		{
			if (i == j)
			{
				MatPoids[i][j] = 0;
			}
			else
			{
				cout << endl << "La distance entre " << i + 1 << " et " << j + 1 << " : ";
				cin >> MatPoids[i][j];
			}
		}
	}
	for (int i = 0; i < nbrSommets; i++)
	for (int j = 0; j < nbrSommets; j++)
	{
		cout << endl << "La distance entre " << i + 1 << " et " << j + 1 << " est :" << MatPoids[i][j]<<endl;
	}
}

Maintenant, je ne sais pas comment continuer.
Est-ce que je dois redéfinir un tableau de chemins possibles ? Si c'est le cas, pourriez-vous m'aider un peu SVP? Je suis débutant et je ne sais pas trop du parcours (en profondeur ou en largeur) en C++, d'ailleurs, je n'ai jamais travaillé sur les graphes.
Cordialement

[JolyLoic]

Tu veux parcourir tous les chemins possibles ? Bon courage ! Dans le graphe :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
A -> B
B -> C
C -> A
C -> D

Entre A et D, tu as comme chemins possibles :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
ABCD
ABCABCD
ABCABCABCABCABCABCABCABCABCABCD
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCD
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCD
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCD

Et tout plein d'autres ! Je pense donc que tu poses mal ta question.

[bacelar]

Pourquoi avez-vous régressé d'un std::vector avec des coordonnées linéarisées vers des pointeurs nus, des new[] dans tout les coins sans aucun delete[] sans aucune protection contre les fuites mémoires?

Supprimez tout ce fatras.

Votre approche n'est pas super pratique pour des graphes peu denses, car il faudra mettre des valeurs interdites pour tous les arcs interdits.
Disons que la valeur interdite est -1, mais attention à ne pas faire de tests d'égalité avec car vous utilisez des doubles qui n'ont pas représentation exacte de -1.

http://fr.wikipedia.org/wiki/Parcours_de_graphe
Y a plus qu'à.

[Mus54Ep]

Ok, j'ai mal posé ma question
Ce que je veux dire, c'est qu'on doit parcourir tous les chemins partant d'un point A vers un point B. Mais s'il y a un circuit, bien sûr qu'on ne va pas les explorer à chaque fois. On va définir une certaine structure ou variable (comme par ex: une variable qui indique si un sommet quelconque est marqué ou pas encore).

[JolyLoic]

Donc si je reformule : Tu veux tous les chemins entre deux points qui ne passent qu'une fois par chaque nœud.

Donc, par exemple, si tu as 1 nœud A avec en sortie 100 nœud B1..B100, puis derrière 100 nœuds C1..C100, chaque nœud Bi ayant en successeur tous les nœuds Cj, puis un nœud D unique successeur de tous les nœuds C, tu veux avoir en tout 10000 chemins :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
AB1C1D
AB1C2D
..
AB2C1D
AB2C2D
...
AB100C100D

C'est bien ça ?
Je pose ces questions non pas pour chipoter, mais bien parce que je ne sais comprends vraiment pas ce que tu veux obtenir, surtout que tu dis que tu veux faire ça dans le cadre d'un tp ayant pour but de trouver le plus court chemin, et que je ne vois vraiment pas le rapport.

[Mus54Ep]

Voici un simple exemple :

Les chemins possibles que je veux trouver sont:
Exemple: Entre 1 et 5, on doit finalement trouver:
1->3->5
1->4->5
1->3->4->5

[JolyLoic]

Ok, ça a l'air de correspondre à mon exemple. Si tu es bien conscient que le nombre de chemins peut être très grand, tellement grand qu'on peut vite exploser les capacités de la machine (par exemple, avec mon exemple à 202 nœuds, on arrive à 10000 chemins, et on pourrait faire bien pire, je peux construire un graphe de 2*n+2 nœuds où le nombre de chemins vaut 2^n), l'algorithme est assez simple. L'objectif est juste de parcourir dans l'ordre tous les chemins possibles, en s'arrêtant aux boucles (donc marquage pour les détecter).

On part du nœud initial, on le marque. On regarde les successeurs non marqués :
- Si cet ensemble est vide, on est dans une impasse, on enlève de dernier bout de chemin courant, on enlève la marque du nœud, et on recommence au successeur suivant
- Si cet ensemble contient le nœud final, on ajoute le chemin à la liste des chemins
- Sinon, on recommence le processus à partir de chaque successeur non marqué.

Dans ton exemple : (entre parenthèses, le chemin courant)
On part de 1, on le marque (1)
3 successeurs non marqués : 2, 3, 4
On marque 2, on continue (12)
0 successeurs non marqués : impasse, on démarque 2, on remonte au nœud 1, et on s'occupe du successeur arrivant après 2
On marque 3, on continue (13)
2 successeurs : 4 et 5
On marque 4, on continue (134)
1 successeur final : 5 => 1 chemin 1345
On remonte à 3 (on démarque 4), on prend le successeur suivant : 5 => 1 chemin 135
On remonte à 3, plus de successeurs, on remonte à 1 (en ayant démarqué 3), et on s'occupe du successeur suivant 3 : 4
On marque 4, on continue (14)
1 successeur final : 5 => 1 chemin 145

Le marquage ne sert à rien dans ton exemple, car on n'a pas de cycle.

Et je ne vois toujours pas ce que ça vient faire dans un calcul de plus court chemin...

[Mus54Ep]

Que proposez-vous d'autres ?

[Jean-Marc.Bourguet]

Que proposez-vous d'autres ?

Si ton TP concerne les plus cours chemin, regarde l'algo de Dijsktra et A* (on peut considérer l'algo de Dijstra comme un cas particulier de A*).

[foetus]

Il y a l'algorithme naïf , avec 2 graphes (comme un peu avec les algos Dijkstra): celui avec les sommets retenus et celui avec les sommets disponibles.
Évidemment comme tu peux t'en douter et comme l'a dit JolyLoic, cela va être un tableau (ou peut-être un arbre) avec comme élément ces 2 graphes.

Exemple avec ton exemple.
Début: ({1}, {2, 3, 4, 5})

Du sommet 1 on peut aller aux somment 2, 3, et 4
({1, 2}, {3, 4, 5}), ({1, 3}, {2, 4, 5}), ({1, 4}, {2, 3, 5})

Ensuite du sommet:
*) 2, on peut aller nulle part
*) 3, on peut aller aux sommets 2, 4, 5
*) 4, on peut aller aux sommets 2, 5

({1, 2}, {3, 4, 5}), ({1, 3, 2}, {4, 5}), ({1, 3, 4}, {2, 5}), ({1, 3, 5}, {2, 4}), ({1, 4, 2}, {3, 5}), ({1, 4, 5}, {2, 3})

Ensuite du sommet:
*) 2 (chemins 1->2, 1->3->2 et 1->4->2), on peut aller nulle part
*) 4, on peut aller aux sommets 2, 5

On a déjà trouvé 1->3->5 et 1->4->5

({1, 2}, {3, 4, 5}), ({1, 3, 2}, {4, 5}), ({1, 3, 4, 2}, {5}), ({1, 3, 4, 5}, {5}), ({1, 3, 5}, {2, 4}), ({1, 4, 2}, {3, 5}), ({1, 4, 5}, {2, 3})
Bon ici on a fini parce qu'on est arrivé soit au sommet terminal 5 soit au sommet "puits" 2.

Et pour la gestion des cycles, il y a peut-être la possibilité de bricoler un truc en regardant le chemin déjà parcouru et les sommets disponibles

Édit: On peut faire une gestion au fil de l'eau en retirant les chemins qui vont nulle part et ceux gagnants