Pour l'algorithme de Dijkstra, l'algorithme produira le même arbre, quel que soit le nœud choisi comme nœud de départ, à condition qu'aucun des arcs du graphe n'ait le même poids.

Dans un arbre avec sommets, le nombre d'arêtes est :

Si l'on essaye de construire un graphe orienté sans cycle à n sommets ayant le plus long chemin possible, quelle sera la longueur maximum de ce chemin ?

S'agit-il d'un arbre ?

Pour un graphe  avec  nœuds, une étudiante exécute l'algorithme de Bellman-Ford pour itérations. Elle effectue ensuite une itération supplémentaire et remarque que le chemin le plus court entre deux nœuds a diminué. 

Qu'est-ce que cette observation suggère à propos du graphe ?

Quel est le plus court chemin de 0 à 2 ?

Le chemin le plus court d'un nœud source vers tous les autres nœuds dans un graphe restera inchangé si :

Dans un graphe non-orienté et pondéré G, si on suppose que le chemin le plus court entre un sommet source s et un sommet destination t soit correctement calculé à l'aide de l'algorithme de Dijkstra. L'affirmation suivante est-elle vraie ?

Quelles affirmations concernant le graphe suivant sont vraies ?

Si on effectue un parcours en profondeur du graphe de la figure ci-après en partant du sommet 5, lequel des sommets suivants ne peut en aucun cas être visité en dernier ?