Calcul de chemins dans un graphe

Bonjour,

Le sujet est vieux mais il est marrant, alors voici quelques idées pour démarrer.

Avant de démarrer, un peu de terminologie :

• Sommet = les villes dans ce problème. L'ensemble des sommets est noté V.
• Sommet source = la ville de départ
• Sommet cible = la ville de destination (par exemple, Rome)
• Arc = les routes connectant deux villes adjacente. L'ensemble des sommets est noté E.
• Graphe = ensemble des sommets et des arcs (dans ton cas, la carte routière)
• Chemin = une séquence d'arcs consécutifs allant d'un sommet source à un sommet cible
• Cycle = un chemin dont le sommet source et le sommet cible sont identique
• Boucle = cycle n'impliquant qu'un seul arc
• Poids d'un arc = le coût à payer pour traverser un arc. Si les poids sont définis sur les sommets, alors peut se ramener à des poids installés sur des arcs en considérant le coût installé sur le sommet cible de l'arc.
• Graphe pondéré = Graphe muni d'une structure de poids (qui donne à chaque arc un poids).

Ensuite, il faut se poser quelques questions sur le problème que l'on veut résoudre. En fonction de celui-ci, des algorithmes sur étagère permettent de répondre immédiatement au problème dans un graphe pondéré.

• Que veut-on optimiser ? Cela induit une algèbre de poids.
  • La distance ?
  • Le coût financier ?
  • Les deux, selon un ordre lexicographique (par exemple le prix, puis à prix égal, la distance) ?
  • Est-ce que cette algèbre de poids permet la formation de cycle absorbant ?
• Que veut-on déterminer ? 
  • Les plus courts chemin entre une source et tous les autres sommets (atteignables) du graphe ? Ou les plus courts chemins, quelle que soient la source et la destination ?
  • Pour chaque couple source destination :
    • Le plus court chemin ?
    • Tous les chemins (sans boucle) ?

Concernant la première question, si le coût est la seule métrique prise en compte, alors un cycle absorbant peut être formé. Si on optimise d'abord le coût puis la distance, des arcs négatifs peuvent apparaître (tous ceux dont le coût financier est négatif). Si on n'optimise que la distance ou que la distance est la première des deux métriques à optimiser, alors "tout va bien" sous réserve qu'il n'y ait pas d'arc dont la distance kilométrique est nulle.

• Si le graphe ne comporte pas d'arc de poids négatif (et donc de cycle absorbant), on peut utiliser l'algorithme de Dijkstra. Il se calcule en O(|V|+|E|). En C++, l'algorithme de Dijkstra est implémenté dans la BGL (boost graph library).
• Si le graphe ne comporte pas des arcs de poids négatifs mais pas de cycle absorbant, on peut utiliser de Bellman Ford (une source) ou l'algorithme de Floyd Warshall (pour tout sommet source). L'algorithme de Bellman Ford se calcule en O(|V|.|E|). En C++, l'algorithme de Bell Ford est implémenté dans la BGL (boost graph library).
• Sinon, il faut énumérer les chemins et rejeter ceux qui engendre un cycle (en particulier de poids négatifs), puisque dans ton problème tu cherches des chemins sans cycle et sans boucle. 

Vue la manière dont est formulé le problème, j'ai l'impression que tu es dans le troisième cas.

Algorithme naïf

On énumère tous les chemins possibles et rejeter les chemins mal formés (ceux comportant un cycle et ceux dont le coût est trop élevé étant donné le budget initial) avec un algorithme de branchement.

• S =  ensemble S de paires (chemin partant de s, budget restant), initialisé à {([s], budget initial)}, où s désigne le sommet de départ.
• R = ensemble S de paires (chemin, budget restant) à destination de t = "Rome", initialisé à l'ensemble vide.
• Tant que S est non vide
  • S' = ensemble vide
  • Pour chaque paire (p, b) de S
    • Soit u le dernier sommet de p
    • Pour chaque sommet v voisin de u
      • Si le coût k_uv de (u, v) <= b et si v n'est pas dans déjà dans p (critère de rejet)
        • Ajouter dans S' la paire (p + (u, v), b - k_uv), où p + (u, v) désigne le chemin obtenu en concaténant l'arc (u, v) à la suite du chemin p 
        • Si v == t
          • Ajouter (p + (u, v), b - k_uv) dans R
  • S = S'
• Retourner R

Terminaison : Le nombre de sommet de G est fini. L'algorithme de considère que des chemins sans boucle et donc de taille au plus |V|. Le nombre de chemins sans boucle est fini. Chaque itération traite un nouveau chemin sans boucle. Il y a donc un nombre fini d'itérations, et donc l'algorithme termine.

Justesse : L'algorithme parcourt tous les chemins bien formés (sans boucle et à budget positif), en particulier ceux à destination de Rome.

Complexité : Si on se restreint au graphe tel qu'il existe au plus un arc entre deux sommets arbitaires, le cas le plus défavorable est quand le graphe forme une clique tel que les contraintes de budget n'écarte aucun chemin (par exemple, pas de taxe de séjour). L'algorithme proposé considère les chemins commençant par s et suivi de n'importe quel arrangement de sommet (autre que s). La somme des arrangements A(n, k) pour k allant de 0 à n est en O(n!), donc l'algorithme est en O((|V|-1)!), autant ça coûte un bras.

Algorithme "malin"

Précision préalable, l'algorithme malin ne répond pas à la question telle que tu l'as formulée, car on se propose ici de ne considérer qu'au plus un chemin de s à t au lieu de tous les chemins (bien formés) de s à t.

Pour cela, on peut simplement adapter l'algorithme de Bellman Ford en ajoutant le critère de rejet vérifiant que le budget reste positif et que le chemin est sans boucle. Comme on rejette les chemins avec des boucles, les cas qui font "planter" l'algorithme de Bellman Ford ne surviennent pas et l'algorithme ainsi modifié calcul un résultat juste.

La complexité devient alors O(|V|.|E|) (soit en O(|V|^2) s'il y a au plus un arc entre chaque paire de sommet), ce qui est clairement bien moins cher que O((|V|-1)!). Mais on aura qu'un seul chemin (un arbitraire chemin arbitraire parmi les chemins optimaux).

Bonne chance