0

Hi,

I am pasting here code for finding path using Dijkstra algorithm.

```
#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;
typedef enum { C1, C2, C3, C4, C5, C6, C7, C8, C9, C10, C11, C12, C13, C14, nonexistent} vertex;
const vertex first_vertex = C1;
const vertex last_vertex = C14;
#define no_vertices 14
string name[] = {"C1","C2","C3","C4", "C5", "C6", "C7", "C8", "C9", "C10", "C11", "C12", "C13", "C14"};
value weight[no_vertices][no_vertices] =
{
/* C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 */
{ 0, 10, oo, oo, 10, oo, oo, oo, oo, oo, oo, oo, oo, oo }, // C1
{ 10, 0, 10, oo, 10, 10, oo, oo, oo, oo, oo, oo, oo, oo }, // C2
{ oo, 10, 0, 10, oo, 10, 10, oo, oo, oo, oo, oo, oo, oo }, // C3
{ oo, oo, 10, 0, oo, oo, 10, oo, oo, oo, oo, oo, oo, oo }, // C4
{ 10, 10, oo, oo, 0, 10, oo, 10, 10, oo, oo, oo, oo, oo }, // C5
{ oo, 10, 10, oo, 10, 0, 10, oo, 10, 10, oo, oo, oo, oo }, // C6
{ oo, oo, 10, 10, oo, 10, 0, oo, oo, 10, 10, oo, oo, oo }, // C7
{ oo, oo, oo, oo, 10, oo, oo, 0, 10, oo, oo, 10, oo, oo }, // C8
{ oo, oo, oo, oo, 10, 10, oo, 10, 0, 10, oo, 10, 10, oo }, // C9
{ oo, oo, oo, oo, oo, 10, 10, oo, 10, 0, 10, oo, 10, 10 }, // C10
{ oo, oo, oo, oo, oo, oo, 10, oo, oo, 10, 0, oo, oo, 10 }, // C11
{ oo, oo, oo, oo, oo, oo, oo, 10, 10, oo, oo, 0, 10, oo }, // C12
{ oo, oo, oo, oo, oo, oo, oo, oo, 10, 10, oo, 10, 0, 10 }, // C13
{ oo, oo, oo, oo, oo, oo, oo, oo, oo, 10, 10, oo, 10, 0 } // C14
};
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* The implementation of Dijkstra's algorithm starts here. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
value D[no_vertices];
bool tight[no_vertices];
vertex predecessor[no_vertices];
vertex minimal_nontight() {
vertex j, u;
for (j = first_vertex; j <= last_vertex; j++)
if (!tight[j])
break;
assert(j <= last_vertex);
u = j;
for (j++; j <= last_vertex; j++)
if (!tight[j] && D[j] < D[u])
u = j;
return u;
}
bool successor(vertex u, vertex z) {
return (weight[u][z] != oo && u != z);
}
void dijkstra(vertex s) {
vertex z, u;
int i;
D[s] = 0;
for (z = first_vertex; z <= last_vertex; z++) {
if (z != s)
D[z] = oo;
tight[z] = false;
predecessor[z] = nonexistent;
}
for (i = 0; i < no_vertices; i++) {
u = minimal_nontight();
tight[u] = true;
if (D[u] == oo)
continue; /* to next iteration ofthe for loop */
for (z = first_vertex; z <= last_vertex; z++)
if (successor(u,z) && !tight[z] && D[u] + weight[u][z] < D[z]) {
D[z] = D[u] + weight[u][z]; /* Shortcut found. */
predecessor[z] = u;
}
}
}
#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);
stack[sp] = u;
sp++;
}
bool stack_empty() {
return (sp == 0);
}
vertex pop() {
assert(!stack_empty());
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(C1,C14);
return 0; /* Return gracefully to the caller of the program
(provided the assertions above haven't failed). */
}
/* End of program. */
```

This is the output you get when you run the program:

```
The shortest path from C1 to C14 is:
C1 C2 C6 C10 C14.
```

**I want other paths which are also shortest should be printed.
that is, below path should also be printed**

```
C1 C5 C6 C10 C14
C1 C5 C9 C10 C14
C1 C5 C9 C13 C14
```

Thanks in advance

Vikash