Salut à tous. Je suis en train de développez un projet en C pour calculer le plus court chemin entre plusieurs gares.
J'ai déjà crée une version de Dijkstra en C (le code est en dessous) qui permet de calculer le plus court chemin entre 2 gares, sauf qu'il y a des contraintes, les horaires de passages et les lignes ;'(
J'ai réfléchi à comment modifier mon algorithme, mais je ne suis pas sûr que ce soit la bonne méthode et je suis un peu perdu dans mes idées.
Voici mon idée, je compte représenter mon réseau ferroviaire sous forme de graphe.

Mon problème commence ici, je ne sais pas quoi choisir comme structure de graphe, soit :
- chaque arête possédera une structure C avec 1) le poids la durée de trajet séparant 2 gares reliées par un chemin, 2) l'horaire à laquelle il est possible de prendre ce chemin, 3) l'horaire d'arrivée, 4) le numéro de la ligne
- chaque arête possédera comme poids la durée de trajet séparant 2 gares reliées par un chemin, et chaque sommet (gares) aura la liste des horaires de départ et d'arrivée avec le numéro des lignes.
Pour info je compte convertir les horaires en minutes pour mettre ça dans un INT ce sera plus simple.
J'aimerai savoir laquelle de ces formes de données sera la plus facile à implémenter dans mon algo de Dijkstra.

Voici le code de mon algo de Dijkstra juste en dessous, j'aimerai savoir ce que je devrai modifier dans mon code pour l'une de ses possibilités si possible OU alors une idée de comment procéder
Pour vous faciliter la lecture et vous faire gagner du temps, voici le prototype des fonctions expliqués qui vont nous intéresser :

void ajouter_sommet(graph_t *g, int i) ajoute la gare (sommet) n° i dans le graphe g, à modifier si je choisis d'ajouter horaire et ligne
ajouter_arete(graph_t *g, int a, int b, int w, int Horaire_voyage) relie 2 gares par un chemin, a gare de départ, b gare d'arrivée, w durée du trajet, et on rajoutera des arguments en plus pour horaire et ligne
void dijkstra(graph_t *g, int a, int b) calcule le plus court chemin entre la gare a et b
void afficher_chemin(graph_t *g, int i) --- g est le pointeur sur graphe du réseau, i est la destination finale, je l'indique car mon dijkstra remonte le chemin à l'envers ^^
Pour infos j'utilise un tas pour stocker les chemins. Les fonctions sont comprises dans le code.

La fonction main illustre un exemple simple, voici le résultat :
Le temps de trajet est de 59 minutes et le chemin emprunté a été
4 2 3 0 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
 
