Algorithme de Prim pour l'Arbre Couvrnat Minimal (MST)

L'algorithme de Prim est une méthode gloutonne permettant de trouver l'arbre couvrant minimal d'un graphe connexe pondéré. L'implémentation ci-dessous utilise une matrice d'adjacence pour représenter le graphe.

#include <stdio.h>
#include <stdlib.h>

#define VAL_INF 65535
#define MAX_SIZE 1001

typedef struct {
    int nb_nodes;
    int nb_edges;
    int weight_matrix[MAX_SIZE][MAX_SIZE];
} AdjacencyGraph;

AdjacencyGraph* init_graph(int n) {
    AdjacencyGraph* g = (AdjacencyGraph*)malloc(sizeof(AdjacencyGraph));
    g->nb_nodes = n;
    g->nb_edges = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g->weight_matrix[i][j] = VAL_INF;
        }
    }
    return g;
}

void add_edge_undirected(AdjacencyGraph* g, int u, int v, int w) {
    g->weight_matrix[u][v] = w;
    g->weight_matrix[v][u] = w;
}

int get_min_distance_node(AdjacencyGraph* g, int dists[]) {
    int min_val = VAL_INF;
    int target_node = -1;
    for (int i = 0; i < g->nb_nodes; i++) {
        if (dists[i] != -1 && dists[i] < min_val) {
            min_val = dists[i];
            target_node = i;
        }
    }
    return target_node;
}

int execute_prim(AdjacencyGraph* g, int start_node) {
    int dists[MAX_SIZE];
    int total_mst_weight = 0;
    int nodes_included = 0;

    for (int i = 0; i < g->nb_nodes; i++) {
        dists[i] = g->weight_matrix[start_node][i];
    }

    dists[start_node] = -1;
    nodes_included++;

    while (1) {
        int v = get_min_distance_node(g, dists);
        if (v == -1) break;

        total_mst_weight += dists[v];
        dists[v] = -1;
        nodes_included++;

        for (int i = 0; i < g->nb_nodes; i++) {
            if (dists[i] != -1 && g->weight_matrix[v][i] < dists[i]) {
                dists[i] = g->weight_matrix[v][i];
            }
        }
    }

    return (nodes_included < g->nb_nodes) ? -1 : total_mst_weight;
}

Tri Topologique et Réseaux AOV

Un tri topologique est un ordonnancement linéaire des sommets d'un graphe orienté tel que pour chaque arête dirigée allant du sommet U vers le sommet V, U apparaisse avant V dans l'ordonnnancement. Ce concept s'applique aux réseaux AOV (Activity On Vertex). Un graphe possédant un tri topologique est nécessairement un Graphe Orienté Acyclique (DAG).

Chemin Critique et Réseaux AOE

Les réseaux AOE (Activity On Edge) sont utilisés pour la planification de projets. Le chemin critique est la séquence d'activités qui détermine la durée minimale du projet. Il est composé d'activités sans marge de manœuvre (機動時間).

• Temps au plus tôt (Earliest) : \(Earliest[j] = \max_{ \in E} \{Earliest[i] + Cost_{i,j}\}\)
• Temps au plus tard (Latest) : \(Latest[i] = \min_{ \in E} \{Latest[j] - Cost_{i,j}\}\)

Implémentation du Tri Topologique (Liste d'Adjacence)

L'utilisation d'une file d'attente permet de traiter efficacement les sommets ayant un degré entrant de zéro.

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100

typedef struct ArcNode {
    int target;
    int weight;
    struct ArcNode* next;
} ArcNode;

typedef struct {
    ArcNode* first_arc;
    int in_degree;
} VertexNode;

typedef struct {
    VertexNode adj_list[MAX_NODES];
    int n_vtx, n_arc;
} ListGraph;

void build_topo_graph(ListGraph* g) {
    int u, v, w;
    scanf("%d %d", &g->n_vtx, &g->n_arc);
    for (int i = 0; i < g->n_vtx; i++) {
        g->adj_list[i].first_arc = NULL;
        g->adj_list[i].in_degree = 0;
    }
    for (int i = 0; i < g->n_arc; i++) {
        scanf("%d %d %d", &u, &v, &w);
        ArcNode* newNode = (ArcNode*)malloc(sizeof(ArcNode));
        newNode->target = v;
        newNode->weight = w;
        newNode->next = g->adj_list[u].first_arc;
        g->adj_list[u].first_arc = newNode;
        g->adj_list[v].in_degree++;
    }
}

int calculate_earliest_completion(ListGraph* g) {
    int queue[MAX_NODES], front = 0, rear = 0;
    int earliest[MAX_NODES] = {0};
    int count = 0;

    for (int i = 0; i < g->n_vtx; i++) {
        if (g->adj_list[i].in_degree == 0) {
            queue[rear++] = i;
        }
    }

    while (front < rear) {
        int v = queue[front++];
        count++;
        for (ArcNode* arc = g->adj_list[v].first_arc; arc; arc = arc->next) {
            int w = arc->target;
            if (earliest[v] + arc->weight > earliest[w]) {
                earliest[w] = earliest[v] + arc->weight;
            }
            if (--g->adj_list[w].in_degree == 0) {
                queue[rear++] = w;
            }
        }
    }

    if (count != g->n_vtx) return -1;

    int max_time = 0;
    for (int i = 0; i < g->n_vtx; i++) {
        if (earliest[i] > max_time) max_time = earliest[i];
    }
    return max_time;
}

int main() {
    ListGraph g;
    build_topo_graph(&g);
    int result = calculate_earliest_completion(&g);
    if (result == -1) printf("Impossible");
    else printf("%d", result);
    return 0;
}