plz help me about Dijkstra's algorithm

[abhradwip]

I want to write a program which will find the shortest path between n no. of cities using dijkstra's algorithm ...... but could not do it..... i have written a program which will give the shortest path between finite no. of cities....... plz help me out....... i would also like to know for the states & city names should i use a database.....if so how???? Im giving the prog which ive written...

plz help me with the source code...........

#include <stdio.h>
#include <limits.h>
#include <assert.h>
#include <conio.h>
 
typedef enum {false, true} bool;
typedef char *string;
 
 
#define oo UINT_MAX 
 
typedef unsigned int value;
 
typedef enum { KOLKATA, MUMBAI, CHENNAI, BANGALORE, PUNE, DELHI, BHUBANESWAR, HYDERBAAD, nonexistent} vertex;
 
const vertex first_vertex = KOLKATA;
const vertex last_vertex = HYDERBAAD;
 
#define no_vertices 8 
 
 
 
string name[] = {"KOLKATA","MUMBAI","CHENNAI","BANGALORE","PUNE","DELHI", "BHUBANESWAR", "HYDERBAAD"};
 
 
 
 
value weight[no_vertices][no_vertices] =
  {
   /*  KOLKATA  MUMBAI CHENNAI BANGALORE  PUNE DELHI BHUBANESWAR HYDERBAAD  */
    {    0,   339,  2555,    oo,    oo,    oo,    oo,    oo}, /* KOLKATA */
    {   oo,    0,   337,  1843,    oo,    oo,    oo,    oo}, /* MUMBAI */
    { 2555,  337,     0,  1743,  1233,    oo,    oo,    oo}, /* CHENNAI */
    {   oo, 1843,  1743,     0,   802,    oo,   849,    oo}, /* BANGALORE */
    {   oo,   oo,  1233,   802,     0,  1387,    oo,  1120}, /* PUNE */
    {   oo,   oo,    oo,    oo,  1387,     0,   142,  1099}, /* DELHI */
    {   oo,   oo,    oo,   849,    oo,   142,     0,  1205}, /* BHUBANESWAR */
    {   oo,   oo,    oo,    oo,  1120,  1099,   1205,    0}  /* HYDERBAAD */
  };
 
 
 
 
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); /* 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() {
  clrscr();
  print_shortest_path(KOLKATA,PUNE);
   getch();
  return 0; /* Return gracefully to the caller of the program
           (provided the assertions above haven't failed). */
}

[sicarie]

So what are you having trouble with? Are you getting any errors, and if so, what are they? Or are you just not getting a correct answer, and what inputs are you using?

[abhradwip]

no.....actually i have done this program for only 8 cities....& have defined the aadjacent matrix within the code...... im getting the output correctly ....but if i want this program for n number of cities, then what to do?

[DeMan]

It may be tedious, but you could use linked lists instead of arrays, otherwise, if there are n cities (and if you don't know what n is) they must come from somwhere (eg std input), you can count them as there input (storing them temporarily in a linked list), and then create matrices the size you like afterward....

Alternatively (assuming you're allowed to get rid of the matrix), you create a graph. A graph is like a linked list, but can go in more than 2 directions (so it contains a linked list of neighbors, say). Any Node stores only the cities it Neighbors, along with the weight for that particular city. This would also modify your code for Djikstra's alg, but it would probably be more efficient, because you only need to try the routes that are possible (that is, you know that a tight node will always be in the list of the current node).

Hope this is helpful, if not (I know I can be confusing) please post again....

[abhradwip]

thanx buddy.......... ......for your help...but the thing is that its little bit confusing.....

let me tell you the problem.....

suppose there is a chart like this

Source Destination

State City Area State City Area

now i have to find the shortest path from same city but different area....or different city & area..... like a flight journey...

buddy this is my main project...& i have to submit it on monday

If u can Plz help me with the source code......im very confused....... plz help me

[DeMan]

You can find the details of Djikstra's algorithmhere

in other words....
Take the Node along the shortest path from the curerent Node (this is why we stored the weights in the Node) and add him to an "active Nodes" storing also the total weight to get this far. Choose the next shortest total path (which may be the shortest node at your new node, or the second shortest at your old one)....Continu e to do this until you arrive at your destination

[abhradwip]

i am getting u ......... but to build this algo..is a very tough task.......that s yyy im requesting u to plz provide me with the code.....for n no. of cities.

[Roonie]

- ahem -

you learning how to build tough algorithms yourself is what its all about. if you dont really want to learn how to program, you should not be doing it.

[DeMan]

As Roonie said, we can offer help, but ultimately you still have to do the work. Perhaps if you can explain where the difficulty lies, we may be able to help you through it.

Alternatively, if you can attempt the problem (and find it doesn't compile, it gives unsexpected output etc), we may be able to help you fix some of the problems.

Maybe to begibn with, you should consider what sort of methods you might need and what they would do. You should also consider Data Structures you may need and how you would go about im[plementing them.
Then you can try to convert the algorithm on the net (or my english version) into some form of pseudocode to work out what you are doing.....

Hope this helps