A voir également:
- Algorithme de dijkstra en c
- Ecrire un algorithme qui permet de resoudre ax²+bx+c=0 - Forum Algorithmes / Méthodes
- Algorithme euromillion excel gratuit - Forum Excel
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Écrivez un algorithme qui calcul l'équation du second degré à 2 inconnus - Forum Programmation
- Algorithme maximum de 3 nombres ✓ - Forum Algorithmes / Méthodes
20 réponses
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 749
18 avril 2006 à 18:55
18 avril 2006 à 18:55
Si c'est une matrice c'est tout s'implement que tu appliques un Dijkstra en prenant pour source plusieurs (ou la totalité des) sommets du graphe.
L'algorithme de Dijkstra retourne un vecteur de poids et un de successeurs. Il suffit donc de mettre ces vecteurs les uns en dessous des autres pour obtenir les deux matrices dont tu parles.
Idéalement tu peux coder un algorithme de dijkstra qui prend en paramètre :
- le graphe (ou la matrice décrivant le graphe)
- le sommet source
... et qui retourne :
- le vecteur de poids
- le vecteur de successeurs
On va supposer que les sommets sont identifiés par un entier pour simplifier, et que les arcs sont pondérés par un entier positif
Exemple :
...qui sera appelée par une fonction qui calculera toute la matrice
Il faut par ailleurs :
- soit implémenter une classe de graphe
- soit repartir d'une classe de graphe d'une lib existante, genre la lib boost
- soit se baser sur une matrice d'adjacence décrivant le graphe, dans laquelle il faudra caractériser un poids infini pour les sommets non adjacents.
Bonne chance
L'algorithme de Dijkstra retourne un vecteur de poids et un de successeurs. Il suffit donc de mettre ces vecteurs les uns en dessous des autres pour obtenir les deux matrices dont tu parles.
Idéalement tu peux coder un algorithme de dijkstra qui prend en paramètre :
- le graphe (ou la matrice décrivant le graphe)
- le sommet source
... et qui retourne :
- le vecteur de poids
- le vecteur de successeurs
On va supposer que les sommets sont identifiés par un entier pour simplifier, et que les arcs sont pondérés par un entier positif
Exemple :
typedef unsigned int vertex_t;
typedef unsigned int weight_t;
void dijkstra(
const graph_t & g, // le graphe
const vertex_t & src, // le sommet source
std::vector<vertex_t> & succs,
std::vector<weight_t> & poids
){
// mon algo remplit succs et poids
}
...qui sera appelée par une fonction qui calculera toute la matrice
void dijkstra_matrix(
const graph_t & g, // le graphe
std::vector<std::vector<vertex_t> > & succs_mat,
std::vector<std::vector<weight_t> > & poids_mat
){
vertex_t vit=0;
vertex_t vend=g.card_v(); //retourne le nombre de sommets
for(vit = 0 ; vit != vend ; ++vit){
//calculer le dijkstra pour la source courante
std::vector<vertex_t> succs = std::vector<vertex_t>(g.card_v());
std::vector<weight_t> poids = std::vector<weight_t>(g.card_v());
dijkstra(g,vit,succs,poids);
succs_mat.push_back(succs);
poids_mat.push_back(poids);
}
}
Il faut par ailleurs :
- soit implémenter une classe de graphe
- soit repartir d'une classe de graphe d'une lib existante, genre la lib boost
- soit se baser sur une matrice d'adjacence décrivant le graphe, dans laquelle il faudra caractériser un poids infini pour les sommets non adjacents.
Bonne chance
18 avril 2006 à 19:54
a chaque etape l'ensemble s et s'
afficher en dernier etape la liste des plus court chemins entre tt couple
de sommets ainsi que leurs valeurs.
et merci encore
11 janv. 2008 à 15:20
1 avril 2011 à 17:25
Tu met que ton algo remplit succs et poids,
est-ce que tu pourrais mettre cet algo en ligne stp,
merci d'avance
8 mars 2012 à 11:14
merci d'avance