Re: dijkstra algorithm issue

On May 25, 3:00 am, programming <periklis.ioan...@xxxxxxxxx> wrote:
Hi all,

I am just trying to implement Dijkstra's algorithm but i am not sure
if how i am implementing is correct . My adjecency list is working,
just need to make sure that i am going the right way of implementing
the algorithm. Does anybody have any suggestions on how i can tackle
and debug the algorithm??

Cheers,

Peri.

#include <stdio.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "list.h"

int main()
{
int n_vertices;
int i,j;
int edges;
int w,v;
int start;
/*int MAXINT = 100007;*/

node_ptr *g;

printf("Please enter the number of vertices?");
scanf("%d", &n_vertices);

/*allocate memory for a dynamically allocated array for the
size of n_vertices*/
g = (node_ptr *)malloc(n_vertices * sizeof(node_ptr));

/* loop for the number of vertices created by user*/
for(i=0;i<n_vertices;i++)
{
if(!n_vertices) break; /* break out of loop when n is
0 */

printf("Please enter number of edges?");
scanf("%d", &edges);
/* create a adjacency list for the for each array
element */
g[i] = create();

/* for loop the amount of edges a user has chosen */
for(j = 0;j<edges;j++)
{
/* user input for weight and vertex*/
scanf("%d", &w);
scanf("%d", &v);
/* insert in order for each weight and vertex
has entered */
insert_in_order(w,v, g[i]);
}
print(g[i]); /* print the first node_Ptr in g */

}

printf("Please enter vertex to start from");
scanf("%d",&start);

Dijkstra(start,n_vertices,g[i]);
/*destroy(g); give back dynamically allocated memory in the list */
print(g[i]);
return 0;

}

void Dijkstra(int start,int n_vertices,node_ptr list)
{
int mark[15];
int graph[15][15],s[15];
int i,u, count = 0;
int pathestimate[15],predecessor[15];
int minimum(int a[],int m[],int k);
int j;

for(j=1;j<=n_vertices;j++)
{
mark[j]=0;
pathestimate[j]=10000;
predecessor[j]=0;
}
pathestimate[start]=0;

while(count<n_vertices)
{
u=minimum(pathestimate,mark,n_vertices);
s[++count]=u;
mark[u]=1;

for(i=1;i<=n_vertices;i++)
{
if(graph[u][i]>0)
{
if(mark[i]!=1)
{

if(pathestimate[i]>pathestimate[u]+graph[u][i])
{

pathestimate[i]=pathestimate[u]+graph[u][i];
predecessor[i]=u;
}
}
}
}
}

}

int minimum(int a[],int m[],int k)
{
int mi=999;
int i,t = 0;

for(i=1;i<=k;i++)
{
if(m[i]!=1)
{
if(mi>=a[i])
{
mi=a[i];
t=i;
}
}
}
return t;

}


before you start,i suggest you re-read dijsktra algorithm
from CLR90 -Introduction to algorithms, by Cormen.
draw a graph on paper,consider its adjacency matrix
write that in a file,make a routine in your program thats
taking the adj matrix from the file.
then compute by hand the shortest path you want on paper,
and see if your algorithm gives the same path you expect it
to give.
i suggest you use msvc .net and put watches on mark,pathestimate,
pathpredecesor,and try to view at the same time what that means
for your graph structure.
have fun :)

.

Relevant Pages

  • Re: C++ more efficient than C?
    ... If you want to do language comparisons, ... complicated algorithm, though). ... int compare ... not been in C's standard library. ...
    (comp.lang.c)
  • Re: Mersenne Twister -- A Revised C++ Implementation
    ... "That algorithm is a slight elaboration on the basic linear congruential ... takes an int, and an int on the target you seem to be developing on -- ... unless you qualify it by stressing that you ... compilation to pick the appropriate type in a more general manner. ...
    (comp.lang.cpp)
  • Re: Non-restoring binary square root and convergence
    ... I took the algorithm from "Algorithms for Extracting Square Roots and Cube ... % sqrt 9 16 ... int main ...
    (sci.math)
  • Re: Non-restoring binary square root and convergence
    ... I took the algorithm from "Algorithms for Extracting Square Roots and Cube ... % sqrt 9 16 ... int main ...
    (comp.programming)
  • Re: dijkstra algorithm issue
    ... and debug the algorithm?? ... int n_vertices; ... draw a graph on paper,consider its adjacency matrix ... then compute by hand the shortest path you want on paper, ...
    (comp.programming)
Loading