Dijkstra

Introduction

La recherche de plus courts chemins dans un graphe est un problème essentiel qui admet de nombreuses solutions plus ou moins exotiques. L'une des plus célèbres est l'algorithme proposé par Edsger Dijkstra que nous allons aborder ici. Commençons par préciser les hypothèses nécessaires à son application :

On fait l'hypothèse que les pondérations des arcs du graphe sont des réels positifs.

Complexité

Lorsqu'on utilise un tas binaire minimal, la complexité de l'algorithme de Dijkstra est en $\small O((N + A) \log A)$ où N désigne le nombre de noeuds du graphe et A le nombre d'arcs. En règle générale, on a donc du $\small O(N \log A)$ .

On peut améliorer cette complexité en utilisant un tas de Fibonacci, auquel cas on obtient du $\small O(N + A \log A)$ , plus performant dans la plupart des configurations.

Pseudo-code

Calcul des distances seul

Soit N le nombre de noeuds
Soit D un tableau de taille N initialisé à +oo
Soit T un tas minimal de couples (noeud, distance) ordonné par distance
Soit A le noeud de départ
 
DIJKSTRA(G)
    T.push(A, 0)
    Tant que T n'est pas vide
        Soit (n, d) = T.pop()
        Si D[n] = +oo
            D[n] = d
            Pour chaque arc de longueur l vers un voisin k de n
                T.push(k, d + l)

Distances avec récupération du chemin

Soit N le nombre de noeuds
Soit A le noeud de départ
Soit D le tableau des distances, initialisé à +oo
Soit P un tableau des parents
Soit T un tas minimal de couples (noeud, distance) ordonné par distance
Soit traité un tableau de N booléens, initialisé à FAUX
 
T.push(A, 0)
Tant que T n'est pas vide
    Soit (n, d) = T.pop()
    Si traité[n] = FAUX
        Pour chaque arc de pondération l vers un voisin k de n
            Si d + l < D[k]
                P[k] = n
                D[k] = d + l
                T <- (k, d + l)
    traité[n] = VRAI

Implémentation

On propose ici un exemple d'implémentation en C++ utilisant le type std::priority_queue de la STL.

#include <queue>
 
const int INFINITY = 1000000000;
const int MAX_NODES = 1000000;
 
//
// Type noeud
// 
// On redéfinit l'opérateur < pour le tas.
// Attention : le tas standard est un tas maximal,
// alors qu'on souhaite un tas minimal.
//
 
struct node_t {
    int id, dist;
 
    node_t(int id, int dist) : id(id), dist(dist)
    {
    }
 
    bool operator < (const node_t &other) const
    {
        return (dist > other.dist);
    }
};
 
//
// Type arc
//
// Une liste chaînée classique.
// Voir l'article dédié pour les détails d'implémentation.
//
 
struct edge_t {
    int dest, dist;
    edge_t *next;
};
 
edge_t *edges[MAX_NODES];
int totalDist[MAX_NODES];
 
void Init()
{
    for (int node = 0; node < MAX_NODES; node++)
        totalDist[node] = INFINITY;
}
 
void Dijkstra(int from)
{
    std::priority_queue <node_t> heap;
    heap.push(node_t(from, 0));
 
    while (!heap.empty()) {
        node_t curNode = heap.top();
        heap.pop();
        if (totalDist[curNode.id] < INFINITY)
            continue;
        totalDist[curNode.id] = curNode.dist;
        for (edge_t *curEdge = edges[curNode.id]; curEdge; curEdge = curEdge->next)
            heap.push(node_t(curEdge->dest, curNode.dist + curEdge->dist));
    }
}