Finding alternate paths using Dijkstra algorithm

[vikashkumar051]

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

[grumpier]

The whole point of Dijkstra's algorithm is to find a least cost (or shortest, in your case) path.

Once you have a first path, eliminate one of the nodes (C2, C5, or C10 in your example) on that path from the graph, and run Dijkstra's algorithm again. If the resultant path has a higher cost than your first one, put the node back, eliminate another node, and try again until the resultant path has same (or similar) cost to the first. Repeat this as often as necessary.

This isn't exactly inexpensive for large graphs (necessary to run Dijkstra's algorithm a number of times) and needs to be done systematically, but it will work.

[vikashkumar051]

Can you please paste here exact code for doing it.

Thanks
Vikash

[grumpier]

Can you please paste here exact code for doing it

You have a description of one possible approach; consider coding it up as an exercise.

[vikashkumar051]

I am unable to go ahead, I'm stuck. Can you please paste here exact code for solving the above scenario.

Thanks
Vikash

[MosaicFuneral]

uhmm.. No.
Learn to code, or at least use a search engine.

[vikashkumar051]

ok, no problem. I thought that may be anyone of you can solve the scenario. First I always try to use search engine, as I was not able to get the solution thats why I posted my problem here, but its ok no problem.

Thanks
Vikash