0x61 Chemins les plus courts
Algorithmes source unique
Algorithme de Dijkstra : Pour un graphe avec des poids d'arêtes non négatifs, cet algorithme calcule les distances les plus courtes depuis un sommet source. Il fonctionne par sélection gloutonne : à chaque itération, le sommet non visité avec la distance la plus faible est choisi, puis on met à jour ses voisins via des relaxations. La complexité est de O(n^2) pour la version naïve, ou O((m + n) log n) avec un tas binaire pour l'optimisation.
#include <queue>
#include <vector>
#include <climits>
const int N_MAX = 1000;
const int INFINI = INT_MAX;
int dist[N_MAX];
bool visite[N_MAX];
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> file_priorite;
void dijkstra(int source, const std::vector<std::vector<std::pair<int, int>>>& graphe) {
for (int i = 0; i < N_MAX; ++i) dist[i] = INFINI;
dist[source] = 0;
file_priorite.push({0, source});
while (!file_priorite.empty()) {
auto [d, u] = file_priorite.top();
file_priorite.pop();
if (visite[u]) continue;
visite[u] = true;
for (const auto& [v, poids] : graphe[u]) {
if (dist[v] > dist[u] + poids) {
dist[v] = dist[u] + poids;
file_priorite.push({dist[v], v});
}
}
}
}
Algorithme de Bellman-Ford : Basé sur la relaxation itérative de toutes les arêtes, il détecte les cycles de poids négatif et calcule les plus courts chemins. L'algorithme nécessite au plus n-1 itérations, avec une complexité O(nm).
Algorithme SPFA : Une optimisation de Bellman-Ford utilisant une file d'attente pour les sommets modifiés. La complexité moyenne est O(km), où k est une petite constante.
#include <queue>
#include <vector>
#include <climits>
int dist[N_MAX];
bool en_queue[N_MAX];
std::queue<int> file;
void spfa(int source, const std::vector<std::vector<std::pair<int, int>>>& graphe) {
for (int i = 0; i < N_MAX; ++i) dist[i] = INFINI;
dist[source] = 0;
file.push(source);
en_queue[source] = true;
while (!file.empty()) {
int u = file.front();
file.pop();
en_queue[u] = false;
for (const auto& [v, poids] : graphe[u]) {
if (dist[v] > dist[u] + poids) {
dist[v] = dist[u] + poids;
if (!en_queue[v]) {
file.push(v);
en_queue[v] = true;
}
}
}
}
}
Problème d'exemple : Chemins avec coûts limités : Pour un graphe où l'on peut rendre jusqu'à k arêtes gratuites, on utilise une approche de programmation dynamique sur une couche. Soit dp[x][p] le coût maximum minimal pour atteindre x avec p arêtes gratuites. On met à jour via SPFA sur les états (sommet, nombre d'arêtes gratuites).
// Exemple simplifié avec dp sur couches
#include <queue>
#include <algorithm>
#include <vector>
const int N = 1000, K = 1000, INFINI = 1e9;
int dp[N][K+1];
bool marque[N][K+1];
std::queue<std::pair<int, int>> file;
void spfa_couche(int source, int max_k, const std::vector<std::vector<std::pair<int, int>>>& graphe) {
for (int i = 0; i < N; ++i) for (int j = 0; j <= max_k; ++j) dp[i][j] = INFINI;
dp[source][0] = 0;
file.push({source, 0});
marque[source][0] = true;
while (!file.empty()) {
auto [u, p] = file.front();
file.pop();
marque[u][p] = false;
for (const auto& [v, poids] : graphe[u]) {
// Cas sans utiliser l'arête gratuite
if (dp[v][p] > std::max(dp[u][p], poids)) {
dp[v][p] = std::max(dp[u][p], poids);
if (!marque[v][p]) { file.push({v, p}); marque[v][p] = true; }
}
// Cas en utilisant une arête gratuite
if (p < max_k && dp[v][p+1] > dp[u][p]) {
dp[v][p+1] = dp[u][p];
if (!marque[v][p+1]) { file.push({v, p+1}); marque[v][p+1] = true; }
}
}
}
}
Alternative : Binaire + BFS 0-1 : Pour minimiser la (k+1)-ème valeur sur le chemin, on binaire sur la réponse. Vérifier si un chemin existe avec au plus k arêtes de poids supérieur au seuil revient à un BFS 0-1, où les arêtes lourdes ont coût 1 et les autres coût 0. Complexité O((n+m) log n).
Algorithmes tous sommets
Algorithme de Floyd-Warshall : Calcule les plus courts chemins entre toutes les paires de sommets. On utilise la relation de récurrence dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j]). Complexité O(n^3).
int dist[N_MAX][N_MAX];
void floyd(int n) {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
}
Fermeture transitive : Utilisée pour déduire des relations dans un réseau. Avec Floyd-Warshall, on peut vérifier la consistance et le nombre minimal d'inégalités nécessaires.
0x62 Arbres couvrants de poids minimum
Pour un graphe non orienté pondéré, un arbre couvrant de poids minimum connecte tous les sommets avec un poids total minimal.
Algorithme de Kruskal : Trie les arêtes par poids croissant et les ajoute à la forêt couvrante si elles ne forment pas de cycle, en utilisant une structure d'union-find. Complexité O(m log m).
#include <algorithm>
#include <vector>
int parent[N_MAX];
int trouver(int x) { return parent[x] == x ? x : parent[x] = trouver(parent[x]); }
void unir(int x, int y) { parent[trouver(x)] = trouver(y); }
int kruskal(int n, std::vector<std::tuple<int, int, int>>& aretes) {
std::sort(aretes.begin(), aretes.end(), [](const auto& a, const auto& b) {
return std::get<2>(a) < std::get<2>(b);
});
for (int i = 1; i <= n; ++i) parent[i] = i;
int poids_total = 0, compteur = 0;
for (const auto& [u, v, poids] : aretes) {
if (trouver(u) != trouver(v)) {
unir(u, v);
poids_total += poids;
++compteur;
if (compteur == n-1) break;
}
}
return (compteur == n-1) ? poids_total : -1;
}
Algorithme de Prim : Part d'un sommet initial et ajoute itérativement l'arête de moindre poids connectant un sommet de l'arbre à un sommet extérieur. Complexité O(m log n) avec un tas.
#include <queue>
#include <vector>
#include <climits>
int prim(int n, const std::vector<std::vector<std::pair<int, int>>>& graphe) {
std::vector<int> dist(n+1, INT_MAX);
std::vector<bool> dans_arbre(n+1, false);
dist[1] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> file_priorite;
file_priorite.push({0, 1});
int poids_total = 0;
while (!file_priorite.empty()) {
auto [d, u] = file_priorite.top();
file_priorite.pop();
if (dans_arbre[u]) continue;
dans_arbre[u] = true;
poids_total += d;
for (const auto& [v, poids] : graphe[u]) {
if (!dans_arbre[v] && poids < dist[v]) {
dist[v] = poids;
file_priorite.push({poids, v});
}
}
}
return poids_total;
}
Problème d'exemple : Aménagement de routes : Pour contraindre le degré d'un sommet racine, on combine des arbres couvrants partiels avec des remplacements d'arêtes le long de cycles.
0x63 Diamètre d'arbre et ancêtre commun le plus proche
Ancêtre commun le plus proche (LCA)
Algorithme par sauts binaires : Prétraitement des profondeurs et des ancêtres à puissances de deux. On aligne d'abord les profondeurs des deux sommets, puis on remonte ensemble jusqu'à trouver l'ancêtre commun.
#include <vector>
#include <cmath>
const int LOG_MAX = 20;
int profondeur[N_MAX];
int ancetre[N_MAX][LOG_MAX];
void dfs_lca(int u, int p, const std::vector<std::vector<int>>& arbre) {
ancetre[u][0] = p;
for (int j = 1; j < LOG_MAX; ++j)
ancetre[u][j] = ancetre[ancetre[u][j-1]][j-1];
for (int v : arbre[u]) {
if (v != p) {
profondeur[v] = profondeur[u] + 1;
dfs_lca(v, u, arbre);
}
}
}
int lca(int u, int v) {
if (profondeur[u] < profondeur[v]) std::swap(u, v);
for (int j = LOG_MAX-1; j >= 0; --j)
if (profondeur[ancetre[u][j]] >= profondeur[v])
u = ancetre[u][j];
if (u == v) return u;
for (int j = LOG_MAX-1; j >= 0; --j)
if (ancetre[u][j] != ancetre[v][j]) {
u = ancetre[u][j];
v = ancetre[v][j];
}
return ancetre[u][0];
}
0x66 Algorithme de Tarjan et connectivité des graphes non orientés
Sommets et ponts d'articulation : En utilisant un DFS avec temps de découverte (dfn) et valeur de rétroaction (low), on identifie les arêtes critiques.
- Pont : Une arête (x,y) est un pont si dfn[x] < low[y].
- Sommet d'articulation : Un sommet x est un point d'articulation si pour un fils y, dfn[x] <= low[y], avec des cas spéciaux pour la racine.
#include <vector>
#include <stack>
int dfn[N_MAX], low[N_MAX], temps;
std::vector<bool> est_pont;
std::vector<bool> est_sommet_articulation;
void tarjan(int u, int p, const std::vector<std::vector<std::pair<int, int>>>& graphe) {
dfn[u] = low[u] = ++temps;
int enfants = 0;
for (const auto& [v, idx] : graphe[u]) {
if (v == p) continue;
if (!dfn[v]) {
++enfants;
tarjan(v, u, graphe);
low[u] = std::min(low[u], low[v]);
if (low[v] > dfn[u]) est_pont[idx] = true;
if (p != 0 && low[v] >= dfn[u] || p == 0 && enfants > 1)
est_sommet_articulation[u] = true;
} else {
low[u] = std::min(low[u], dfn[v]);
}
}
}
Composantes bi-connexes :
- e-DCC (composantes bi-connexes par arêtes) : En supprimant tous les ponts, chaque composante connexe restante est une e-DCC.
- v-DCC (composantes bi-connexes par sommets) : Utilise une pile pour collecter les sommets lors des détections d'articulation.
std::vector<std::vector<int>> edcc, vdcc;
std::stack<int> pile;
void tarjan_vdcc(int u, int p, const std::vector<std::vector<int>>& graphe) {
dfn[u] = low[u] = ++temps;
pile.push(u);
int enfants = 0;
for (int v : graphe[u]) {
if (v == p) continue;
if (!dfn[v]) {
++enfants;
tarjan_vdcc(v, u, graphe);
low[u] = std::min(low[u], low[v]);
if (low[v] >= dfn[u]) {
std::vector<int> composante;
composante.push_back(u);
int sommet;
do {
sommet = pile.top();
pile.pop();
composante.push_back(sommet);
} while (sommet != v);
vdcc.push_back(composante);
}
} else {
low[u] = std::min(low[u], dfn[v]);
}
}
if (p == 0 && enfants == 0) vdcc.push_back({u}); // Isole
}