Aujourd’hui, je vous partage une petite implémentation générique de l’algorithme de Dijkstra , dont l’utilité principale est de déterminer le plus court chemin entre deux points d’un graphe en parcourant la totalité de celui-ci.

L’algorithme

L’algorithme de Dijkstra est un algorithme simple permettant de déterminer le meilleur chemin entre deux points. Vous pouvez trouver son pseudo-code un peu partout sur le net, par exemple sur la page wikipedia qui y est consacrée.

Il n’est pas recommandé lorsque vous souhaitez obtenir un résultat rapide, ou lorsque l’arbre est beaucoup trop grand. Dans ces cas là, un algorithme de la famille du A* sera sûrement plus indiqué. Ceci dit, il est parfait lorsque toutes les possibilités doivent être étudiées. Par exemple, prenons le jeu “Tan network” du site Coding Games. (Pour ceux qui ne connaissent pas, il s’agit d’une plateforme de “jeux de développement”, permettant de mettre en pratique tous types d’algorithmes, le tout sous forme de mini-jeux assez amusants).

Pour celui-ci, un parcours complet du graphe est nécessaire.

L’algorithme générique

Mettons donc en place un Dijkstra générique, prenant en constructeur une liste des nœuds, chacun connaissant ses voisins liés.

public abstract class Dijkstra<TNode>  where TNode : Node
{
    private List<TNode> _Nodes;
    protected Dijkstra(List<TNode> nodes)
    {
        _Nodes = nodes;
    }
    public IList<TNode> GetShortestPath(TNode from, TNode to)
    {
         // ...
    }
    public abstract double GetDist(TNode n1, TNode n2);
}

Notez que c’est au moment de créer cette liste qu’il faudra décider si les liens sont unis ou bidirectionnels (dans le second cas, “noeud1” aura une référence à “noeud2” dans sa liste de nœuds liés, et réciproquement).

Nous n’avons plus qu’à tester tous les nœuds, en réajustant le poids du plus court chemin vers eux, jusqu’à obtenir le meilleur chemin dans la chaine pointant sur le nœud résultat.

var unSeen = new List<TNode>(_Nodes);

from.PathDone = 0;
while (unSeen.Count != 0)
{
    var n1 = unSeen.OrderBy(x => x.PathDone).First();
    unSeen.Remove(n1);
    foreach (var n2 in n1.Linked)
    {
        var dist = n1.PathDone + GetDist(n1, n2 as TNode);

        if (!(n2.PathDone > dist)) continue;

        n2.PathDone = dist;
        n2.Previous = n1;
    }
}
var finalWay = new List<TNode>();
var currNode = to;
while (currNode != from && currNode != null)
{
    finalWay.Add(currNode);
    currNode = currNode.Previous as TNode;
}
if (currNode == from)
{
    finalWay.Add(currNode);
    finalWay.Reverse();
    return finalWay;
}
return new List<TNode>();

Nous conservons une méthode “GetDist” abstraite, qui permettra de calculer la distance entre deux nœuds liés.

L’application spécifique

Il ne nous restera plus qu’à hériter de cette classe pour notre cas particulier, le réseau Tan. On remarque que quelques informations supplémentaires sont également nécessaires sur un nœud, on crée donc la classe fille “TanNode”.

public class TanNode : Node
{
    public TanNode(string nodeText) : base(new List<Node>())
    {
          //....
    }
    
    // ....
    public string ShortName { get; set; }
    public string LongName { get; set; }
    public double Lat { get; set; }
    public double Long { get; set; }
}

Ensuite, on s’occupe d’hériter de la classe “Dijkstra”, pour spécifier ce que l’on souhaite que la méthode “GetDist” calcule. Dans notre cas, une distance entre deux coordonnées “Lat” et “Long”.

public class TanDijkstra : Dijkstra<TanNode>
{
    public TanDijkstra(List<TanNode> nodes) : base(nodes) { }

    public override double GetDist(TanNode n1, TanNode n2)
    {
        var x = (n2.Long - n1.Long) * Math.Cos(Math.PI * (n1.Lat + n2.Lat) / 2);
        var y = n2.Lat - n1.Lat;
        return Math.Sqrt(x * x + y * y) * 6731;
    }
}

Finalement, on utilise un “main” pour appeler cet algorithme et valider son fonctionnement.

var nodes = Init(true);
var algo = new TanDijkstra(nodes);
var result = algo.GetShortestPath(start, end);

if (result.Count == 0)
    Console.WriteLine("IMPOSSIBLE");
else
{
    foreach (var point in result)
    {
        Console.WriteLine(point.LongName);
    }
}

Si vous vous posez des questions sur la méthode “Init (bool)”, regardez la version complète du code disponible sur Github. Celle-ci ne sert qu’à simplifier mes copier-coller entre Visual Studio et le site Coding game, et n’est pas explicité ici car elle n’apporte rien sur l’algorithme en lui même.

Félicitations, vous êtes maintenant capables d’utiliser un algorithme de Dijkstra générique et de le spécialiser en fonction de vos besoins.