Qu'est-ce qu'un graphe étiqueté ?

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.