Recherche de l'ensemble des plus courts chemins entre 2 noeuds d'un graphe

[invite601a5f00]

Bonsoir,
je dispose d'un graphe d'après le code suivant:

w=[1 1 1 1 1 1];
DG=sparse([1 1 2 2 3 4],[2 3 3 4 5 5],w,5,5);
h = view(biograph(DG,[],'ShowWeights','on'));

Je souhaite déterminer l'ensemble des plus courts chemins pour aller du nœud 2 au nœud 5.
Mais à ma connaissance j'utilise la fonction suivante et dont le résultat est:

[dist, path] = graphshortestpath(DG, 2, 5)

dist =

    2    


path =
    2     3     5

Cette fonction ne me donne qu'un seul chemin alors qu'il y a aussi le chemin 2 4 5.
Je cherche une fonction ou un algorithme me permettant d'avoir tous ces plus courts chemins.
Merci de me répondre.
-----

[invite9dc7b526]

Je vois bien une façon un peu bête de trouver tous ces chemins, en utilisant la fonction que tu as déjà. Si tu as n sommets en plus des sommets A et B qui t'intéressent, tu cherches pour chaque sommet X parmi ces n sommets un plus court chemin de X à A et un plus court chemin de X à B. Tu vérifies que la longueur résultante est bien la longueur minimale. Tu ne rateras aucun chemin de longueur minimale mais tu auras plusieurs fois le même (en général). Ca coûtera 2*n appels de la fonction, plus des tests pour vérifier que tu obtiens de nouveaux chemins. Tu peux gagner un peu de temps, si par exemple le chemin de X à A est déjà plus long que le plus court chemin de A à B alors ce n'est pas la peine de chercher les chemins de X à B.

[invite0bbe92c0]

Il existe un algorithme standard pour ce problème. Il est connu sous le nom d'algorithme de Dijkstra.

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

[invite601a5f00]

Bonsoir,
J'ai l'impression que je ne me suis pas fait bien comprendre.
En fait il arrive souvent que dans un graphe, il existe plusieurs plus courts chemins pour allant d'un nœud source à un nœud destination (comme dans l'exemple que j'ai évoqué). La fonction que j'ai utilisée ne me donne qu’un seul chemin entre ces 2 nœuds. Je voudrai avoir une fonction ou un algorithme qui me permet de lister tous les plus courts chemins entre ces 2 nœuds.
Merci.

[A voir en vidéo sur Futura]

[invitef35ebd48]

Bonjour,

tu peux te baser sur l'algo de Dijkstra et le modifier pour qu'il te retourne plusieurs solutions...en gros tu fais un Dijkstra et dès que t'as trouvé une solution, tu continues à explorer les autres chemin ( ceux qui sont plus court que ta solution).