Scribd
Importer
16 vues4 pages

Algorithme de Dijkstra en C

Le document présente une implémentation de l'algorithme de Dijkstra en C pour trouver les distances minimales depuis un sommet source dans un graphe non orienté. Il inclut la définition de la matrice d'adjacence, l'initialisation des distances, et la logique pour mettre à jour les distances minimales. L'utilisateur peut entrer le nombre de sommets, le nombre d'arcs, et les détails des arcs pour exécuter l'algorithme.

Transféré par

dani bashengezi
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
16 vues4 pages

Algorithme de Dijkstra en C

Le document présente une implémentation de l'algorithme de Dijkstra en C pour trouver les distances minimales depuis un sommet source dans un graphe non orienté. Il inclut la définition de la matrice d'adjacence, l'initialisation des distances, et la logique pour mettre à jour les distances minimales. L'utilisateur peut entrer le nombre de sommets, le nombre d'arcs, et les détails des arcs pour exécuter l'algorithme.

Transféré par

dani bashengezi
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

#include <stdio.

h>

#include <limits.h>

#define MAX 100

#define INF 99999

int n; // nombre de sommets

int graph[MAX][MAX]; // matrice d'adjacence

// Fonction pour trouver le sommet avec la plus petite distance

int minDistance(int dist[], int visited[]) {

int min = INF, min_index = -1;

for (int v = 0; v < n; v++) {

if (!visited[v] && dist[v] <= min) {

min = dist[v];

min_index = v;

return min_index;

// Fonction de Dijkstra

void dijkstra(int src) {

int dist[MAX]; // distance minimale de src à chaque sommet

int visited[MAX] = {0}; // marque les sommets visités


// Initialisation des distances

for (int i = 0; i < n; i++)

dist[i] = INF;

dist[src] = 0;

// Calcul des distances minimales

for (int count = 0; count < n - 1; count++) {

int u = minDistance(dist, visited);

if (u == -1) break; // plus aucun sommet atteignable

visited[u] = 1;

for (int v = 0; v < n; v++) {

if (!visited[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

// Affichage des résultats

printf("Sommet\tDistance depuis %d\n", src);

for (int i = 0; i < n; i++) {

if (dist[i] == INF)

printf("%d\tINF\n", i);

else

printf("%d\t%d\n", i, dist[i]);
}

int main() {

int m, u, v, poids, src;

printf("Entrer le nombre de sommets : ");

scanf("%d", &n);

printf("Entrer le nombre d’arcs : ");

scanf("%d", &m);

// Initialiser la matrice

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

graph[i][j] = 0;

// Lire les arcs

for (int i = 0; i < m; i++) {

printf("Arc %d (u v poids) : ", i + 1);

scanf("%d %d %d", &u, &v, &poids);

graph[u][v] = poids;

graph[v][u] = poids; // graphe non orienté

}
printf("Sommet de départ : ");

scanf("%d", &src);

dijkstra(src);

return 0;

Vous aimerez peut-être aussi