Analyseur de théorie des graphes

Fonctionnalités et exemple concret

Cet outil vous aide à résoudre des problèmes de plus court chemin dans un graphe non orienté. Il utilise l'algorithme de Dijkstra, ce qui implique que les poids négatifs ne sont pas acceptés, mais les poids nuls sont autorisés.

Exemple de travail

Considérons les arêtes suivantes :

A,B,2
B,C,3
A,C,10

Si vous choisissez A comme départ et C comme arrivée, l'outil affichera une distance de 5 et le chemin A → B → C.

Paramètres et limites

• Nombre d'arêtes : entre 1 et 1000.
• Nombre maximal de nœuds distincts : 500.
• Les arêtes sont non orientées et les entrées parallèles sont autorisées.
• Seuls les espaces au début et à la fin des noms de nœuds sont supprimés.
• Le nœud de départ et d'arrivée doivent apparaître dans la liste des arêtes.
• Si aucun chemin n'existe, un message explicite est affiché.

Limitations importantes

Cet outil ne prend pas en charge les graphes orientés, la visualisation de coordonnées, les mesures de centralité, les arbres couvrants minimaux ou les algorithmes avec arêtes négatives. Il ne fournit qu'un seul plus court chemin, même s'il en existe plusieurs.

FAQ

Puis-je utiliser des poids négatifs ?

Non, l'algorithme de Dijkstra ne fonctionne pas avec des poids négatifs. Les poids négatifs sont rejetés, mais les poids nuls sont autorisés.

Que se passe-t-il si je saisis plus de 1000 arêtes ?

L'outil est limité à 1000 arêtes. Vous devez réduire votre saisie à cette limite ou moins.

Comment sont traités les espaces dans les noms de nœuds ?

Les espaces en début et fin de chaque nom de nœud sont supprimés. Par exemple, " A " devient "A".

Séparez les champs par des virgules ASCII et utilisez le point décimal pour les poids. A,B vaut 1 ; A,B, vaut actuellement 0 : indiquez donc le poids explicitement. Les lignes vides sont ignorées. Les noms sont sensibles à la casse ; seuls les espaces extérieurs sont retirés, et les virgules sont interdites dans un nom. Un départ identique à l’arrivée donne 0 et ce nœud comme chemin. Le total inclut tous les nœuds listés. Les sommes flottantes peuvent être arrondies ; une distance accessible hors plage finie produit une erreur numérique.