Write a function that implements Dijkstras algorithm, and finds the shortest path from a given vertex to the most distant vertex.

The given graph has positive edge-lengths.

You write a function

struct edge list * Dijkstra(int n, int *graph, int start);

The vertices of the graph are numbered 0 to n ? 1; start is the start vertex and graph is the pointer to the start of the distance matrix.

If *(graph +n*i +j) is less than 100, that number is the distance from vertex i to vertex j; else the two vertices are not connected by an edge.

Your function returns a list of edges

struct edge list { int u; int v; struct edgelist * next}; which are the edges on the shortest path from start to the vertex with the largest distance from start.

TEST CODE:

#include

#include

int main()

{ list_node_t *path;

long i,j,k,l, dist, length;

int *graph;

struct edgelist * result, *tmp;

graph = (int *) malloc( 1000000*sizeof(int) );

for(i=0; i<1000; i++)

for(j=0; j<1000;j++)

*(graph+1000*i+j) = 100;

/* now create 30 by 30 grid */

for(k=0; k<29; k++)

for(l=0; l<30;l++)

{ i = 30*k + l;

j = 30*(k+1 ) + l;

*(graph+1000*i+j) = 1;

*(graph+1000*j+i) = 1;

}

for(k=0; k<30; k++)

for(l=0; l<29;l++)

{ i = 30*k + l;

j = 30*k + l+1;

*(graph+1000*i+j) = 1;

*(graph+1000*j+i) = 1;

}

for(k=0; k<10; k++)

for(l=0; l<10;l++)

{ i = 900+10*k + l;

j = 30*3*k + 3*l;

*(graph+1000*i+j) = 18;

*(graph+1000*j+i) = 18;

}

for(k=0; k<10; k++)

for(l=0; l<9;l++)

{ i = 900+10*k + l;

j = 900+10*k + l +1;

*(graph+1000*i+j) = 2;

*(graph+1000*j+i) = 2;

}

for(k=0; k<9; k++)

for(l=0; l<10;l++)

{ i = 900+10*k + l;

j = 900+10*(k+1) + l;

*(graph+1000*i+j) = 2;

*(graph+1000*j+i) = 2;

}

result = Dijkstra(1000, graph, 31);

dist = 0;

if( result-> v != 31 && result-> u != 31 )

{ printf("Wrong startvertex; should be 31, but first edges goes from %d to %d. ", result->v, result->u ); fflush(stdout);

exit(-1);

}

tmp = result;

printf("Path is: ");

while( tmp != NULL )

{ printf("%d-%d, ", tmp->u, tmp->v);

tmp = tmp-> next;

}

printf(" "); fflush(stdout);

dist = *(graph + 1000*(result->v) + (result->u));

while( result->next != NULL)

{ result = result-> next;

length = *(graph + 1000*(result->v) + (result->u));

if( length >= 100 )

{ printf("Path uses non-edge: no edge between %d and %d ",

result->u, result->v ); fflush(stdout);

exit(-1);

}

dist += length;

}

if( length != 54 )

{ printf("Length of path is %d, should be 54. "); fflush(stdout);

exit(-1);

}

printf("Passed Test "); fflush(stdout);

}

PLEASE HELP!!!!!!!!!!