Glossary

Définitions

• Un graphe étiqueté est un graphe où chaque arête est affectée soit d'une chaîne de caractères, soit d'un nombre.
• Un graphe pondéré est un graphe étiqueté où chaque arête est affectée d'un nombre réel positif, appelé poids de cette arête.
• Le poids d'une chaîne est la somme des poids des arêtes qui la composent.
• Une plus courte chaîne entre deux sommets est, parmi les chaînes qui les relient, une chaîne de poids minimum.