Chemin le plus court dans un graphe en parallèle

Bonjour,

je voudrais savoir s’il existe un algorithme de plus court chemin avec contraintes temporelles dans un graphe qui est susceptible d'être parallélisé?

merci pour vos réponses!

Citation:

---

Envoyé par arkerone

je voudrais savoir s’il existe un algorithme de plus court chemin avec contraintes temporelles dans un graphe qui est susceptible d'être parallélisé?

---

Bonjour,

Il nous faudrait un peu plus de détail sur le problème que tu souhaites résoudre.

Par exemple, s'agit-il de trouver le chemin le plus court entre 2 noeuds connus (single-source shortest path) ou de trouver le plus court entre 2 noeuds quelconques (all pairs short path) ? Est-ce que le graphe est orienté ? De quel contrainte temporelle s'agit-il ? Les dimensions du problème (noeuds, arcs, processeurs, ...)

Il s'agit d'un problème de transport il faut que je trouve le chemin le plus court entre un point A et un point B dans un graphe orienté en respectant une date de départ et d'arrivé. Par contre, ce qui pose problème c'est qu'il y a plusieurs départs du point A qui permet d'arrivé à un point intermédiaire, par exemple pour le train j'ai plusieurs trains qui peuvent partir de Paris pour allait à Marseille en passant par Lyon à des horaires différentes. Concernant la taille du problème, il n'y a pas de limitation de taille du graphe.