Qu'est ce que un graphe?

La figure ci-dessous correspond à la représentation graphique du graphe. Deux éléments importants composent le graphe. Il y a les arêtes et les sommets. Le sommet, ou nœud, est le point de rencontre de plusieurs arêtes. Tandis qu'un arête relie deux sommets entre eux.

Figure 1 - Représentation graphique du graphe

Dans le cas du VAV, les sommets correspondent aux intersections du labyrinthe. Les arêtes, quant à eux, correspondent aux différents chemin possible entre un sommet et les autres qu'il voit. La figure 2 ci-dessous présente la forme que le graphe prend dans un labyrinthe. Les points bleus sont les sommets et les lignes rouges les arêtes.

Figure 2 - Représentation du graphe dans un labyrinthe

Un dernier point doit être éclairci. Pour que l'algorithme de Dijkstra puisse trouver le chemin le plus court entre deux points, il faut associer un poids à chacun des arêtes. Ce poids, dans le cas du VAV, est la distance en pixels entre les deux sommets.