Introduction aux problématiques de cheminement

Les problèmes de recherche du plus court chemin se divisent principalement en deux catégories, selon que l'on considère une source unique ou toutes les paires de sommets. Le choix de l'algorithme dépend de la densité du graphe (nombre d'arêtes $m$ par rapport au nombre de nœuds $n$) et de la présence de poids négatifs.

• Source unique (SSSP) : Calcul de la distance d'un point $A$ vers tous les autres points du graphe.
  • Poids positifs uniquement : Dijkstra (versions naïve ou optimisée par tas).
  • Poids négatifs autorisés : Bellman-Ford ou SPFA.
• Toutes paires (APSP) : Calcul de la distance entre n'importe quel couple de sommets $(i, j)$.
  • Algorithme de référence : Floyd-Warshall.

1. Dijkstra Classique (Graphes Denses)

Adapté lorsque le nombre d'arêtes est proche de $n^2$. On utilise une matrice d'adjacence. La complexité est de $O(n^2)$.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
int adjMatrix[505][505];
int minDistance[505];
bool finalized[505];
int nodeCount, edgeCount;

int solveDijkstra() {
    fill(minDistance, minDistance + nodeCount + 1, INF);
    minDistance[1] = 0;

    for (int i = 0; i < nodeCount; ++i) {
        int current = -1;
        for (int j = 1; j <= nodeCount; ++j) {
            if (!finalized[j] && (current == -1 || minDistance[j] < minDistance[current]))
                current = j;
        }

        if (current == -1 || minDistance[current] == INF) break;
        finalized[current] = true;

        for (int j = 1; j <= nodeCount; ++j) {
            minDistance[j] = min(minDistance[j], minDistance[current] + adjMatrix[current][j]);
        }
    }

    return (minDistance[nodeCount] == INF) ? -1 : minDistance[nodeCount];
}

2. Dijkstra avec Tas Binaire (Graphes Creux)

Pour les graphes où $m \ll n^2$, l'utilisation d'une file de priorité réduit la complexité à $O(m \log n)$. On privilégie ici une liste d'adjacence.

#include <queue>
#include <vector>

struct Edge {
    int to, weight;
};

typedef pair<int, int> PII; // {distance, node}
vector<Edge> graph[100005];
int distArr[100005];
bool visited[100005];

int dijkstraHeap() {
    fill(distArr, distArr + nodeCount + 1, INF);
    priority_queue<PII, vector<PII>, greater<PII>> pq;

    distArr[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (auto &edge : graph[u]) {
            if (distArr[edge.to] > d + edge.weight) {
                distArr[edge.to] = d + edge.weight;
                pq.push({distArr[edge.to], edge.to});
            }
        }
    }
    return (distArr[nodeCount] == INF) ? -1 : distArr[nodeCount];
}

3. Algorithme de Bellman-Ford

Essentiel pour les graphes contenant des arêtes de poids négatif. Il permet également de limiter le nombre d'étapes (nombre d'arêtes empruntées), ce qui est utile pour certaines contraintes métier.

struct Road {
    int u, v, cost;
};

vector<Road> roads;
int pathDist[505], lastDist[505];

int bellmanFord(int maxEdges) {
    fill(pathDist, pathDist + nodeCount + 1, INF);
    pathDist[1] = 0;

    for (int i = 0; i < maxEdges; ++i) {
        copy(pathDist, pathDist + nodeCount + 1, lastDist);
        for (auto &r : roads) {
            if (lastDist[r.u] < INF / 2) { // Evite les relaxations depuis l'infini
                pathDist[r.v] = min(pathDist[r.v], lastDist[r.u] + r.cost);
            }
        }
    }
    return (pathDist[nodeCount] > INF / 2) ? -1 : pathDist[nodeCount];
}

4. Algorithme SPFA (Shrotest Path Faster Algorithm)

Il s'agit d'une optimisation de Bellman-Ford utilisant une file pour ne relaxer que les sommets dont la distance a été mise à jour. Bien que sa complexité théorique pire cas soit $O(nm)$, il est extrêmement performant en pratique ($O(m)$ en moyenne).

int spfa() {
    queue<int> q;
    vector<int> d(nodeCount + 1, INF);
    vector<bool> inQueue(nodeCount + 1, false);

    d[1] = 0;
    q.push(1);
    inQueue[1] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        for (auto &edge : graph[u]) {
            if (d[edge.to] > d[u] + edge.weight) {
                d[edge.to] = d[u] + edge.weight;
                if (!inQueue[edge.to]) {
                    q.push(edge.to);
                    inQueue[edge.to] = true;
                }
            }
        }
    }
    return d[nodeCount];
}

Pour détecter un cycle négatif, il suffit de maintenir un compteru d'arêtes pour chaque chemin. Si un sommet est relaxé plus de $n-1$ fois, un cycle négatif existe.

5. Algorithme de Floyd-Warshall

Utilisé pour calculer les distances entre toutes les paires de nœuds. Sa structure repose sur la programmation dynamique. Sa complexité est de $O(n^3)$, ce qui limite son usage à $n \le 500$ environ.

void floydWarshall() {
    for (int k = 1; k <= nodeCount; ++k) {
        for (int i = 1; i <= nodeCount; ++i) {
            for (int j = 1; j <= nodeCount; ++j) {
                if (adjMatrix[i][k] != INF && adjMatrix[k][j] != INF) {
                    adjMatrix[i][j] = min(adjMatrix[i][j], adjMatrix[i][k] + adjMatrix[k][j]);
                }
            }
        }
    }
}

Critères de sélection

Le choix de l'algorithme doit être guidé par les contraintes de l'énoncé :

• Dijkstra Naïf : Graphe dense, pas de poids négatifs.
• Dijkstra Tas : Graphe creux, pas de poids négatifs.
• Bellman-Ford : Poids négatifs, limite explicite sur le nombre d'arêtes.
• SPFA : Poids négatifs, recherche de cycles négatifs, ou optimisation générale de Bellman-Ford.
• Floyd-Warshall : Plusieurs sources et destinations, petit nombre de sommets.