Algorithme de Dijkstra et plus court chemin

[invite09e593f7]

Bonjour. Je travaille actuellement, dans le cadre d'un tipe, sur l'algorithme de Dijkstra, qui est censé donné le plus court chemin entre deux sommets d'un graphe.
Je ne suis pas un As en programmation, mais si j'ai bien compris, le principe de cet algorithme est de calculer la distance minimale de chaque sommet à la source. Ainsi grâce au point d'arrivé on retrouve le chemin le plus court en remontant de prédécesseur en prédécesseur jusqu'à la source.
Donc j'en déduit que la somme des plus courts chemins est le plus court chemin.

Mais est-ce vraiment le chemin le plus court?

Car je crois avoir trouvé un contre exemple.



J'ai pris le chemin le plus court pour aller au sommet suivant, et on s'aperçoit qu'il y a une intersection de deux arcs. Or un théorème dit que s'il y a a une intersection alors il existe un chemin plus court sans intersection.

J'aimerais avoir vos avis, et savoir si je pense mal.

Merci à tous.
-----

[invite35452583]

Donc j'en déduit que la somme des plus courts chemins est le plus court chemin.

Dis ainsi c'est maladroit car on peut avoir A-B-C est le plus court chemin pour aller de A à C, C-D est le plus court chemin pour aller de C à D mais A-B-C-D n'est pas nécessairement le plus court.
Par contre, si le chemin le plus court entre A et D est par exemple A-E-F-D alors A-E est le plus court chemin pour aller de A à E, idem pour aller de A à F et aussi entre E et F.

J'ai pris le chemin le plus court pour aller au sommet suivant, et on s'aperçoit qu'il y a une intersection de deux arcs. Or un théorème dit que s'il y a a une intersection alors il existe un chemin plus court sans intersection.

La seule intersection sur la figure est celle de [DC] et de [AB]. Mais, cette intersection n'est pas un sommet du graphe. Dans ce cas soit le graphe est mal représenté (et il n'y a en fait pas d'intersection) soit le graphe est mal défini et il faut créer un sommet de plus (l'intersection sus-évoquée).
Ton théorème n'est valide que si deux arêtes ne peuvent s'intersecter qu'en des sommets (ce qui est toujours supposé en fait dans la théorie des graphes à mon avis).

[invite09e593f7]

Ok donc en fait la réciproque que je supposé n'est pas vrai. Il est vrai que dit comme ça cela paré plus intuitif. Merci pour cet éclaircissement. salut

[invitebe0cd90e]

Ton théorème n'est valide que si deux arêtes ne peuvent s'intersecter qu'en des sommets (ce qui est toujours supposé en fait dans la théorie des graphes à mon avis).

Je suis d'accord que le theoreme concerne les intersections qui correspondent a des sommets (puisque "asbtraitement" seuls les relations entre les sommets comptent).

Un graphe peut ne pas etre "representable" sans que des aretes ne se croisent hors sommet (ce qui dans le cas present n'a aucune importance, c'est une remarque générale).

Les graphes qui sont isomorphes a un graphe sans croisements de cette sorte sont dit planaire, c'est une propriété qui peut avoir me semble t il des consequences interressantes.

[A voir en vidéo sur Futura]

[invite35452583]

Je suis d'accord que le theoreme concerne les intersections qui correspondent a des sommets (puisque "asbtraitement" seuls les relations entre les sommets comptent).

Un graphe peut ne pas etre "representable" sans que des aretes ne se croisent hors sommet (ce qui dans le cas present n'a aucune importance, c'est une remarque générale).

Les graphes qui sont isomorphes a un graphe sans croisements de cette sorte sont dit planaire, c'est une propriété qui peut avoir me semble t il des consequences interressantes.

Oui mais il suffit de prendre une surface suffisamment tordue pour pouvoir dessiner le graphe sans croisement autre qu'aux sommets (ruban de Moebius, tore, surface orientée à n "trous"...). (La sphère n'amène rien de plus à ce niveau, si on pique en un point on obtient un plan).

[invitebe0cd90e]

Vu comme ca On peut aussi le plonger dans R^3

[invite35452583]

On peut aussi le plonger dans R^3

En effet