Implémentation de l'algo de Dijkstra en C

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 :

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