Difference between revisions of "Dijkstra Algorithm Implementation in C/C++"

Latest revision as of 16:41, 22 February 2014

<syntaxhighlight lang="C" name="dijkstra">

1. include<iostream>

using namespace std;

struct vert {

   char neighbour[20];
   int cost[20];
   int nn;
   char name;
   int color;
   int d;
   char pi;

};

int vi = 0; vert vertex[20];

int findi(char a) { int i; for(i = 0; i < vi; i++) if(vertex[i].name == a) return i; return 0; } void dij(char start);

int main() { char b, a,start; int c, d, i, u, w;

cout<<"Enter the edges and weights\n0 to stop:\n"; while(1) { cin >> a; if(a == '0') break; cin >> b; cin >> w; c = 0, d = 0; for(i = 0; i < vi; i++) { if(a == vertex[i].name) { vertex[i].cost[vertex[i].nn] = w; vertex[i].neighbour[vertex[i].nn++] = b; c++; } if(b == vertex[i].name) { d++; } } if(c == 0) { vertex[vi].name = a; vertex[vi].nn = 0; vertex[vi].cost[vertex[vi].nn] = w; vertex[vi++].neighbour[vertex[vi].nn++] = b; } if(d == 0) { vertex[vi++].name = b; vertex[vi].nn = 0; } } cout << "Enter the starting vertex: "; cin >> start; dij(start); cout << endl; }

void dij(char start) { int i; int front = 0, u, c = 0; int queue[50], qi = 0; int s[50], si = 0, j, d; for(i = 0; i < vi; i++) { if(vertex[i].name == start) { vertex[i].d = 0; vertex[i].pi = 0; } else { vertex[i].color = 0; vertex[i].d = 0x7ffffffff; vertex[i].pi = 0; } queue[qi++] = i; } while(front < qi) { for(i = front; i < qi; i++) for(j = front; j < qi-i+front-1; j++) if(vertex[queue[j]].d > vertex[queue[j+1]].d) { u = queue[j]; queue[j] = queue[j+1]; queue[j+1] = u; } u = queue[front++]; s[si++] = u; cout << vertex[u].name << endl; for(i = 0; i < vertex[u].nn; i++) if(vertex[u].cost[i] + vertex[u].d < vertex[findi(vertex[u].neighbour[i])].d) { vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d + vertex[u].cost[i]; vertex[findi(vertex[u].neighbour[i])].pi = u; } } for(i = 0; i < vi; i++) { cout << endl << endl << vertex[i].name << "\t" << vertex[vertex[i].pi].name << endl; } }

</syntaxhighlight>