Le problème est défini dans un graphe orienté. Si tu cherches des chemins dans un graphe non orienté, il faut que tu définisses l'orientation. Tu peux par exemple remplacer chaque arête de ton graphe non orienté par deux arcs pour autoriser les deux directions. Ensuite tu peux appliquer l'algorithme. Est ce que cela t'aide ? Bonne journée !
Bonjour Mohamed, Oui si tu as un graphe non-orienté G, tu peux construire un graphe orienté G' dans lequel tu mets les deux arcs i->j et j->i pour chaque arête i-j de G et tu appliques Bellman-Ford dans G'. Attention du coup cela ne fonctionne pas si tu as des distances négatives dans G car cela te crée immédiatement un circuit négatif dans G'.
bonjour, merci pour cette vidéo qui m’a permis de comprendre le fonctionnement de l’algorithme. Il m’a manqué juste un élément : le PCC à la fin, après avoir complété la matrice, avoir l’identification du PCC : est-ce s-b-d ? s-c-e ? etc… cette dernière étape n’est pas claire pour moi.
Bonjour, oui je n'aborde pas l'extraction de la solution elle même dans cette vidéo. En fait, l'algorithme permet d'obtenir l'arborescence des plus courts chemins qui donne tous les PCCs de s vers tout autre sommet. Dans ce cas, on aurait l'arborescence ou "l'arbre orienté": {(s,c), (c,b), (b,e), (b,d)} donc on y trouve le PCC de s vers e: s->c->b->e mais aussi celui de s vers d: s->c->b->d et ainsi de suite. Pour avoir cette arborescence, il suffit de stocker dans une matrice P le prédécesseur de chaque sommet chaque fois qu'une mise à jour est faite. Ainsi quand la valeur phi[i,v] est mise à jour à partir de u, on stocke P[i,v] = u. Et la dernière ligne de cette matrice nous donne la solution (les PCC de s vers TOUT autre sommet): P[4,s] = -; P[4,b] = c; P[4,c] = s; P[4,d] = b; P[4,e] = b
Bonjour Tama, Cet algorithme sert à calculer toutes les valeurs des plus courts chemins d'un sommet vers tous les autres. Cela permet notamment d'obtenir un plus court chemin entre deux sommets du graphe. C'est, par exemple, le problème que traite le GPS sur une carte routière. J'espère que cela t'aide.
Merci, votre vidéo m'a beaucoup aidé ! J'espère que vous continuerez :)
Merci infiniment
Merci chef
Merci beaucoup monsieur
Merci 🙏 cousin 👍👍👍👍👍
Merci pour cette vidéo
Mercii
Pourquoi il n'y a pas d'exemple avec un graphe non orienté ?
Le problème est défini dans un graphe orienté. Si tu cherches des chemins dans un graphe non orienté, il faut que tu définisses l'orientation. Tu peux par exemple remplacer chaque arête de ton graphe non orienté par deux arcs pour autoriser les deux directions. Ensuite tu peux appliquer l'algorithme.
Est ce que cela t'aide ?
Bonne journée !
merci bcp
ça marche aussi avec un graphe non-orienté ?
Bonjour Mohamed,
Oui si tu as un graphe non-orienté G, tu peux construire un graphe orienté G' dans lequel tu mets les deux arcs i->j et j->i pour chaque arête i-j de G et tu appliques Bellman-Ford dans G'. Attention du coup cela ne fonctionne pas si tu as des distances négatives dans G car cela te crée immédiatement un circuit négatif dans G'.
Merci
bonjour, merci pour cette vidéo qui m’a permis de comprendre le fonctionnement de l’algorithme. Il m’a manqué juste un élément : le PCC à la fin, après avoir complété la matrice, avoir l’identification du PCC : est-ce s-b-d ? s-c-e ? etc… cette dernière étape n’est pas claire pour moi.
Bonjour, oui je n'aborde pas l'extraction de la solution elle même dans cette vidéo. En fait, l'algorithme permet d'obtenir l'arborescence des plus courts chemins qui donne tous les PCCs de s vers tout autre sommet. Dans ce cas, on aurait l'arborescence ou "l'arbre orienté": {(s,c), (c,b), (b,e), (b,d)} donc on y trouve le PCC de s vers e: s->c->b->e mais aussi celui de s vers d: s->c->b->d et ainsi de suite.
Pour avoir cette arborescence, il suffit de stocker dans une matrice P le prédécesseur de chaque sommet chaque fois qu'une mise à jour est faite. Ainsi quand la valeur phi[i,v] est mise à jour à partir de u, on stocke P[i,v] = u. Et la dernière ligne de cette matrice nous donne la solution (les PCC de s vers TOUT autre sommet):
P[4,s] = -; P[4,b] = c; P[4,c] = s; P[4,d] = b; P[4,e] = b
J'ai une question
Où cette programmation on va utiliser ?
Et on fait quoi avec cette programmation ?
Bonjour Tama,
Cet algorithme sert à calculer toutes les valeurs des plus courts chemins d'un sommet vers tous les autres. Cela permet notamment d'obtenir un plus court chemin entre deux sommets du graphe. C'est, par exemple, le problème que traite le GPS sur une carte routière.
J'espère que cela t'aide.
C'est utilisé en informatique réseau aussi
Svp besoin d'un cours résumé en Recherche opérationnelle
Bonjour Séverin,
Désolé je n'ai pas ça en stock.
Bon courage pour tes révisions !
Hadrien