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
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
|
#include <stdio.h>
#include <limits.h>
#include <assert.h>
typedef enum {false, true} bool; /* The order is rather important to
get the boolean values right. */
typedef char *string;
#define oo UINT_MAX /* infinity is represented as the maximum unsigned int. */
typedef unsigned int value;
/* Firstly, the type of vertices for our particular graph (which was
given as an example in the lectures). The (non)vertex `nonexistent'
is used in order to indicate that a vertex (un sommet) hasn't got a predecessor
in the path under consideration. See below. */
typedef enum { A, B, C, D, nonexistent} vertex;
/* If you modify the above, in order to consider a different graph,
then you also have to modify the following. */
const vertex first_vertex = A;
const vertex last_vertex = D;
#define no_vertices 4 // nombre de sommets
/* Now a dictionary for output purposes. The order has to match the
above, so that, for example, name[SFO]="SFO". */
string name[] = {"A","B","C","D"};
value weight[no_vertices][no_vertices] =
{
/* A B C D */
{ 0, 1, 2, oo}, /* A */
{ oo, 0, 1, 4}, /* B */
{ oo, oo, 0, 3}, /* C */
{ 2, oo, oo, 0} /* D */
};
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* The implementation of Dijkstra's algorithm starts here. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* We first declare the array (ordre) `array_D' of overestimates, the array `tight' (serré)
which records which of those estimates are actually tight, and the
array `predecessor'. The last has the property that predecessor[z]
is the last vertex visited on the way from the start node to z. */
value array_D[no_vertices]; // coûts ou valeurs
bool tight[no_vertices];
vertex predecessor[no_vertices]; // sommets
/*
We begin with the following auxiliary function, which should be
called only when we know for sure that there is at least one node u
with tight[u] false. Otherwise, the program aborts; this happens
when the assertion below fails.
*/
vertex minimal_nontight() {
vertex j, u;
for (j = first_vertex; j <= last_vertex; j++)
if (!tight[j])
break;
assert(j <= last_vertex); // vérification que j est bien inférieur à last_vertex
u = j;
/* Now u is the first vertex with nontight estimate, but not
necessarily the one with minimal estimate, so we aren't done
yet. */
for (j++; j <= last_vertex; j++)
if (!tight[j] && array_D[j] < array_D[u])
u = j;
/* Having checked all vertices, we now know that u has the required
minimality property. */
return u;
}
/*
The following definition assumes that the graph is directed in
general, which means that it would be wrong to have weight[z][u]
instead. The intended meaning is that the vertex u has the vertex z
as one of its successors. Recall that such a vertex z was
called a neighbour of the vertex u, but this latter terminology is
best reserved for undirected graphs. Notice that the example given
above happens to be undirected. But, as remarked above, this
program is intended to work for directed graphs as well.
*/
bool successor(vertex u, vertex z) {
return (weight[u][z] != oo && u != z);
}
/*
We finally arrive at the main algorithm. This is the same as given
above, now written in C, with the computation of the actual
paths included. The computation of paths is achieved via the use of
the array `predecessor' declared above. Strictly speaking,
Dijkstra's algorithm only records what is needed in order to recover
the path. The actual computation of the path is performed by the
algorithm that follows it.
*/
void dijkstra(vertex s) {
vertex z, u;
int i;
array_D[s] = 0;
for (z = first_vertex; z <= last_vertex; z++) {
if (z != s)
array_D[z] = oo;
tight[z] = false;
predecessor[z] = nonexistent;
}
for (i = 0; i < no_vertices; i++) {
u = minimal_nontight();
tight[u] = true;
/* In a disconnected graph, array_D[u] can be oo. But then we just move
on to the next iteration of the loop. (Can you see why?) */
if (array_D[u] == oo)
continue; /* to next iteration ofthe for loop */
for (z = first_vertex; z <= last_vertex; z++)
if (successor(u,z) && !tight[z] && array_D[u] + weight[u][z] < array_D[z]) {
array_D[z] = array_D[u] + weight[u][z]; /* Shortcut found. */
predecessor[z] = u;
}
}
}
/* The conditions (successor(u,z) && !tight[z]) can be omitted from
the above algorithm without changing its correctness. But I think
that the algorithm is clearer with the conditions included, because
it makes sense to attempt to tighten the estimate for a vertex only
if the vertex is not known to be tight and if the vertex is a
successor of the vertex under consideration. Otherwise, the
condition (array_D[u] + weight[u][z] < array_D[z]) will fail anyway. However,
in practice, it may be more efficient to just remove the conditions
and only perform the test (array_D[u] + weight[u][z] < array_D[z]). */
/* We can now use Dijkstra's algorithm to compute the shortest path
between two given vertices. It is easy to go from the end of the
path to the beginning.
To reverse the situation, we use a stack. Therefore we digress
slightly to implement stacks (of vertices). In practice, one is
likely to use a standard library instead, but, for teaching
purposes, I prefer this program to be selfcontained. */
#define stack_limit 10000 /* Arbitrary choice. Has to be big enough to
accomodate the largest path. */
vertex stack[stack_limit];
unsigned int sp = 0; /* Stack pointer. */
void push(vertex u) {
assert(sp < stack_limit); /* We abort if the limit is exceeded. This
will happen if a path with more
vertices than stack_limit is found. */
stack[sp] = u;
sp++;
}
bool stack_empty() {
return (sp == 0);
}
vertex pop() {
assert(!stack_empty()); /* We abort if the stack is empty. This will
happen if this program has a bug. */
sp--;
return stack[sp];
}
/* End of stack digression and back to printing paths. */
void print_shortest_path(vertex origin, vertex destination) {
vertex v;
assert(origin != nonexistent && destination != nonexistent);
dijkstra(origin);
printf("The shortest path from %s to %s is:\n\n",
name[origin], name[destination]);
for (v = destination; v != origin; v = predecessor[v])
if (v == nonexistent) {
printf("nonexistent (because the graph is disconnected).\n");
return;
}
else
push(v);
push(origin);
while (!stack_empty())
printf(" %s",name[pop()]);
printf(".\n\n");
}
/* We now run an example. */
int main() {
print_shortest_path(C,A); // de C à A
getch();
return 0; /* Return gracefully to the caller of the program
(provided the assertions above haven't failed). */
} |