/*
 * Dijkstra.c
 *
 *  Created on: 21 janv. 2017
 *      Author: totor
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
//#include "Dijkstra.h"
 
typedef struct {  // structure d'une arete entrante
	int sommet;
	int poids;
	int Horaire_Passage; // -------------------- Application au réseau ferroviaire ???
	int NumeroLignePrise;
} arete_graphe;
 
typedef struct { // structure du chemin parcouru, mémorise les chemins précédents
	arete_graphe **sommets;
	int arete_l;
	int arete_s;
	int dist;
	int precedent;
	int visite;
} sommet_t;
 
typedef struct {  // Taille et longueur du graphe
	sommet_t **sommets;
	int sommet_l;
	int sommet_s;
	//int Horaire_Passage; // -------------------- Application au réseau ferroviaire ???
	//int NumeroLignePrise;
} graph_t;
 
typedef struct {  //Structure du tas pour organiser données
	int *donnees;
	int *prio;
	int *index;
	int longueur_tas;
	int taille;
} Tas;
 
void ajouter_sommet(graph_t *g, int i) {
	if (g->sommet_s < i + 1) {
		int size = g->sommet_s * 2 > i ? g->sommet_s * 2 : i + 4;
		g->sommets = realloc(g->sommets, size * sizeof(sommet_t *));
		for (int j = g->sommet_s; j < size; j++)
			g->sommets[j] = NULL;
		g->sommet_s = size;
	}
	if (!g->sommets[i]) {
		g->sommets[i] = calloc(1, sizeof(sommet_t));
		g->sommet_l++;
	}
}
 
void ajouter_arete(graph_t *g, int a, int b, int w, int Horaire_voyage) {
	//a = a - 'a';
	//b = b - 'a';
	ajouter_sommet(g, a);
	ajouter_sommet(g, b);
	sommet_t *v = g->sommets[a];
	if (v->arete_l >= v->arete_s) {
		v->arete_s = v->arete_s ? v->arete_s * 2 : 4;
		v->sommets = realloc(v->sommets, v->arete_s * sizeof(arete_graphe *));
	}
	arete_graphe *e = calloc(1, sizeof(arete_graphe));
	e->sommet = b;
	e->poids = w;
	v->sommets[v->arete_l++] = e;
	e->Horaire_Passage = Horaire_voyage;
}
 
Tas *creer_tas(int n) {
	Tas *h = calloc(1, sizeof(Tas));
	h->donnees = calloc(n + 1, sizeof(int));
	h->prio = calloc(n + 1, sizeof(int));
	h->index = calloc(n, sizeof(int));
	return h;
}
 
void decale_tas(Tas *h, int v, int p) {
	int i = h->index[v] == 0 ? ++h->longueur_tas : h->index[v];
	int j = i / 2;
	while (i > 1) {
		if (h->prio[j] < p)
			break;
		h->donnees[i] = h->donnees[j];
		h->prio[i] = h->prio[j];
		h->index[h->donnees[i]] = i;
		i = j;
		j = j / 2;
	}
	h->donnees[i] = v;
	h->prio[i] = p;
	h->index[v] = i;
}
 
int min(Tas *hauteur, int i, int j, int k) {
	int m = i;
	if (j <= hauteur->longueur_tas && hauteur->prio[j] < hauteur->prio[m])
		m = j;
	if (k <= hauteur->longueur_tas && hauteur->prio[k] < hauteur->prio[m])
		m = k;
	return m;
}
 
int Modifier_Tas(Tas *h) {
	int v = h->donnees[1];
	int i = 1;
	while (1) {
		int j = min(h, h->longueur_tas, 2 * i, 2 * i + 1);
		if (j == h->longueur_tas)
			break;
		h->donnees[i] = h->donnees[j];
		h->prio[i] = h->prio[j];
		h->index[h->donnees[i]] = i;
		i = j;
	}
	h->donnees[i] = h->donnees[h->longueur_tas];
	h->prio[i] = h->prio[h->longueur_tas];
	h->index[h->donnees[i]] = i;
	h->longueur_tas--;
	return v;
}
 
void dijkstra(graph_t *g, int a, int b) {
	int i, j;
	//a = a - 'a';
	//b = b - 'a';
	for (i = 0; i < g->sommet_l; i++) {
		sommet_t *v = g->sommets[i];
		v->dist = INT_MAX;
		v->precedent = 0;
		v->visite = 0;
	}
	sommet_t *v = g->sommets[a];
	v->dist = 0;
	Tas *h = creer_tas(g->sommet_l);
	decale_tas(h, a, v->dist);
	while (h->longueur_tas) {
		i = Modifier_Tas(h);
		if (i == b)
			break;
		v = g->sommets[i];
		v->visite = 1;
		for (j = 0; j < v->arete_l; j++) {
			arete_graphe *e = v->sommets[j];
			sommet_t *u = g->sommets[e->sommet];
			if (!u->visite && v->dist + e->poids <= u->dist) {
				u->precedent = i;
				u->dist = v->dist + e->poids;
				decale_tas(h, e->sommet, u->dist);
			}
		}
	}
}
 
void afficher_chemin(graph_t *g, int i) {
	int n, j;
	sommet_t *v, *u;
	//i = i - 'a';
	v = g->sommets[i];
	if (v->dist == INT_MAX) {
		printf("Il n'existe aucun chemin\n");
		return;
	}
	for (n = 1, u = v; u->dist; u = g->sommets[u->precedent], n++)
		;
	char *path = malloc(n);
	path[n - 1] = 'a' + i;
	for (j = 0, u = v; u->dist; u = g->sommets[u->precedent], j++)
		path[n - j - 2] = 'a' + u->precedent;
	//printf("%d %.*s\n", v->distance, n, path); --- Le cas où les sommets sont de type char
	printf("Le temps de trajet est de %d minutes et le chemin emprunté a été\n",
			v->dist);
	for (int i = 0; i < n; i++)
		printf("%d ", path[i] - 'a');    // à modifier pour afficher ligne prise et horaire à la fois
	printf("\n");
}
 
int main() {
	//a=0 b=1 c=2 d=3 e=4 f=5
	graph_t *g = calloc(1, sizeof(graph_t));
	ajouter_arete(g, 4, 1, 7,158);
	ajouter_arete(g, 4, 2, 9,78);
	ajouter_arete(g, 4, 5, 14,48);
	ajouter_arete(g, 1, 2, 10,4848);
	ajouter_arete(g, 1, 3, 15,59);
	ajouter_arete(g, 2, 3, 11,15);
	ajouter_arete(g, 2, 5, 2,58);
	ajouter_arete(g, 3, 0, 6,14);
	//ajouter_arete(g, 0, 5, 9,256);
	ajouter_arete(g,0,6,5,18);
	int a=5, b=6;
	for(int i=0; i<15; i++){
		a=a+1;
		b=b+1;
		ajouter_arete(g,a,b,5,18);
		ajouter_arete(g,a,b,2,18);
	}
	//printf("a=%d\n",a);
	dijkstra(g, 4, a);
	afficher_chemin(g, a);
	return 0;
}